Logica Computacional_Lista 00

Prévia do material em texto

Logica Computacional / Lista 00 
 
Aluna: Franciely Santos Mota 
Matricula: 2020205434 
 
Exercícios: 
1. Numa fábrica, cinco máquinas levam 5 minutos para fazer cinco produtos. Quantos 
tempos 100 máquinas levam para fazer 100 produtos? 
 
 
2. Respondam 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? 
R: Assim que ampulheta de 7 minutos chegar ao fim, vire-a para iniciar novamente, no momento que 
a ampulheta de 11 minutos chegar ao fim terá se passado 4 minutos na ampulheta de 7 minutos, então, 
vire novamente a ampulheta de 7 minutos para somar mais 4 minutos aos 11 minutos já transcorridos. 
 
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? 
R: Alinho as varetas em paralelo, de forma que suas extremidades coincidam. Simultaneamente, acendo 
uma vareta por uma extremidade (e.g., a direita) e a outra vareta pela extremidade oposta (e.g., a 
esquerda). Quando o fogo se encontrar, passaram-se exatamente 30 minutos e, portanto, faltam 30 
minutos para que o restante de cada vareta seja completamente queimado. Neste momento eu apago o 
fogo. Alinho novamente as varetas em paralelo, de forma que as extremidades das partes n˜ao 
queimadas coincidam. Novamente, acendo as duas varetas simultaneamente, sendo uma por uma 
extremidade e outra pela extremidade oposta. Quando o fogo se encontrar, passaram-se exatamente 15 
minutos e, portanto, faltam 15 minutos para que o restante de cada vareta seja completamente 
queimado. Apago então, o fogo. Agora cada uma das varetas pode medir um tempo de exatamente 15 
minutos quando queimadas. Uso qualquer uma das varetas para medir o tempo de cozimento da 
verdura. 
 
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? 
R: 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: os indivıduos mais lentos atravessam a 
ponte uma unica vez, e eles o fazem junto. Uma possıvel estrategia para realizar a tarefa é 
mostrada na Tabela 1. Nesta tabela, cada linha representa uma etapa da solução, assim como o 
tempo gasto. Por exemplo, a Etapa 0 indica que no Lado A da ponte estao 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. 
 
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? 
R: O numero 36 pode ser fatorado em 2 (elevado) 2 · 3 (elevado) 2 . Para determinar as poss´ıveis idades 
das tres filhas temos que distribuir estes fatores entre as tres meninas, lembrando que 1 tambem é um 
fator (nao-primo) de 36. De todas as possibilidades para as idades, apenas 2 possuem a mesma soma, 
13, e sao, portanto, as unicas que ainda deixariam o recenseador confuso: (a) 6, 6, 1 e (b) 9, 2, 2. Como a 
moradora informou que ha uma filha mais velha, a opção (a) nao é valida nesse caso haveria duas filhas 
mais velhas, o que contradiz o fato de que a mais velha toca piano e, portanto, a resposta correta 9, 2, 2. 
 
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 um torneio com n participantes, em que n é uma potência de 
2. 
R: Ao final do torneio, havera n − 1 times eliminados. Como cada partida elimina um, e exatamente um, 
time, é preciso haver n − 1 partidas para que um campeão seja decidido. 
 
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? 
R: Se o carro estivesse na Caixa 1, as frases que acompanham as Caixas 2 e 3 deveriam ser falsas, já que 
a primeira delas afirma exatamente o que estamos propondo. Porém, a frase da Caixa 2 também seria 
verdadeira, já que o carro realmente não estaria ali dentro. Dessa forma, as duas frases estariam 
corretas, o que quer dizer que o carro não pode estar na Caixa 1. Como a sentença da Caixa 3 também 
fala à respeito do conteúdo da Caixa 1, vamos partir diretamente para ela. Se o carro estivesse dentro 
da Caixa 3, isso faria com que as frases das Caixas 2 e 3 fossem verdadeiras, o que também vai contra as 
regras do nosso desafio e invalida essa caixa como opção para resposta correta. Assim, se as Caixas 1 e 3 
não podem conter a nossa solução, isso dignifica que só nos resta a Caixa 2 Colocando o carro na Caixa 
2, a única sentença verdadeira seria aquela relacionada com a Caixa 1, que realmente não teria o carro. 
A Caixa 1, que defende ter o carro, estaria mentindo, assim como a Caixa 2, que guardaria o veículo 
mesmo afirmando o contrário. O carro está na caixa 2! 
 
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. 
R: N é a quantidade de biscoitos que cada amigo recebeu pela manhã. Isso significa que de manhã havia 
m = 3n + 1 biscoitos no pacote (pois os amigos subtrairam 1 biscoito de m para dar ao macaco, sobrando 
3n, e dividiram o resultado por 3, dando n 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 4 biscoito de a1 para dar ao macaco, dividiu o restante em 3 
partes, comeu uma partes, e deixou duas partes para a manh˜a). 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 menorvalor 
de n que torna possıvel que todas as quantidades m, a3, a2 e a1 sejam números inteiros. O resultado 
encontra-se na Tabela 2, de onde concluimos que o número mınimo total de biscoitos é 79. 
 
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? 
R: Chamar de A o companheiro que tinha inicialmente 5 paes 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˜ao. A doou para o homem a diferen¸ca 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 o homem 3 − 8/3 = 1/3 de pão. Logo, um total de 7/3 + 1/3 = 8/3 de pao foi doado por A e B juntos 
(o que é exatamente o que foi comido pelo terceiro homem). 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 possíveis relações entre o conteúdo inicial e o conteúdo final da lata. 
R: A cada passo, o total de feijões na lata decresce em 1. 
Feijões brancos so 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 numero inicial de feijões brancos for par—ou exatamente 1 feijão branco— caso o 
numero inicial de feijões brancos for ımpar. 
Caso não reste nenhum feijão branco, a unica coisa que pode acontecer é retirar-se um par de feijões 
pretos e repo-lo com um unico 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, nao ha mais como eliminar feijões brancos (pois eles so podem 
ser eliminados em pares). As unicas opções são, portanto, retirar um par de feijões pretos e substituı-lo 
com um unico preto (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 restara 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. 
Logo, se a lata contiver inicialmente um número par de feijões brancos, restara apenas um feijão preto 
ao final do processo. Se a lata contiver inicialmente um numero ımpar de feijões brancos, restara um 
unico feijão branco ao final do processo.