Olimpíadas ⇒ (OBM - 2007) Análise Combinatória Tópico resolvido

[triplebig]

Olá galera,

Esta questão caiu na OBM e eu até agora não a entendi. O enunciado é o seguinte:

"Em um certo país há 21 cidades e o governo pretende construir n estradas (todas de mão dupla), sendo que cada estrada liga exatamente duas das cidades do país. Qual o menor valor de n para que, independente de como as estradas sejam construídas, seja possível viajar entre quaisquer duas cidades (passando, possivelmente, por cidades intermediárias)? "

O meu raciocínio foi: 21 estradas, construindo um poligono de 21 lados ligando as cidades. Assim, cada uma delas estará ligando duas outras cidades e alguem saindo de qualquer cidade poderá chegar em qualquer outra fazendo intermédio nelas.

Eu também raciocinei que o máximo de estradas possível seria 42, pois para cada cidade há exatamente duas estradas saindo delas.

O resultado da pergunta é 191, com a seguinte resolução:

"Escolha 20 das cidades do país. Ligando duas quaisquer delas por uma estrada, utilizaremos [tex3]C_2^2[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^2[/tex3]

=190 estradas, e a cidade restante não poderá ser alcançada de automóvel. Logo se deve construir pelo menos 191 estradas. Vamos mostrar que com essa quantidade é possível atingir
nosso objetivo.

