Questão FC317116
Uma empresa administra salas de bate papo para treinamento de idiomas. A regra dessas salas é que cada estudante deve falar com todos os outros, mas só pode falar com outro colega
Princípio da Casa dos Pombos
Com. Org. (IFSP) · 2018
Uma empresa administra salas de bate papo para treinamento de idiomas. A regra dessas salas é que cada estudante deve falar com todos os outros, mas só pode falar com outro colega estudante em apenas um idioma. Se o estudante A conversar com o estudante B no idioma X, A e B manterão contanto nesse idioma apenas, porém o estudante A pode conversar com o estudante C em outra língua se assim desejar, no entanto, uma vez definido o idioma, o contato será apenas nesse idioma escolhido. A empresa verificou, nas salas de treinamento com exatamente dois idiomas, que todas as configurações com seis estudantes permitiam encontrar um trio que conversava entre si em um idioma. Em algumas salas com cinco estudantes eles não conseguiram encontrar esse mesmo fenômeno. A empresa, então, decidiu olhar para as salas de treinamento com exatamente três idiomas para ver se encontrava um trio que também conversava entre si em um idioma. Dadas as regras das salas, qual é o número mínimo de pessoas em uma sala com três idiomas para garantir que existam três estudantes que conversem entre si em um idioma?
- 15
- 16
- 17
- 18
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
17 pessoas é o número mínimo.
Considere um estudante qualquer E₁. Fora ele há 16 colegas. Distribuindo essas 16 conversas em 3 idiomas, pelo princípio da casa dos pombos deve haver ao menos \( \lceil 16/3\rceil = 6 \) estudantes que falam com E₁ no mesmo idioma A.
Se entre esses 6 algum par conversa também em A, então formamos um trio (E₁ e esse par) falando o mesmo idioma.
Se nenhum par desses 6 fala em A, então todas as conversas entre eles ocorrem apenas nos outros dois idiomas. Mas, pelo enunciado, em qualquer configuração com 6 pessoas e 2 idiomas existe um trio monocromático. Assim, também aparece um trio falando o mesmo idioma.
Portanto, com 17 pessoas é garantido um trio que conversa entre si num idioma. Quanto à minimalidade: com 16 pessoas teríamos \( \lceil 15/3\rceil = 5 \) colegas num mesmo idioma, e já se admite a existência de uma configuração de 5 sem trio, logo 16 não basta.
Conteúdo do catálogo FC Concursos · Atualizado em