Questão 18 (Nível 2) da OBMEP 2018

Question

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

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 18 (Nível 2) da OBMEP 2018

Nível 2 · Matemática: Lógica e raciocínio lógico

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

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

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.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Cada pessoa diz "meus dois vizinhos mentem". Vamos ver o que isso implica em cada caso.

Verdadeiro (V): a frase é verdadeira, então os dois vizinhos são mentirosos (M).

Mentiroso (M): a frase é falsa, então pelo menos um vizinho diz a verdade.

Consequências na mesa circular:

Cada V tem dois M ao lado, então dois V nunca ficam juntos.
Cada M tem pelo menos um V ao lado, então três M seguidos são impossíveis (o M do meio teria dois vizinhos M).
Logo, os grupos de M entre dois V consecutivos têm tamanho 1 ou 2.

Se há v verdadeiros, há v grupos de mentirosos, cada um com no máximo 2. Então M \le 2v.

Como v + M = 17, temos M \le 2(17 - M), ou seja, 3M \le 34 e M \le 11{,}33. Portanto M \le 11.

Verificação com M = 11 e v = 6: são 6 grupos de mentirosos, somando 11, então 5 grupos de 2 e 1 grupo de 1. Isso dá 5\cdot 2 + 1 = 11. A disposição V M M V M M V M M V M M V M M V M funciona: cada V está entre dois M, e cada M tem um V ao lado.

O máximo é 11.

Alternativa B.

Por que as outras alternativas estão erradas

A10 é possível, mas não é o máximo; existe configuração com 11 mentirosos.
C12 mentirosos exigiria v=5 e M\le10, o que é contraditório.
D15 mentirosos deixaria apenas 2 verdadeiros, e então haveria grupos de mentirosos com 3 ou mais seguidos.
ESe todos mentissem, nenhum mentiroso teria vizinho verdadeiro, e a frase "meus vizinhos mentem" seria verdadeira, o que é contraditório.

Assunto: Lógica e raciocínio lógico.

Reportar erro na resolução

Ver como caiu na prova

Questão 18 no caderno Nível 2 da OBMEP 2018

Fonte: OBMEP 2018 · Nível 2. Prova oficial ↗