Re: [obm-l] Involucao (e Teorema de T�ran)

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi Gugu e demais membros da lista,

O problema � bem legal mesmo... eu s� consegui
resolver porque j� conhecia o padr�o dos exemplos
pequenos, que acabei aprendendo por causa do problema
da IMO 93 (veja abaixo) e de uma tentativa minha de
provar o teorema de Beatty.

Antes, na lista, foi comentado o teorema de T�ran, em
particular sua aplica��o no problema abaixo (ali�s,
parab�ns ao Cl�udio pela resolu��o!!)

> Sao dados 21 pontos numa circunferencia. Mostre que
pelo menos 100 arcos determinados por estes pontos
medem menos de 2/3*pi.

O teorema de T�ran � um teorema de grafos, e diz o
seguinte: um grafo tem n v�rtices, n > 1 fixado. Seja
m < n um n�mero inteiro positivo maior que 1, fixado
tamb�m. O grafo que n�o cont�m um subgrafo K_m (grafo
completo com m v�rtices - um grafo completo � um grafo
no qual ligamos quaisquer dois v�rtices) e que tem o
maior n�mero de arestas poss�vel � um grafo
(m-1)-partido completo, na qual as classes de v�rtices
t�m os n�meros mais iguais de v�rtices poss�vel, ou
seja, a diferen�a entre as suas cardinalidades � no
m�ximo 1. Um grafo (m-1)-partido completo pode ser
obtido da seguinte forma: divida os n v�rtices em m-1
classes e ligue todos os pares de v�rtices que *n�o*
est�o em uma mesma classe. No caso do teorema de
T�ran, as classes ainda s�o as mais "iguais"
poss�veis, tendo [n/m] ou [n/m] + 1 v�rtices.

O teorema de T�ran foi assunto de um cap�tulo inteiro
do lindo livro "Proofs From The Book", que cont�m uma
s�rie de demonstra��es elegantes de v�rios teoremas.

Agora, vamos utiliz�-lo para resolver o problema.
Ali�s, acho que o enunciado tem que ser "menor ou
igual" a 120 graus, n�o �? Se a gente considerar que
pontos podem coincidir, tome os v�rtices de um
tri�ngulo equil�tero e coloque neles 7, 7 e 7 pontos,
respectivamente. H� 3*7*6/2 = 63 < 100 �ngulos menores
que 120 graus (todos medindo 0).

Considere o grafo cujos v�rtices s�o os 21 pontos e
dois pontos s�o ligados se o �ngulo determinando por
eles na circunfer�ncia � estritamente maior que 120
graus. Claramente este grafo n�o tem tri�ngulos (um
K_3), ent�o o n�mero de arestas � menor ou igual ao
caso maximal do teorema, um grafo 2-partido
(bipartido) completo com 10 e 11 v�rtices em cada
classe. Ou seja, o n�mero de arestas � no m�ximo 10*11
= 110 (ligamos dois v�rtices, um de cada grupo). Isto
quer dizer que no m�ximo 110 pares de pontos
determinam um �ngulo maior que 120 graus. Assim, os
demais pares, que s�o pelo menos 21*10/2 - 110 = 100,
determinam �ngulos menores ou iguais a 120 graus.

O teorema de T�ran tambem proporciona uma solu��o bem
curta do problema 5 (acho) da IMO 1992: considere 9
pontos no plano, n�o havendo entre eles 3 colineares.
Determine o maior n�mero de segmentos que podemos
desenhar, usando as cores azul ou vermelho, de modo
que n�o haja um tri�ngulo com v�rtices em tr�s dos 9
pontos ligados por segmentos de mesma cor. Para
resolver, use o fato de que R(3,3) = 6, ou seja, um
K_6 cujas arestas s�o pintadas de duas cores tem com
certeza um tri�ngulo (K_3) cujas arestas s�o todas de
mesma cor e os outros grafos completos menores podem
ser pintados de modo a n�o haver um tri�ngulo com
arestas de mesma cor (para o K_5 s� h� essencialmente
uma maneira de pintar!).

