Lista00_Desafios-ResolucaoProblemas[solucao]

Prévia do material em texto

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2019/02
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 00
(Desafios e Resolução de Problemas)
Leitura necessária:
• Não há! O objetivo desta lista é exercitar sua capacidade lógica de resolver problemas, usando apenas
o que você já sabia antes de entrar na universidade!
Exerćıcios.
1. Numa fábrica, 5 máquinas levam 5 minutos para fazer 5 produtos. Quanto tempo 100 máquinas levam
para fazer 100 produtos?
Solução do professor:
• Solução 1. O tempo t necessário para produção é diretamente proporcional ao número p de
produtos desejados e inversamente proporcional ao número m de máquinas à disposição. Logo
t = k
p
m
,
onde k é uma constante. Para determinar o valor de k, vamos usar o fato de que 5 máquinas
produzem 5 produtos em 5 minutos:
5 min = k
5 produtos
5 máquinas
.
Logo k = 5 min ·máquinaproduto .
Agora podemos calcular o tempo para se produzirem 100 produtos utilizando 100 máquinas:
t = 5
min · máquina
produto
· 100 produtos
100 máquinas
= 5 min.
Logo, a resposta final é 5 minutos.
• Solução 2. Divida as 100 máquinas em 20 grupos de 5 máquinas. Cada grupo produz 5 produtos
em 5 minutos. Como há 20 grupos operando em paralelo, no total são produzidos 20 · 5 = 100
produtos em 5 minutos.
2. Responda as seguintes perguntas.
(a) Você tem duas ampulhetas: uma que mede 11 minutos e outra que mede 7 minutos. Você tem
que cozinhar uma verdura durante exatamente 15 minutos. Como você pode usar as ampulhetas
para marcar precisamente os 15 minutos?
1
Solução do professor:
• Solução 1. Você pode seguir os seguintes passos.
i. Vire as duas ampulhetas ao mesmo tempo para iniciar a contagem de tempo nas duas
simultaneamente.
ii. Quando a areia da ampulheta de 7 minutos acabar, comece a cozinhar a verdura.
iii. Quando a areia da ampulheta de 11 minutos acabar, note que terão se passado exatamente
4 minutos desde que o cozimento foi iniciado. Neste momento, vire imediatamente a
ampulheta de 11 minutos para que ela reinicie a contagem de tempo.
iv. Quando a areia da ampulheta de 11 minutos tiver novamente acabado, note que terão
se passado exatamente 4 + 11 = 15 minutos desde que o cozimento se iniciou. Portanto,
neste momento você pode parar o cozimento da verdura.
• Solução 2. Uma alternativa é seguir os seguintes passos.
i. Vire as duas ampulhetas ao mesmo tempo para iniciar a contagem de tempo nas duas
simultaneamente. Ao mesmo tempo, coloque a verdura para cozinhar.
ii. Quando a areia da ampulheta de 7 minutos acabar, note que estarão sobrando exatamente
4 minutos na ampulheta de 11. Neste momento, vire imediatamente a ampulheta de 7
minutos para reiniciar a contagem do tempo nesta ampulheta.
iii. Quando os 4 minutos na ampulheta de 11 minutos tiverem corrido, note que terão se
passado exatamente 7 + 4 = 11 minutos, e restarão 3 minutos na ampulheta de 7 mi-
nutos. Neste momento, vire a ampulheta de 7 minutos novamente, notando que resta o
equivalente a 4 minutos de areia nela.
iv. Quando a areia da ampulheta de 7 minutos acabar novamente, note que terão se passado
mais 4 minutos, totalizando 11 + 4 = 15 minutos desde que o cozimento se iniciou.
Portanto, neste momento você pode parar o cozimento da verdura.
(b) Existe um novo produto para substituir a ampulheta. Ele consiste de um conjunto de varetas
idênticas que queimam de uma ponta a outra em exatamente uma hora. Cada vareta não tem
nem permite marcações intermediárias, e não pode ser cortada ou dobrada. Como você medir
quinze minutos precisamente com duas destas varetas?
Solução do professor: Você pode seguir os seguintes passos.
i. Alinhe as varetas em paralelo, de forma que suas extremidades coincidam.
ii. Simultaneamente, acenda uma vareta por uma extremidade (e.g., a direita) e a outra vareta
pela extremidade oposta (e.g., a esquerda).
iii. Quando o fogo se encontrar, note que terão se passado exatamente 30 minutos e, portanto,
estarão faltando 30 minutos para que o restante de cada vareta seja completamente queimado.
Neste momento eu apague o fogo nas duas varetas.
iv. Alinhe o que sobrou das varetas em paralelo, de forma que as extremidades das partes ainda
não queimadas coincidam.
v. Acenda novamente as partes não queimadas das duas varetas simultaneamente, sendo uma
por uma extremidade e outra pela extremidade oposta.
vi. Quando o fogo se encontrar novamente, note que terão se passado exatamente mais 15 minutos
e, portanto, restarão 15 minutos para que o restante de cada vareta seja completamente
queimado. Apague novamente o fogo das varetas.
vii. Agora o que restou de cada uma das varetas pode medir um tempo de exatamente 15 minutos
quando queimadas. Use qualquer uma das varetas para medir o tempo de cozimento da
verdura.
2
3. Um grupo de 4 pessoas tem que atravessar uma ponte. Cada uma das pessoas no grupo leva um tempo
diferente para atravessar a ponte: 5, 10, 20 ou 25 minutos. A travessia requer iluminação, e podem
passar no máximo 2 pessoas pela ponte de cada vez. O grupo de pessoas dispõe de uma lanterna. Qual
o tempo mı́nimo para a travessia das 4 pessoas?
Solução do professor: Vamos chamar de A o lado da ponte em que as pessoas iniciam, e de B o
lado da ponte em que elas devem terminar. Vamos chamar as pessoas de p5, p10, p20 e p25 de acordo
com o tempo que elas levam para atravessar a ponte. O melhor uso do tempo ocorre quando: (i) os
indiv́ıduos mais lentos atravessam a ponte uma única vez, e (ii) eles o fazem juntos. Uma posśıvel
estratégia para realizar a tarefa é mostrada na Tabela 1. Nesta tabela, cada linha representa uma
etapa da solução, assim como o tempo gasto nesta etapa. Por exemplo, a Etapa 0 indica que no Lado
A da ponte estão todas as pessoas (p5, p10, p20 e p25), enquanto a Etapa 1 indica que as pessoas p5
e p10 atravessam para o Lado B, gastando 10 minutos no processo, enquanto as pessoas p20 e p25
continuam do lado A. Note que o tempo total necessário para a travessia é de 60 minutos.
Etapa
Atravessaram
A→ B
Atravessaram
B → A Lado A Lado B Tempo gasto
0 — —
p5, p10,
p20, p25
— —
1 p5, p10 — p20, p25 p5, p10 10
2 — p5
p5, p20,
p25
p10 5
3 p20, p25 — p5
p10,
p20,p25
25
4 — p10 p5, p10 p20, p25 10
5 p5, p10 — —
p5, p10,
p20, p25
10
Tempo total 60
Tabela 1: Estratégia para atravessar a ponte.
4. Um recenseador bate na porta de uma casa, e uma mulher o atende. Então, o seguinte diálogo se
desenrola:
Recenseador: “Quantos filhos a senhora tem, e qual a idade deles?”
Mulher: “Eu tenho três filhas, a idade delas consiste de números inteiros, e o produto das idades é
36.”
Recenseador: “Esta informação não é suficiente.”
Mulher: “Eu poderia te dizer a soma das idades delas, mas mesmo assim você ainda não saberia as
idades ao certo.”
Recenseador: “Eu gostaria que a senhora me desse mais informações.”
Mulher: “A mais velha das três toca piano.”
Recenseador: “Ok, já sei as idades de suas três filhas!”
Quais são as idades das três filhas?
Solução do professor: O número 36 pode ser fatorado em 22 · 32. Para determinar as posśıveis
idades das três filhas temos que distribuir estes fatores entre as três meninas, lembrando que 1 também
é um fator (não-primo) de 36. De todas as possibilidades para as idades, apenas 2 possuem a mesma
soma, 13, e são, portanto, as únicas que ainda deixariam o recenseador confuso: (a) 6, 6, 1 e (b) 9,
3
2, 2. Como a moradora informou que há uma filha mais velha, a opção (a) não é válida –nesse caso
haveria duas filhas mais velhas, o que contradiz o fato de que a mais velha toca piano– e, portanto, a
resposta correta é a opção (b), sendo a idade das três filhas 9, 2 e 2 anos.
5. Em um torneio eliminatório de tênis, em que os participantes jogam individualmente, o vencedor de
cada partida se classifica para a etapa seguinte, e o perdedor é desclassificado. O vencedor da última
partida é o campeão. Determine o número de partidas em umtorneio com n participantes, em que n
é uma potência de 2.
Solução do professor: Há mais de uma maneira de resolver este problema. A seguir, apresentamos
uma solução longa e trabalhosa (que usa vários conceitos que você aprendeu no Ensino Médio), e uma
solução alternativa extremamente simples que faz uso astuto da lógica e resolve o problema em poucas
linhas e praticamente sem contas. Este é um bom exemplo de como a solução pode ser mais simples
do que parece!
Antes de mais nada, vamos chamar de P o número total de partidas.
• Solução 1 (A mais trabalhosa)
Note que na primeira rodada do torneio haverá n/2 partidas, na segunda rodada haverá n/4, na
terceira haverá n/8, e assim por diante até a rodada final do torneio, que consiste em uma única
partida. (Note que isto vale porque n é uma potência de 2.) Logo
P =
n
2
+
n
4
+
n
8
+ · · ·+ 4 + 2 + 1︸ ︷︷ ︸
k rodadas
.
Note que P é uma progressão geométrica (PG) de k termos, em que o termo inicial é a1 = n/2 e
a razão de progressão é q = 1/2. Para encontrar o número k de termos desta PG, notamos que
o último termo da soma é ak = 1 (pois o torneio termina com um único vencedor). Entretanto,
note que pela definição de termos de uma PG temos que este termo é dado por
ak = a1q
k−1
=
n
2
(
1
2
)k−1
=
n
2k
,
o que implica que n/2k = 1 e, portanto, k = log2 n (note que isto é razoável, porque n é uma
potência de 2 e portanto k será um valor inteiro). Relembrando que a soma dos termos de uma
PG é S = a1(q
k − 1)/(q − 1), obtemos que
P =
n
2
· (1/2)
log2 n − 1
(1/2)− 1
=
n
2
· (2
log2 n)−1 − 1
−1/2
=
n
2
· (n)
−1 − 1
−1/2
= n− 1
Logo, a resposta é que são necessárias n− 1 partidas num torneio de n times.
• Solução 2 (A que usa “simples lógica”)
Note que para que haja 1 campeão ao final do torneio, é necessário que exatamente n− 1 parti-
cipantes tenham sido eliminados. Como cada partida elimina exatamente participante, é preciso
haver exatamente n− 1 partidas no torneio.
4
6. Imagine que há três caixas (bem grandonas!), e exatamente uma delas contém um carro zerinho. Você
pode ficar com o carro se você escolher abrir a caixa certa.
Para te ajudar, cada caixa tem um rótulo, e você sabe que exatamente um rótulo é verdadeiro (e os
outros dois são, portanto, falsos).
• Rótulo da caixa 1: “O carro está nesta caixa.”
• Rótulo da caixa 2: “O carro não está nesta caixa.”
• Rótulo da caixa 3: “O carro não está na caixa 1.”
Em qual caixa está o carro?
Solução do professor: O carro está na caixa 2. Para ver o porquê, note que há apenas três
possibilidades a serem consideradas, das quais duas podemos eliminar por serem inconsistentes:
• O carro está na caixa 1. Nesse caso os rótulos das caixas 1 e 2 seriam ambos verdadeiros, o que
não é permitido pelo enunciado. Logo essa possibilidade deve ser eliminada.
• O carro está na caixa 2. Nesse caso o rótulo das caixa 3 seria o único verdadeiro, o que atende
ao enunciado.
• O carro está na caixa 3. Nesse caso os rótulos das caixas 2 e 3 seriam ambos verdadeiros, o que
não é permitido pelo enunciado. Logo essa possibilidade deve ser eliminada.
7. Três amigos, um dos quais tinha um macaco, compraram uma caixa de biscoitos e decidiram repartir
os biscoitos na manhã seguinte. Durante a noite o primeiro deles acordou e dividiu os biscoitos em três
partes iguais, restando um biscoito que ele deu ao macaco; ele comeu sua parte, devolveu o restante à
caixa e foi dormir. Mais tarde o segundo amigo acordou e, sem saber que alguns dos biscoitos haviam
sido retirados, dividiu os biscoitos em três partes iguais, restando um biscoito após a divisão, o qual
ele deu ao macaco; ele comeu uma das três partes, devolveu o restante à caixa e foi dormir. O mesmo
aconteceu com o terceiro amigo.
De manhã, os três amigos dividiram os biscoitos restantes na caixa em três partes, de novo restando
um biscoito que foi dado ao macaco. Determine o número mı́nimo de biscoitos originalmente na caixa
para que tal divisão seja posśıvel. (Assuma que todas as divisões resultam em um número inteiro de
biscoitos.)
Solução do professor: Vamos chamar de n a quantidade de biscoitos que cada amigo recebeu
pela manhã. Isso significa que no ińıcio da manhã havia m = 3n + 1 biscoitos no pacote (pois os
amigos subtráıram 1 biscoito de m para dar ao macaco, sobrando 3n, e dividiram o resultado por 3,
distribuindo n biscoitos para cada um). Portanto, quando o terceiro amigo acordou, ele encontrou
a3 = 3/2 ·m + 1 biscoitos no pacote (pois o valor de m deve satisfazer m = (a3−1)/3 · 2, uma vez que o
terceiro amigo subtraiu um biscoito de a1 para dar ao macaco, dividiu o restante em 3 partes, comeu
uma partes, e deixou duas partes para a manhã). De forma similar, quando o segundo amigo acordou,
havia a2 = 3/2 · a3 + 1 biscoitos no pacote, e quando o primeiro amigo acordou havia a1 = 3/2 · a2 + 1
biscoitos no pacote. Queremos determinar o valor de a1, que é o total de biscoitos inicialmente contidos
no pacote. Para isso, vamos montar uma tabela e inspecionar qual o menor valor de n que torna posśıvel
que todas as quantidades m, a3, a2 e a1 sejam números inteiros. Por exemplo, quando n = 0 teŕıamos
que m = 1 é inteiro, mas a3 = 3/2 · 1 + 1 = 2.5 não é inteiro e, portanto, esta possibilidade tem que ser
eliminada. O resultado da busca completa encontra-se na Tabela 2, de onde conclúımos que o número
mı́nimo total de biscoitos é 79.
5
n m = 3n + 1 a3 = 3/2 ·m + 1 a2 = 3/2 · a3 + 1 a1 = 3/2 · a2 + 1
0 1 2.5 − −
1 4 7 11.5 −
2 7 11.5 − −
3 10 16 25 38.5
4 13 20.5 − −
5 16 25 38.5 −
6 19 29.5 − −
7 22 34 52 79
Tabela 2: Solução do problema dos biscoitos.
8. Dois companheiros sentaram-se para comer; um deles tinha cinco pães, e o outro, três. Antes de
começarem a comer passou uma mulher que os cumprimentou. Os homens convidaram-na para comer
com eles, repartindo os oito pães, e cada um dos três consumiu quantidades iguais de comida. Antes
de ir embora, a mulher deixou aos dois homens oito moedas (iguais), dizendo que aquilo era pelo que
ele tinha comido. Os dois companheiros se puseram então a discutir como dividir entre eles as oito
moedas. Qual seria uma divisão justa, levando em conta o que tinham e o que comeram?
Solução do professor: Vamos chamar de A o companheiro que tinha inicialmente 5 pães e de B o
companheiro que tinha 3 pães. Cada um dos 3 indiv́ıduos comeu 1/3 · (5 + 3) = 8/3 de pão. A doou
para a mulher a diferença entre o que ele ofereceu e o que ele efetivamente comeu, ou seja, 5− 8/3 = 7/3
de pão. Similarmente, B doou para a mulher 3 − 8/3 = 1/3 de pão. Logo, um total de 7/3 + 1/3 = 8/3
de pão foi doado por A e B juntos (o que é exatamente o que foi comido pela mulher). Como A
contribuiu com (7/3)/(8/3) = 7/8 do total doado, enquanto B contribuiu com (1/3)/(8/3) = 1/8 do total
doado, cabem a A 7 moedas e a B apenas 1.
9. Uma lata contém feijões pretos e brancos. O seguinte processo é repetido tanto quanto se possa:
aleatoriamente são retirados dois feijões da lata; se eles são da mesma cor, ambos são jogados fora
e um feijão preto é colocado na lata (supondo que se dispõe de um suprimento ilimitado de feijões
pretos); se eles são de cor diferente, o feijão preto é jogado fora e o feijão branco é colocado de volta
na lata.
Determine as posśıveis relações entre o conteúdo inicial e o conteúdo final da lata.
Solução do professor: Note o seguinte:
• A cada passo, o total de feijões na lata decresce sempre de 1.
• Feijões brancos só são eliminados aos pares.
• Independentemente do que acontece com os feijões pretos uma hora vão restar exatamente 0
feijões brancos –caso o número inicial de feijões brancos for par– ou exatamente 1 feijão branco
–caso o número inicial de feijões brancos for ı́mpar.
• Caso não reste nenhum feijão branco (ou seja, quando a quantidade de feijões brancos iniciais
for par), a única coisa que pode acontecer éretirar-se um par de feijões pretos e repô-lo com um
único feijão preto. Portanto, necessariamente apenas um feijão preto vai restar na lata ao fim do
processo.
• Caso reste exatamente 1 feijão branco (ou seja, quando a quantidade de feijões brancos iniciais for
ı́mpar), não há mais como eliminar feijões brancos (pois eles só podem ser eliminados em pares).
As únicas opções são, portanto, retirar um par de feijão pretos e substitúı-lo com um único preto
6
(eliminando assim um feijão preto), ou retirar um feijão branco e um preto, e devolver o branco
e jogar o preto fora (eliminando assim também um feijão preto). Portanto, necessariamente ao
final do processo restará apenas um feijão branco.
Logo, se a lata contiver inicialmente um número par de feijões brancos, restará apenas um feijão preto
ao final do processo. Se a lata contiver inicialmente um número ı́mpar de feijões brancos, restará um
único feijão branco ao final do processo.
7