OBMEP 2019: Seis livros, numerados de 1 a 6, estão inicialmente distribuídos entre seis pessoas A, B, C, D , E e F, respectivamente. Cada um...
OBMEP 2019: 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.
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 fi cou com C, e o livro que estava com C fi cou com A;
• o livro que estava com B ficou com E, e o livro que estava com E fi cou com B;
• o livro que estava com F ficou com ele mesmo.
a) Complete a tabela abaixo de acordo com as trocas indicadas:
b) Indique uma maneira de fazer as trocas para chegar na distribuição após o 2º dia indicada na tabela abaixo.
c) Explique por que sempre é possível, em dois dias, fazer trocas e obter qualquer distribuição de livros entre as seis pessoas.
QUESTÃO ANTERIOR:
- OBMEP 2019: Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2 × 2 do tabuleiro. Por exemplo, dos tabuleiros abaixo, o da esquerda é bacana e o da direita não é bacana.
GABARITO:
a)
b)
Além dessa maneira, existem outras formas diferentes de preenchimento:
c) Em uma configuração qualquer, podemos “acompanhar” para onde vai o livro de um dado estudante, e os livros subsequentes. Por exemplo, no item a) temos que “o livro de A vai para B, o livro de B vai para D, e o livro de D vai para A”. Note que, como o número de estudantes é finito, esse “acompanhamento” sempre volta ao ponto de onde começamos. A isso chamaremos de “ciclo”. Diremos que o “tamanho” do ciclo é o número de estudantes envolvidos. No exemplo citado do item a), temos um ciclo de tamanho 3.
Podemos mostrar que uma configuração qualquer consiste de vários ciclos: escolha um estudante e encontre o ciclo ao qual ele pertence. Remova esses estudantes e repita o processo. Como, a cada passo, diminuímos o número de estudantes em pelo menos uma unidade e como o número de estudantes é finito, o processo termina. Temos, assim, uma “coleção de ciclos disjuntos”.
Para mostrar que qualquer configuração pode ser obtida em 2 dias, temos que mostrar que um ciclo de qualquer tamanho entre 1 e 6 pode ser obtido após duas sequências de trocas.
Para isto, basta analisar, sem perda de generalidade, o ciclo que, após o segundo dia, tem a configuração
n,1, 2, ... n-2, n-1,
(o qual chamaremos de ciclo padrão de tamanho n), n = 1, 2, 3, 4, 5, 6.
Isto pode ser feito, por exemplo, da seguinte maneira:
- No primeiro dia, trocamos números opostos em relação ao centro da linha 1, 2, .., n.
- No segundo dia, fixamos o primeiro número obtido (n) e trocamos os números opostos em relação ao centro da linha restante obtida após retirarmos esse primeiro número.
Para esclarecer melhor, vamos detalhar esse procedimento para ciclos de diversos tamanhos.
Para um ciclo de tamanho 1 não há nada a fazer, o estudante mantém o livro por dois dias.
Para um ciclo de tamanho 2, uma troca basta: o livro de A vai para B, e o livro de B vai para A.
Analisemos os casos restantes possíveis, os ciclos de tamanho 3, 4, 5 e 6.
Ciclo de tamanho 3:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 3 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 4:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 4 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 5:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 5 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 6:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 6 e de como obtê-lo fazendo trocas em dois dias (é o primeiro exemplo que apresentamos na solução do item b)
Portanto, qualquer que seja a configuração final, podemos obtê-la após 2 dias de trocas.
Generalização:
Note que essa análise é válida para qualquer número de estudantes: em um grupo de n estudantes, podemos obter uma configuração qualquer de livros entre eles após trocas realizadas em apenas 2 dias.
Para mostrar o caso geral de um ciclo padrão de tamanho n, vamos denotar os estudantes por A1, A2, …, An.
Inicialmente eles têm os livros 1, 2, …, n.
No primeiro dia o estudante Ak troca de livro com o estudante An-k+1. Se, para algum k, ocorrer que k = n – k + 1, esse estudante mantém seu livro (esse caso acontece para todo n ímpar). No segundo dia, o estudante A1 não troca com ninguém e, para k de 2 a n, o estudante Ak troca de livro com o estudante An – k + 2.
Assim, após o primeiro dia, o estudante A1 está com o livro n, e, para k entre 2 e n, o estudante Ak está com o livro n – k + 1. Após o segundo dia o estudante Ak está com o livro que An – k + 2 = An – (k – 1) + 1 recebeu depois do primeiro dia, isto é, com o livro k – 1, e o ciclo padrão de tamanho n está completo.
PRÓXIMA QUESTÃO:
- mais questões da OBMEP.
QUESTÃO DISPONÍVEL EM:
- Questões da OBMEP 2019 (2ª Fase) com Gabarito e Resolução
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.
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 fi cou com C, e o livro que estava com C fi cou com A;
• o livro que estava com B ficou com E, e o livro que estava com E fi cou com B;
• o livro que estava com F ficou com ele mesmo.
a) Complete a tabela abaixo de acordo com as trocas indicadas:
b) Indique uma maneira de fazer as trocas para chegar na distribuição após o 2º dia indicada na tabela abaixo.
c) Explique por que sempre é possível, em dois dias, fazer trocas e obter qualquer distribuição de livros entre as seis pessoas.
QUESTÃO ANTERIOR:
- OBMEP 2019: Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2 × 2 do tabuleiro. Por exemplo, dos tabuleiros abaixo, o da esquerda é bacana e o da direita não é bacana.
GABARITO:
a)
b)
Além dessa maneira, existem outras formas diferentes de preenchimento:
c) Em uma configuração qualquer, podemos “acompanhar” para onde vai o livro de um dado estudante, e os livros subsequentes. Por exemplo, no item a) temos que “o livro de A vai para B, o livro de B vai para D, e o livro de D vai para A”. Note que, como o número de estudantes é finito, esse “acompanhamento” sempre volta ao ponto de onde começamos. A isso chamaremos de “ciclo”. Diremos que o “tamanho” do ciclo é o número de estudantes envolvidos. No exemplo citado do item a), temos um ciclo de tamanho 3.
Podemos mostrar que uma configuração qualquer consiste de vários ciclos: escolha um estudante e encontre o ciclo ao qual ele pertence. Remova esses estudantes e repita o processo. Como, a cada passo, diminuímos o número de estudantes em pelo menos uma unidade e como o número de estudantes é finito, o processo termina. Temos, assim, uma “coleção de ciclos disjuntos”.
Para mostrar que qualquer configuração pode ser obtida em 2 dias, temos que mostrar que um ciclo de qualquer tamanho entre 1 e 6 pode ser obtido após duas sequências de trocas.
Para isto, basta analisar, sem perda de generalidade, o ciclo que, após o segundo dia, tem a configuração
n,1, 2, ... n-2, n-1,
(o qual chamaremos de ciclo padrão de tamanho n), n = 1, 2, 3, 4, 5, 6.
Isto pode ser feito, por exemplo, da seguinte maneira:
- No primeiro dia, trocamos números opostos em relação ao centro da linha 1, 2, .., n.
- No segundo dia, fixamos o primeiro número obtido (n) e trocamos os números opostos em relação ao centro da linha restante obtida após retirarmos esse primeiro número.
Para esclarecer melhor, vamos detalhar esse procedimento para ciclos de diversos tamanhos.
Para um ciclo de tamanho 1 não há nada a fazer, o estudante mantém o livro por dois dias.
Para um ciclo de tamanho 2, uma troca basta: o livro de A vai para B, e o livro de B vai para A.
Analisemos os casos restantes possíveis, os ciclos de tamanho 3, 4, 5 e 6.
Ciclo de tamanho 3:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 3 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 4:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 4 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 5:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 5 e de como obtê-lo fazendo trocas em dois dias:
Ciclo de tamanho 6:
Abaixo está um exemplo típico de um ciclo (padrão) de tamanho 6 e de como obtê-lo fazendo trocas em dois dias (é o primeiro exemplo que apresentamos na solução do item b)
Portanto, qualquer que seja a configuração final, podemos obtê-la após 2 dias de trocas.
Generalização:
Note que essa análise é válida para qualquer número de estudantes: em um grupo de n estudantes, podemos obter uma configuração qualquer de livros entre eles após trocas realizadas em apenas 2 dias.
Para mostrar o caso geral de um ciclo padrão de tamanho n, vamos denotar os estudantes por A1, A2, …, An.
Inicialmente eles têm os livros 1, 2, …, n.
No primeiro dia o estudante Ak troca de livro com o estudante An-k+1. Se, para algum k, ocorrer que k = n – k + 1, esse estudante mantém seu livro (esse caso acontece para todo n ímpar). No segundo dia, o estudante A1 não troca com ninguém e, para k de 2 a n, o estudante Ak troca de livro com o estudante An – k + 2.
Assim, após o primeiro dia, o estudante A1 está com o livro n, e, para k entre 2 e n, o estudante Ak está com o livro n – k + 1. Após o segundo dia o estudante Ak está com o livro que An – k + 2 = An – (k – 1) + 1 recebeu depois do primeiro dia, isto é, com o livro k – 1, e o ciclo padrão de tamanho n está completo.
PRÓXIMA QUESTÃO:
- mais questões da OBMEP.
QUESTÃO DISPONÍVEL EM:
- Questões da OBMEP 2019 (2ª Fase) com Gabarito e Resolução
COMENTÁRIOS