[obm-l] Magicos

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Caros Pavlos et al,
   Vou contar a minha solucao parcial para o problema dos magicos, que
funciona para n > 11 (e tambem para n=6, 8, 9 e 10). Neste fim de semana o
Yoccoz pensou no problema e conseguiu uma outra solucao, que funciona para
todo n >= 7, como pede o enunciado do problema. Vamos primeiro lembrar o
enunciado:
  60. (St.Petersburg-1999) Três mágicos apresentam um truque entregando a
uma pessoa da platéia um maço de cartas numeradas com 1,2,...,2n+1 (n>6).
  O espectador fica com uma das cartas e aleatoriamente distribui as 
restantes entre o primeiro e o segundo mágicos (cada um deles fica com n 
cartas) . Estes olham suas cartas (sem se comunicar um ao outro) e cada um 
escolhe duas cartas formando um maço (ordenado) com estas cartas e as 
entrega ao terceiro mágico. O terceiro mágico olha estas quatro cartas e 
anuncia a carta que ficou com o espectador. Explique como este truque pode 
funcionar.

   As duas solucoes comecam do mesmo jeito : a ideia e' que cada magico
transmita de algum jeito a soma de suas n cartas modulo 2n+1 (e entao o
outro magico descobre a carta que foi retirada, que e' o simetrico da soma
dos dois resultados modulo 2n+1).
   Assim, basta definir uma funcao f: Z/(2n+1)xZ/(2n+1)->Z/(2n+1) tal que,
dado c em Z/(2n+1) e um subconjunto arbitrario A de Z/(2n+1) com n elementos
eles satisfazem a propriedade P(A,c):existem elementos distintos x e y de A
com f(x,y)=c.
   Eu tentei achar uma tal funcao na forma f(x,y)=x-by. Suponha que
b^2+b+1=0 (mod 2n+1).
Entao b^3=1 e, dado c, f(by+c,y)=c para todo y. Assim, se um conjunto A e'
ruim (isto e', nao satisfaz P(A,c)), entao para todo y que esteja em A com
by+c diferente de y, by+c nao pode estar em A. Como
b(b(by+c)+c)+c=b^3.y+c(b^2+b=1)=y, na tripla {y,by+c,b(by+c)+c} so' pode
haver um elemento de A, donde A nao pode ter muito mais de um terco dos
elementos de Z/(2n+1). Deixo os detalhes para voces. Temos que cuidar
separadamente dos y com by+c=y (podem ser um ou tres), e de que nem sempre
existe o tal b. Nesse caso trocamos 2n+1 por 2m+1 com m>n tal que exista b
com b^2+b+1=0 (mod 2m+1) (para n grande podemos mesmo tomar 2m+1 da forma
b^2+b+1), tal que um terco de 2m+1 ainda seja bem menor que n, e tomamos
f(x,y)=x-by (mod 2m+1)(mod 2n+1).Para 2n+1=13 podemos tomar b=3. Para
2n+1=19, podemos tomar b=7. isso resolve os casos 2n+1=19 e 2n+1=17 (com
m=8). Para 2n+1=21 podemos tomar b=4. Para 2n+1=31 podemos tomar b=5 (aqui o
tamanho de um conjunto ruim maximo e' 1+30/3=11, o que resolve portanto os
casos 2n+1=25,27,29 e 31.
    Mas vamos a solucao do Yoccoz, que funciona em todos os casos do
problema.A ideia dele foi mostrar a existencia de uma funcao f(x,y) como
acima que fosse equivariante, isto e',que satisfizesse f(x+c,y+c)=f(x,y)+c,
para quaisquer x,y e c. E' facil ver que para uma tal funcao f vale P(A,c)
se e somente se vale P(A-c,0), onde A-c={x-c|x em A}. Assim, basta ver que
todo A com n elementos satisfaz P(A,0). Agora, em vez de cosnstruir f, vamos
construir a pre-imagem de 0 pela f (ou um subconjunto conveniente dela).
Pela equivariancia, se (x,y) e (u,v) sao pares distintos com f(x,y)=f(u,v)=0
entao y-x tem que ser diferente de v-u, senao, para c=u-x, temos
(u,v)=(x+c,y+c), donde f(u,v)=c. Por outro lado dado um conjuno de pares
{(x1,y1),...,(xk,yk)} com yj-xj distinto de yi-xi para todo i distinto de j,
existe uma funcao equivariante f com f(xi,yi)=0 para todo i.
    Nosso problema agora se reduz a encontrar um conjunto de pares
{(x1,y1),...,(xk,yk)} com os yi-xi todos distintos (e distintos de 0) tal
que para todo A com n elementos exista i tal que xi e yi estejam em A. O
Yoccoz faz com que esse conjunto de pares contenha os pares
(0,1),(2,1),(0,2),(3,6),(9,6),(3,9),(4,8),(12,8) e (4,12). Note que as
diferencas yi-xi sao 1,-1,2,3,-3,6,4,-4 e 8, e que um A ruim so' pode conter
um elemento de cada uma das triplas {0,1,2},{3,6,9} e {4,8,12}. Vamos
completar nosso conjunto de pares com n-4 pares que formarao uma particao de
Z/(2n+1)\{0,1,2,3,6,9,4,8,12}. Um conjunto ruim so' pode ter um elemento de
cada par, tendo pois no maximo n-4+3=n-1 elementos, como queriamos. Para
isso ele considera alguns casos:
    I)n par, n>=12: Escrevemos n=2k.Os pares serao
(-k+6,k+6),(-k+7,k+5),...,(-1,13) (diferencas n,n-2,...,14);
(k+7,3k+6),(k+8,3k+5),...,(2k+4,2k+9) (diferencas n-1,n-3,
...,-5); e (2k+5,5),(2k+6,7),(2k+7,11) e (2k+8,10) (diferencas -n,1-n,4-n e
2-n).
    II)n impar, m>=13: Escrevemos n=2k+1. Os pares serao
(-1,13),...,(-k+6,k+6) (diferencas 14,...,n-1); (k+7,3k+8),...,(2k+5,2k+10)
(diferencas n,...,5); e (2k+6,5),(2k+7,7),(2k+8,11) e (2k+9,10) (diferencas
-n,1-n,4-n e 2-n).
    Casos particulares anteriores:
    n=7: Pares (5,10),(13,11) e (7,14) (diferencas 5,-2 e 7).
    n=8: Pares (5,-1),(7,14),(15,10) e (13,11) (diferencas -6,7,-5 e -2).
    n=9: Pares (5,14),(16,7),(10,17),(18,11) e (15,13) (diferencas 9,-9,7,-7
e -2).
    n=10: Pares (20,10),(19,11),(18,13),(5,14),(16,7) e (17,15) (diferencas
-10,-8,-5,9,
 -9 e -2).
    n=11: Pares (16,5),(17,7),(20,11),(18,10),(19,13),(21,14) e (15,22)
(diferencas -11,
 -10 ,-9,-8,-6,-7 e 7).
    
     Abracos,
             Gugu
    
  
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================