Re: OBM!!

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sun, 29 Oct 2000, Carlos Stein Naves de Brito wrote:

> Pela honra do nome desta lista ser OBM, alguem ajude na questao 5 da OBM!
> Grato
> Carlos 
> 

Vai aí o enunciado e um esboço de solução.

Enunciado:

Seja X o conjunto de todas as seqüências a = (a_1, ..., a_2000) 
tais que a_i \in {0,1,2} se 1 <= i <= 1000 e a_i \in {0,1} se 1001 <= i <= 2000.
Dados a e b \in X, definimos a distância entre a e b como sendo o número
de valores de i, 1 <= i <= 2000, tais que a_i é diferente de b_i.
Determine o número de funções f: X -> X que preservam distâncias,
isto é, tais que d(f(a),f(b)) = d(a,b).

Esboço de solução:

Você pode permutar as primeiras 1000 ou as últimas 100 coordenadas.
A cada uma das primeiras 1000 coordenadas podemos aplicar uma
permutação de {0,1,2} e a cada uma das últimas 1000 podemos aplicar
uma permutação de {0,1}. Isto nos dá 

(1000!)^2 * (3!)^1000 * (2!)^1000

funções f diferentes. Resta provar que toda função f tem esta forma.

Dizemos que duas seqüências são vizinhas se a distância entre elas é 1.
Cada seqüência a admite 3000 vizinhos, dentre os quais 2000 formam 1000
pares de vizinhos mútuos. Fora estes pares, as distâncias mútuas são 2.
Os 1000 pares equivalem a mudar uma das 1000 primeiras coordenadas;
os 1000 demais vizinhos equivalem a mudar uma das 1000 últimas.

Considere uma f satisfazendo o enunciado e observe f(0) e f dos vizinhos
de 0. A função f deve levar vizinhos de 0 em vizinhos de f(0)
e pares de vizinhos que são vizinhos mútuos em pares do mesmo tipo.
Existe exatamente uma f_1 dentre as construídas no início com estes
valores e não é difícil agora provar que f = f_1.

[]s, N.