FANDOM


Exemplo (OBM 1999 - 3ª Fase - Nível 2)Editar

Um reino é formado por dez cidades. Um cidadão muito chato foi exilado da cidade A para a cidade B, que é a cidade do reino mais longe de A. Após um tempo, ele foi expulso da cidade B para a cidade C do reino mais longe de B. Sabe-se que a cidade C não é a mesma cidade A. Se ele continuar sendo exilado dessa maneira, é possível que ele retorne à cidade A?

Solução: Vamos nomear as outras cidades: D, E, F, G, H, I e J. Como C é a cidade mais distante de C, segue que AB< BC. Se repetirmos o mesmo raciocínio para outras cidades, teremos

AB<BC<CD<\dots<HI< IJ.

Para podermos fechar o ciclo, precisamos que A seja a cidade mais longe de J. Porém, como B é a cidade mais longe de A e pela desigualdade anterior

AJ< AB < IJ.

Contradição. Logo, é impossível que as cidades cumpram as condições do enunciado.

Exemplo (Putnam 1956)Editar

Considere um conjunto de 2n pontos no espaço (com n>1). Suponha que eles estão unidos por pelo menos n^2+1 segmentos. Mostre que pelo menos um triângulo é formado. Mostre também que para cada n é possível ter 2n pontos unidos por n^2 segmentos sem que um triângulo seja formado.

Solução: Vamos usar indução em n. Comecemos com n=2. Suponha que ligamos 2.2=4 pontos por 2^2+1=5 segmentos. No máximo, podemos ligar 4 pontos por 6 segmentos. Então, se traçarmos 5 segmentos, existem 2 pontos que não estão ligados (que chamaremos de A e B). Assim basta pegarmos um destes e os outros dois, para termos três pontos e todos eles ligados entre si, ou seja, um triângulo.

Considere agora que a afirmação seja válida para n-1 (com n>2), ou seja, quaisquer 2(n-1)=2n-2 pontos ligados por (n-1)^2+1=n^2-2n+2 segmentos tem um triângulo formado. Provaremos que o resultado vale para n.

Suponha que temos 2n pontos ligados por n^2+1 segmentos. Tome dois pontos, digamos P e Q, que estão ligados por um segmento. Nenhum dos outros pontos está ligado a P e Q ao mesmo tempo, pois se estivesse, teríamos um triângulo formado.

Se retirarmos P e Q ao mesmo tempo (junto com os segmentos que se juntam a eles), eliminaremos, no máximo, 2(n-1)+1=2n-1 segmentos (pois P e Q estão ligados e cada um dos outros pontos está ligado com, no máximo, um deles).

Então, sobrarão 2n-2 pontoos e n^2+1-(2n-1)=n^2-2n+2 segmentos e, por hipótese de indução, existe um triângulo formado.

Resta a segunda parte do exercício: aqui basta dividirmos os 2n pontos em dois conjuntos disjuntos de n pontos cada e ligarmos cada ponto de um conjunto com todos os outros pontos do outro. Com isso, teremos n^2 segmentos e nenhum triângulo formado.



Referências BibliográficasEditar

[1] E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.

Interferência de bloqueador de anúncios detectada!


A Wikia é um site grátis que ganha dinheiro com publicidade. Nós temos uma experiência modificada para leitores usando bloqueadores de anúncios

A Wikia não é acessível se você fez outras modificações. Remova o bloqueador de anúncios personalizado para que a página carregue como esperado.