OBMEP 2018: Ao redor de uma mesa sentaram-se os 17 participantes de um debate

OBMEP 2018: Ao redor de uma mesa sentaram-se os 17 participantes de um debate. Alguns deles sempre dizem a verdade, e os demais sempre mente...

OBMEP 2018: Ao redor de uma mesa sentaram-se os 17 participantes de um debate. Alguns deles sempre dizem a verdade, e os demais sempre mentem. Todos iniciaram o debate dizendo: “Meus dois vizinhos mentem”. No máximo, quantos mentirosos havia entre os participantes?

A) 10
B) 11
C) 12
D) 15
E) 17

QUESTÃO ANTERIOR:
- OBMEP 2018: Na figura abaixo, ABCD é um paralelogramo. O ponto E é ponto médio de AB, e F é ponto médio de CD. Qual é a razão entre a área do triângulo GIH e a área do paralelogramo ABCD?

RESOLUÇÃO:

Quando um participante que diz a verdade diz que seus dois vizinhos mentem, podemos concluir que ele tem, de fato, um mentiroso de cada lado.

Quando a frase é dita por um mentiroso, ela é necessariamente falsa; em consequência, pelo menos um dos vizinhos de um mentiroso deverá dizer a verdade.

Portanto, não pode haver mais do que dois mentirosos consecutivos. Isto significa que o número de mentirosos não pode exceder 2/3 dos participantes (já que dois mentirosos consecutivos devem ser sucedidos por uma pessoa que diz a verdade). Como 2/3 de 17 é igual a 11 + (1/3), pode haver no máximo 11 mentirosos.

Resta verificar se é de fato possível colocar 11 mentirosos e 6 pessoas que dizem a verdade em círculo de modo que cada pessoa que diz a verdade esteja ladeada por mentirosos e pelo menos um vizinho de cada mentiroso diga a verdade. Para tal, basta numerar as cadeiras de 1 a 17 e colocar as pessoas que dizem a verdade nas cadeiras 3, 6, 9, 12, 15 e 17 e as mentirosas nas demais. Note que, nessa situação, cada pessoa que diz a verdade está ao lado de dois mentirosos e cada mentiroso tem a seu lado uma pessoa que mente e outra que diz a verdade, com exceção do sentado na cadeira 16, que tem duas pessoas que dizem a verdade a seu lado. Portanto, o número máximo de mentirosos é, de fato, igual a 11.

RESPOSTA:
B) 11

PRÓXIMA QUESTÃO:
- OBMEP 2018: Para fazer um percurso do ponto P ao ponto Q da fi gura, uma formiguinha deve andar sobre os segmentos horizontais sempre para a direita e nunca passar duas vezes por um mesmo segmento vertical. De quantas maneiras diferentes ela pode fazer esse percurso?