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
=========================================================================