Lógica, Jogos e Pensamento Computacional
Prof. Bruno Holanda
Problema 1. (OMCPLP 2022) Anselmo e Beto jogam alterna-
damente um jogo com frutas em uma caixa. A caixa tem inici-
almente 32 frutas. Anselmo joga primeiro e cada jogada consiste
em retirar 1, 2 ou 3 frutas da caixa ou retirar 2/3 das frutas
da caixa (essa jogada só é possı́vel caso o número de frutas na
caixa seja múltiplo de 3). O jogador que retirar a última fruta da
caixa vence. Qual dos dois jogadores possui estratégia vencedora?
Como este jogador deve jogar para vencer?
Problema 2. São dadas 4 moedas aparentemente iguais. Sabe-
se que uma delas é falsa (tem peso diferente das demais e não se
sabe se ela é mais leve ou mais pesada). Mostre como descobrir
a moeda falsa com 2 pesagens em uma balança de dois pratos.
Problema 3. Carlitos possui seis moedas, sendo uma delas falsa.
Nós não sabemos o peso de uma moeda falsa e nem o peso de
uma moeda verdadeira, sabemos apenas que as moedas verdadei-
ras possuem todas o mesmo peso e que o peso da moeda falsa é
diferente. Dispomos de uma balança de dois pratos. Mostre como
é possı́vel descobrir a moeda falsa usando apenas três pesagens.
Problema 4. No gabinete de ações ultra-secretas de um paı́s,
trabalham 15 agentes. Cada um deles conhece uma parte de uma
informação confidencial. Quando dois agentes se encontram, eles
trocam as informações que possuem e cada um fica sabendo o que
1
tudo o que o outro sabia. O agente também não esquece o que já
sabia antes do encontro. Cada encontro envolve exatamente dois
agentes. Prove que 26 encontros são suficientes para que todos os
agentes saibam da informação confidencial completa.
Problema 5. Você tem cinco caixas consecutivas numeradas de
1 a 5, nas quais um gato está escondido em uma delas. Todas
as noites ele pula para uma caixa vizinha da qual se encontra e
todas as manhãs você tem uma chance de abrir exatamente uma
caixa para tentar encontrá-lo. Se você abrir uma caixa e o gato
não estiver lá, então você deve fechá-la e tentar novamente no
outro dia. Existe alguma estratégia para encontrar o gato em no
máximo seis dias?
Problema 6. Sobre uma mesa há 14 moedas aparentemente
iguais. Porém, sete são verdadeiras e sete são falsas. Adriano
sabe quais são verdadeiras e quais são falsas, mas Bianca não.
Ela sabe apenas que:
• Todas as moedas falsas têm peso iguais entre si.
• Todas as moedas verdadeiras têm peso iguais entre si.
• As moedas verdadeiras são mais pesadas dos que as falsas.
Adriano pode comprovar para Bianca quais moedas são falsas por
meio de três pesagens em uma balança de dois pratos?
Problema 7. Os 2018 moradores de uma cidade estão dividi-
dos em duas classes: cavalheiros, que sempre dizem a verdade, e
mentirosos, que sempre mentem. Certo dia todos os moradores
2
sentaram-se ao redor de uma circunferência e cada um deles falou
em voz alta “Meus dois vizinhos, o da esquerda e o da direita, são
mentirosos”. Logo após, um dos moradores abandonou a cidade.
Os 2017 que permaneceram sentaram-se novamente em uma cir-
cunferência (não necessariamente na mesma ordem que antes) e
cada um deles falou em voz alta “Nenhum de meus vizinhos, o da
esquerda e o da direita, é da mesma classe que eu”. Determinar,
se for possı́vel, de que classe é o morador que abandonou a cidade:
cavalheiro ou mentiroso.
Problema 8. Existem 3 provadores de comida no reino e eles
receberam a informação vinda de um espião que dentre as 7 gar-
rafas de suco que serão servidas na festa do rei na noite seguinte,
exatamente uma delas está envenenada. Além disso, é sabido que:
i) Nenhum provador pode reconhecer a bebida envenenada pelo
sabor, peso ou textura;
ii) Qualquer provador irá passar mal até a noite seguinte se in-
gerir alguma porção, por menor que seja, da bebida envene-
nada.
Determine uma estratégia para que os provadores consigam
determinar a bebida envenenada até a noite do dia seguinte.
Problema 9. Um viajante chegou a uma ilha onde viviam 50
nativos. Todos os nativos formavam um cı́rculo e cada um anun-
ciava primeiro a idade do vizinho da esquerda, depois a idade do
vizinho da direita. Cada nativo é um guerreiro que sempre fala a
verdade ou um patife que sempre aumenta um dos números em 1
e diminui o outro em 1 (de forma aleatória). Após todos falarem
3
dois números, sempre é possı́vel estabelecer quais dos nativos são
guerreiros e quais são patifes?
Problema 10. (OBM 2000) Isabel tem dois baralhos, cada um
com 50 cartas. Em cada um dos baralhos estão escritos os números
de 1 a 100 (em cada carta estão escritos dois números, um em cada
face da carta). Por um defeito de fabricação, a distribuição dos
números nas cartas não é a mesma nos dois baralhos (por exem-
plo, em um dos baralhos o 1 aparece na mesma carta do 2; no
outro, o 1 aparece com o 76). Mostre como Isabel deve fazer para
que, ao colocar as 100 cartas sobre uma mesa, as faces voltadas
para cima mostrem todos os números de 1 a 100.
Problema 11. (OBM 1994) Considere todos os cı́rculos cujas cir-
cunferências passam por três vértices consecutivos de um polı́gono
convexo. Prove que um desses cı́rculos contém todo o polı́gono.
Problema 12. Um grafo tem n vértices, cada um ligado a não
mais do que k outros vértices. Mostre que podemos pintar os
vértices usando k + 1 cores de modo que vértices vizinhos tenham
cores diferentes.