Suponha que n = 191, mas que seja possível dividir as cidades do país em dois grupos A e B,
digamos com a e b cidades, respectivamente, de tal sorte que nenhuma cidade de A possa ser alcançada de automóvel a partir de qualquer cidade de B. Então o número de estradas no país é no máximo [tex3]C_2^a+C_2^b[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^a+C_2^b[/tex3]

, de modo que [tex3]C_2^a+C_2^b\geq191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^a+C_2^b\geq191[/tex3]

,ou ainda, [tex3](a^2+b^2)-(a+b)\geq2.191=382[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a^2+b^2)-(a+b)\geq2.191=382[/tex3]

.
Como a+ b = 21, segue da inequação que [tex3]a^2+b^2\geq282+21=403[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a^2+b^2\geq282+21=403[/tex3]

(?????? é assim que está escrito, mas acho que era pra ser 121...). Logo
[tex3]ab=\frac{(a+b)^2-(a^2+b^2)}{2}\leq\frac{441-403}{2}=19[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab=\frac{(a+b)^2-(a^2+b^2)}{2}\leq\frac{441-403}{2}=19[/tex3]

Mas, como a + b = 21 e a e b são naturais, temos [tex3]ab\geq1.20 = 20[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab\geq1.20 = 20[/tex3]

, uma contradição.

Logo, se n = 191, sempre é possível viajar entre quaisquer duas cidades. "

Eu não entendi simplesmente nada!!! Se eu digitei algo errado,

Questão: http://www.obm.org.br/provas/obm2007/2F ... 3_2007.pdf

Resolução http://www.obm.org.br/frameset-provas.htm (segunda fase nivel 3 2007)

Alguem porfavor ajuda, tou de saco cheio tentando entender isso!

abraços

[edu_landim]

A resposta não é 21 pois deseja-se

Qual o menor valor de n para que, independente de como as estradas sejam construídas, seja possível viajar entre quaisquer duas cidades (passando, possivelmente, por cidades intermediárias)? "

Desta foma devemos descobrir um número [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

de estradas que mesmo que quisessemos deixar uma cidade sem ligação isso não seria possível. Como por exemplo 1.000.000 estradas, mas deve ser o menor desses números.

Tentando deixar uma cidade isolada, devemos ligar apenas as outras 20 cidades e isso pode ser feito até que não haja mais modos de interligar as 20 cidades. Definir uma estrada é definir seus extremos, ou seja, o número máximo de estradas que interligaram as 20 cidades é [tex3]C^{20}_{2}\,=\,190[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C^{20}_{2}\,=\,190[/tex3]

.

Assim com a construção de mais uma estrada a cidade que se queria isolar estará interligada às demais, pois não outra possibilidade de evitar o isolamento.

Acredito que isso baste como solução.


Tentando detalhar um pouco mais os cálculos na resolução proposta. Na resolução houve uma distribuição das 21 cidades em dois gupos "isolados" (sem estradas que ligue cidades de um grupo com as do outro); um grupo com [tex3]a[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a[/tex3]

cidades e outro com as restantes: [tex3]b[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]b[/tex3]

ou [tex3]21\,-\,a[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]21\,-\,a[/tex3]

cidades.

Ele tenta então fazer uma prova por absurdo e admite que haja um modo de construir estrutura viária mesmo com mais de 190 estradas.

[tex3]C_2^a+C_2^b\geq191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^a+C_2^b\geq191[/tex3]

Veja que
[tex3]C_2^a\,=\,\frac{a\,\cdot\,(a\,-\,1)}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^a\,=\,\frac{a\,\cdot\,(a\,-\,1)}{2}[/tex3]

e
[tex3]C_2^b\,=\,\frac{b\,\cdot\,(b\,-\,1)}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C_2^b\,=\,\frac{b\,\cdot\,(b\,-\,1)}{2}[/tex3]

Substituinda na desigualdade temos

[tex3]\frac{a\,\cdot\,(a\,-\,1)}{2}\,+\frac{b\,\cdot\,(b\,-\,1)}{2}\,\geq191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{a\,\cdot\,(a\,-\,1)}{2}\,+\frac{b\,\cdot\,(b\,-\,1)}{2}\,\geq191[/tex3]

[tex3]\frac{a^2\,-\,a\,+\,b^2\,-\,b}{2}\,\geq191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{a^2\,-\,a\,+\,b^2\,-\,b}{2}\,\geq191[/tex3]

[tex3]\frac{(a^2\,+\,b^2)\,-\,(a\,+\,b)}{2}\,\geq191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{(a^2\,+\,b^2)\,-\,(a\,+\,b)}{2}\,\geq191[/tex3]

[tex3](a^2\,+\,b^2)\,-\,(a\,+\,b)\,\geq 2\,\cdot\,191[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a^2\,+\,b^2)\,-\,(a\,+\,b)\,\geq 2\,\cdot\,191[/tex3]

lembre-se que [tex3]a\,+\,b\,=21\,\,\,[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a\,+\,b\,=21\,\,\,[/tex3]

(I)

[tex3](a^2\,+\,b^2)\,-\,21\,\geq 382[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a^2\,+\,b^2)\,-\,21\,\geq 382[/tex3]

[tex3](a^2\,+\,b^2)\,\geq 382\,+\,21\,\,\,[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a^2\,+\,b^2)\,\geq 382\,+\,21\,\,\,[/tex3]

(perceba que é 382 e não 282)

[tex3](a^2\,+\,b^2)\,\geq 403\,\,\,[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a^2\,+\,b^2)\,\geq 403\,\,\,[/tex3]

(II)


Então ele utiliza

[tex3](a\,+\,b)^2\,=\,a^2\,+\,2ab\,+\,b^2[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a\,+\,b)^2\,=\,a^2\,+\,2ab\,+\,b^2[/tex3]

[tex3]ab=\frac{(a+b)^2-(a^2+b^2)}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab=\frac{(a+b)^2-(a^2+b^2)}{2}[/tex3]

Substituindos os valores de (I) e (II) temos

[tex3]ab\,\leq\frac{21^2\,-\,403}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab\,\leq\frac{21^2\,-\,403}{2}[/tex3]

[tex3]ab\,\leq\frac{441\,-\,403}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab\,\leq\frac{441\,-\,403}{2}[/tex3]

[tex3]ab\,\leq 19[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab\,\leq 19[/tex3]

O que gera um absurdo.

[triplebig]

Valeu Edu_landim

Eu entendi a solução, mas o que eu não estou entendendo é esse fato:

"sendo que cada estrada liga exatamente duas das cidades do país"

Se liga duas cidades do pais eu não posso conectar 19 estradas em uma cidade só, tem que ser somente duas..

Não devo estar interpretanado corretamente ...

abraços

[edu_landim]

Cada estrada liga exatamente duas cidades é o mesmo que afirmar que cada estrada terá como extremos duas cidades. É diferente de afirmar que de cada cidade partem duas estradas.