[]'s
Shine

--- Carlos Gustavo Tamm de Araujo Moreira
<gugu@impa.br> wrote:
>    Caro Shine,
>    Na verdade eu fiquei sabendo desse problema pela
> lista mesmo (se nao me
> engano proposto pelo Claudio Buffara) e sugeri que
> fosse incluido numa lista 
> de treinamento para a IMO. E' bem legal, nao ?
>    Abracos,
>             Gugu
>  
> >
> >Oi,
> >
> >Esse problema � de uma lista da prepara��o para a
IMO desse ano e, se n�o me engano, o Gugu o prop�s (�
isso mesmo, Gugu?). A prepara��o desse ano j� foi,
ent�o podemos conversar sobre esse problema.
> >
> >Vamos ver alguns valores pequenos:
> >
> >f(1) = 1;
> >f(2) = 3;
> >f(3) = 2;
> >f(4) = 6;
> >f(5) = 8;
> >f(6) = 4;
> >f(7) = 11;
> >f(8) = 5;
> >f(9) = 14;
> >f(10) = 15;
> >f(11) = 7;
> >f(12) = 19;
> >f(13) = 21...
> >
> >Vamos formar os pares (a,b) nas quais f(a) = b e
f(b) = a (vamos convencionar a < b):

> >(1;1), (2;3), (4;6), (5;8), (7;11), (9;14),
(10;15), (12;19), (13;21)...
> >
> >Apareceram os n�meros consecutivos de Fibonacci
(1;1), (2;3), (5;8) e (13;21)... e as raz�es b/a em
cada par s�o muito pr�ximas... de phi = (1+raiz(5))/2!
> >
> >Pode-se provar que se x e y s�o irracionais tais
que 1/x + 1/y = 1 ent�o as seq��ncias [mx] e [ny], m,n
inteiros positivos, e [r] � o maior inteiro menor ou
igual a r, particionam os inteiros positivos, ou seja,
{[mx]} uni�o {[ny]} = Z+* e {[mx]} inter {[ny]} =
vazio (eu aprendi a demonstra��o desse fato no livro
"Elementary Number Theory", de Joe Roberts). phi e
phi^2 satisfazem essa condi��o, assim as seq��ncias
[m*phi] e [n*phi^2] particionam Z+*.
> >
> >Se voc� calcular os valores pequenos dessas duas
seq��ncias, pode conjecturar que f([n*phi]+1) =
[n*phi^2]+1 e f([n*phi^2]+1) = [n*phi]+1.
> >
> >Eu lembro que, na �poca, provei isso por indu��o,
adicionando algumas hip�teses para sair mais f�cil...
> >
> >Um problema relacionado caiu na IMO 1993 (acho que
o ano � esse...): Encontre uma fun��o f de N em N tal
que f(f(n)) = f(n) + n para todo n em N.
> >
> >[]'s
> >Shine
> >
> >> Caros colegas:
> >
> >> Este problema me foi proposto ha alguns meses
> pelo
> >Domingos Jr. mas eu nao consegui fazer. Trata-se da
> >generalizacao de um problema que ele resolveu aqui
> na
> >lista.
> >
> >> Seja N = conjunto dos inteiros positivos.
> >> 
> >> Definimos f:N --> N por:
> >> f(1) = 1
> >> e, para n > 1,
> >> f(n) = menor inteiro positivo que:
> >> i)  nao pertence a {f(1), ...., f(n-1)}
> >> e
> >> ii) faz com que [f(1) + ... + f(n)]/n seja
> inteiro.
> >> 
> >> Prove que f eh uma involucao, ou seja, eh tal que
> >f(f(n)) = n, para todo n em N. (em particular, isso
> >implica que f eh uma bijecao, que foi o que o
> Domingos
> >provou).
> >
> >> Qualquer ajuda serah bem-vinda.
> >
> >> Um abraco,
> >> Claudio.

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================