Um problema da Olimpíada de Matemática da Itália, de 1994:
Todo habitante da Ilha de Cavalheiros e Canalhas ou é um Cavalheiro (que sempre fala a verdade), ou é um Canalha (que sempre mente). Um jornalista visitante entrevista cada habitante da Ilha exatamente uma vez e obtém as seguintes respostas:
A(1): Nesta Ilha há pelo menos um Canalha.
A(2): Nesta Ilha há pelo menos dois Canalhas.
…
A(n-1): Nesta Ilha há pelo menos (n – 1) Canalhas.
A(n): Nesta Ilha todos são Canalhas.
Com estas respostas, o jornalista pode descobrir se há mais Cavalheiros que Canalhas na Ilha?
PCFilho
O último habitante é um canalha(Se fosse cavalheiro, sua afirmação seria verdadeira, porém ele diz que todos na ilha são canalhas, levando a uma contradição), indicando que o primeiro habitante é um cavalheiro.
ResponderExcluirO penúltimo habitante é um canalha(Se fosse cavalheiro, estaria dizendo que todos exceto ele são canalhas, porém o primeiro habitante também é cavalheiro, levando a outra contradição), também indicando que o segundo habitante é um cavalheiro.
Repetindo esse raciocínio, concluímos que a primeira metade dos entrevistados é composta apenas por cavalheiros, e a segunda metade apenas por canalhas, então há a mesma quantidade de cavalheiros e canalhas na ilha. E sim, n é um número par.
Se existem k canalhas na ilha, os primeiros k habitantes são cavalheiros pois estão dizendo a verdade e o restante (n-k) é canalha, pois estão mentindo.
ResponderExcluirPortanto para existir k canalhas na ilha, tem que haver também n-k canalhas
Sendo assim temos k = n-k
Ou k = n/2.
O jornalista pode concluir que metade da ilha é de canalhas e metade de cavalheiros
ST.