Seis livros, numerados de 1 a 6, estão inicialmente distribuídos entre seis pessoas A, B, C, D , E e F, respectivamente. Cada uma delas pode trocar seu livro com o de outra pessoa uma única vez por dia. A tabela abaixo mostra um exemplo de possíveis trocas de livros entre as pessoas em dois dias. No 1º dia, as pessoas A e D, bem como B e E, trocaram livros entre si, e C e F não trocaram seus livros. No 2º dia, somente A e C trocaram livros entre si.
Distribuição de livros
A
B
C
D
E
F
No início
1
2
3
4
5
6
Após o 1º dia
4
5
3
1
2
6
Trocas: A \leftrightarrow D e B \leftrightarrow E
Após o 2º dia
3
5
4
1
2
6
Trocas: A \leftrightarrow C
Observe que, após o 2º dia, ocorreu a seguinte distribuição de livros:
• o livro que estava com A ficou com D, o livro que estava com D ficou com C, e o livro que estava com C ficou com A;
• o livro que estava com B ficou com E, e o livro que estava com E ficou com B;
• o livro que estava com F ficou com ele mesmo.
a) Complete a tabela abaixo de acordo com as trocas indicadas:
Distribuição de livros
A
B
C
D
E
F
No início
1
2
3
4
5
6
Após o 1º dia
Trocas: B \leftrightarrow D
Após o 2º dia
Trocas: A \leftrightarrow B e C \leftrightarrow E
b) Indique uma maneira de fazer as trocas para chegar na distribuição após o 2º dia indicada na tabela abaixo.
Distribuição de livros
A
B
C
D
E
F
No início
1
2
3
4
5
6
Após o 1º dia
Trocas: ___________________________
Após o 2º dia
6
1
2
3
4
5
Trocas: ___________________________
c) Explique por que sempre é possível, em dois dias, fazer trocas e obter qualquer distribuição de livros entre as seis pessoas.
Reportar erro na questãoResolução comentada
Resolução comentada
a) Em cada dia, quem troca apenas passa o livro que tem para o parceiro.
1º dia (B ↔ D): B fica com o livro 4 e D com o livro 2. Os demais ficam como estavam.
2º dia (A ↔ B e C ↔ E): A passa a ter o livro 4 (que estava com B) e B passa a ter o 1. C passa a ter o 5 e E o 3. D e F não trocam.
A
B
C
D
E
F
Início
1
2
3
4
5
6
Após o 1º dia
1
4
3
2
5
6
Após o 2º dia
4
1
5
2
3
6
Resposta: após o 1º dia, 1 4 3 2 5 6; após o 2º dia, 4 1 5 2 3 6.
b) A distribuição final é uma "rotação" dos livros: o livro de cada pessoa vai para a pessoa seguinte, e o de F vai para A. Uma rotação pode ser obtida com duas trocas do tipo "espelho", em que se inverte a ordem e depois se ajusta.
1º dia: A ↔ F, B ↔ E, C ↔ D. A distribuição fica 6, 5, 4, 3, 2, 1, que é a ordem invertida.
2º dia: B ↔ F, C ↔ E, e A e D não trocam. Partindo de 6, 5, 4, 3, 2, 1, B e F trocam os livros 5 e 1, e C e E trocam os livros 4 e 2. O resultado é 6, 1, 2, 3, 4, 5, como pedido.
c) Qualquer distribuição final decompõe as pessoas em ciclos disjuntos, como no exemplo do enunciado. Em cada ciclo, o livro de uma pessoa vai para a próxima, e o da última volta para a primeira. Ciclos de tamanho 1 não precisam de troca.
Vamos mostrar que cada ciclo se resolve em dois dias. Como os ciclos envolvem pessoas diferentes, as trocas de ciclos distintos podem ser feitas ao mesmo tempo.
Tome um ciclo com pessoas P_1,P_2,\dots,P_k, em que o livro de P_i deve ir para P_{i+1} e o de P_k para P_1.
1º dia: P_i troca com P_{k+1-i}, o que inverte a ordem do ciclo. O livro de P_i vai para P_{k+1-i}. Cada pessoa troca no máximo uma vez, e quem fica no meio não troca.
2º dia: P_j troca com P_{k+2-j}, com os índices contados módulo k. Assim P_1 não troca, e P_2 troca com P_k, P_3 com P_{k-1}, e assim por diante.
O livro que começou com P_i passou no 1º dia para P_{k+1-i}, e no 2º dia vai para P_{k+2-(k+1-i)}=P_{i+1}. É exatamente o destino desejado. Isso vale para todos os livros do ciclo.
Portanto, com no máximo duas trocas por pessoa (uma em cada dia), qualquer distribuição de livros é obtida em dois dias.
Resposta: todo arranjo é composto de ciclos disjuntos, e cada ciclo se resolve com uma troca "em espelho" no 1º dia e outra no 2º dia, feitas em paralelo para todos os ciclos.
