Logic Puzzles

Hint:

It is much smaller than you first might think. Try to solve the problem first with one poisoned bottle out of eight total bottles of wine.

Solution:

10 prisoners must sample the wine. Bonus points if you worked out a way to ensure than no more than 8 prisoners die.

Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.

Here is how you would find one poisoned bottle out of eight total bottles of wine.

	1	2	3	4	5	6	7	8
Prisoner A		X		X		X		X
Prisoner B			X	X			X	X
Prisoner C					X	X	X	X

In the above example, if all prisoners die, bottle 8 is bad. If none die, bottle 1 is bad. If A & B dies, bottle 4 is bad.

With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.

Each of the ten prisoners will take a small sip from about 500 bottles. Each sip should take no longer than 15 seconds and should be a very small amount. Small sips not only leave more wine for guests. Small sips also avoid death by alcohol poisoning. As long as each prisoner is administered about a millilitre from each bottle, they will only consume the equivalent of about one bottle of wine each.

Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine. If there are ten prisoners then there are ten more combinations where all but one prisoner must sip from the wine. By avoiding these two types of combinations you can ensure no more than 8 prisoners die.

One viewer felt that this solution was in flagrant contempt of restaurant etiquette. The emperor paid for this wine, so there should be no need to prove to the guests that wine is the same as the label. I am not even sure if ancient wine even came with labels affixed. However, it is true that after leaving the wine open for a day, that this medieval wine will taste more like vinegar than it ever did. C'est la vie.

 

Hint:

To solve this problem, you need to presume that each wise man can count the total number of red hats in front of them without error, that all the wise men have great attention to detail and that all the wise men care about the greater good.

Solution:

99.

You can save about 50% by having everyone guess randomly.

You can save 50% or more if every even person agrees to call out the color of the hat in front of them. That way the person in front knows what color their hat is, and if the person behind also has the same colored hat then both will survive.

So how can 99 people be saved? The first wise man counts all the red hats he can see (Q) and then answers "blue" if the number is odd or "red" if the number is even. Each subsequent wise man keeps track of the number of red hats known to have been saved from behind (X), and counts the number of red hats in front (Y).

If Q was even, and if X&Y are either both even or are both odd, then the wise man would answer blue. Otherwise the wise man would answer red.

If Q was odd, and if X&Y are either both even or are both odd, then the wise man would answer red. Otherwise the wise man would answer blue.

There can be any number of red hats, as the following examples show...

Prisoner	Hat he wears	Number of red hats he sees (Y)		Red hats saved for sure (X)		He says
1	red	6	even (Q)		N/A	red
2	blue	6	even	0	even	blue
3	red	5	odd	0	even	red
4	blue	5	odd	1	odd	blue
5	blue	5	odd	1	odd	blue
6	red	4	even	1	odd	red
7	red	3	odd	2	even	red
8	red	2	even	3	odd	red
9	red	1	odd	4	even	red
10	red	0	even	5	odd	red

Another example might also help, as this puzzle seems to trip up most people...

Prisoner	Hat he wears	Number of red hats he sees (Y)		Red hats saved for sure (X)		He says
1	blue	5	odd (Q)		N/A	blue
2	blue	5	odd	0	even	blue
3	red	4	even	0	even	red
4	blue	4	even	1	odd	blue
5	blue	4	even	1	odd	blue
6	red	3	odd	1	odd	red
7	blue	3	odd	2	even	blue
8	red	2	even	2	even	red
9	red	1	odd	3	odd	red
10	red	0	even	3	odd	red

 

Hint:

The balance tells you which side is heavier and which side is lighter. You can move coins around and get more information this way.

Solution:

3.

If you knew the fake coin was lighter, then the solution would have an easy explanation. But you do not. So....

Number the coins 1 through 12.

1. Weigh coins 1,2,3,4 against coins 5,6,7,8.

1.1. If they balance, then weigh coins 9 and 10 against coins 11 and 8 (we know from the first weighing that 8 is a good coin).

1.1.1. If the second weighing also balances, we know coin 12 (the only one not yet weighed) is the counterfeit. The third weighing indicates whether it is heavy or light. 

1.1.2. If (at the second weighing) coins 11 and 8 are heavier than coins 9 and 10, either 11 is heavy or 9 is light or 10 is light. Weigh 9 against 10. If they balance, 11 is heavy. If they don't balance, you know that either 9 or 10 is light, so the top coin is the fake.

1.1.3 If (at the second weighing) coins 11 and 8 are lighter than coins 9 and 10, either 11 is light or 9 is heavy or 10 is heavy. Weigh 9 against 10. If they balance, 11 is light. If they don't balance, you know that either 9 or 10 is heavy, so the bottom coin is the fake. 

1.2. Now if (at first weighing) the side with coins 5,6,7,8 are heavier than the side with coins 1,2,3,4. This means that either 1,2,3,4 is light or 5,6,7,8 is heavy. Weigh 1,2, and 5 against 3,6, and 9.

1.2.1. If (when we weigh 1,2, and 5 against 3,6 and 9) they balance, it means that either 7 or 8 is heavy or 4 is light. By weighing 7 and 8 we obtain the answer, because if they balance, then 4 has to be light. If 7 and 8 do not balance, then the heavier coin is the counterfeit. 

1.2.2. If (when we weigh 1,2, and 5 against 3,6 and 9) the right side is heavier, then either 6 is heavy or 1 is light or 2 is light. By weighing 1 against 2 the solution is obtained.

1.2.3. If (when we weigh 1,2, and 5 against 3, 6 and 9) the right side is lighter, then either 3 is light or 5 is heavy. By weighing 3 against a good coin the solution is easily arrived at.

1.3 If (at the first weighing) coins 1,2,3,4 are heavier than coins 5,6,7,8 then repeat the previous steps 1.2 through 1.2.3 but switch the numbers of coins 1,2,3,4 with 5,6,7,8.

Hint:

Creating a single loop will only help you identify all the wires by walking 40km. You need to group them in a rather odd matrix.

Solution:

20.

At one end label a wire "A". Then join two wire and label them both "B', then tie three (not already joined) wires together and call them each "C"....continue until all the wires are joined together in groups of 1, 2, 3, 4, 5, etc....for a 120 strand cable. NOTES that the largest group will have 15 wires.

Now walk to the other end.

Using a (battery and light bulb) it is now possible, for example, to find the wire that wasn't joined to any of the others. It is similarly possible to find which wires are in a pair, which is joined in a group of 3, etc. Each time a group is found the technician should label it with the letter for the group, so the single wire is labeled 'a', the pair are each labeled "A", etc....this now matches the other end.....the letters will go up to "O". Now take "A", "B", up to "O" and join them together in a group and label each one with "15", so we have cable "A15", "B15', "C15", up to "O15". Take the second and last "B'"wire and 
join it with a remaining "C", "D", up to "O" and label these each "14' so we have "B14", "C14", up to "O14". Repeat this until at the end there will be a single "O" cabled labeled "O1".

Now walk to the other end.

Now untie all the old connections and identify the group labeled "1", "2", "3" ..."15" at which point each wire at each end has a unique classification.

Alternative solution from citrog:

First, tie the 120 wires together randomly in 60 pairs. Next, go to the far end, randomly label any wire 1, and connect the battery to it. Test which other wire is tied to it at the starting end, and label that wire 2. Then pick another wire other than 1 or 2, label it 3, and tie it to 2, so now the battery is connected to 1, which is tied to 2 at the other end, which is tied to 3 at the end you're at. Now test which wire is tied to 3 at the other end, and label that 4, etc. What you will wind up with is all 120 wires tied to each other in a continuous sequence. Then go back to the end you started at, leaving the battery behind, connected to wire 1. Before you untie all the wires at the starting point, label each wire so that you know which wire was paired with which. Now with all the wires untied at the starting point, test which wire is connected to the battery, and label that 1. Whichever wire was in the same pair as 1, label that 2, and then tie 1 and 2 back together. Now you can find 3, because it's tied to 2 on the far end. Once you find 3, label the wire it was tied to 4, etc. This assumes that the resistance of the wire is small enough that the battery will still light the bulb across 12,000 km of wire.

Hint:

There are only 4 suits, so there will be at least two cards of one suit, one higher and another lower. By careful selection and placement the cards can be used to encode the exact number and suit of the selected card.

Solution:

Pick out two cards of the same suit. Select a card for Alex where adding a number no greater than six will result in the number of the other card of the same suit. Adding one to the Ace would cycle to the beginning again and result in a Two. E.g. if you have a King and a Six of Diamonds, hand the King to Alex. The other three cards will be used to encode a number from 1 through 6. Devise a system with Peter to rank all cards uniquely from 1 to 52 (e.g. the two of hearts is 1, the two of diamonds is fourteen etc...). That will allow you to choose from six combinations, depending on where you put the lowest and highest cards. 

Hint:

Take a long-term perspective. Solve the puzzler for three prisoners.

Solution:

The team nominates a leader. The group agrees upon the following rules:

The leader is the only person who will announce that everyone has visited the switch room. All the prisoners (except for the leader) will flip the first switch up at their very first opportunity, and again on the second opportunity. If the first switch is already up, or they have already flipped the first switch up two times, they will then flip the second switch. Only the leader may flip the first switch down, if the first switch is already down, then the leader will flip the second switch. The leader remembers how many times he has flipped the first switch down. Once the leader has flipped the first switch down 44 times, he announces that all have visited the room.

It does not matter how many times a prisoner has visited the room, in which order the prisoners were sent or even if the first switch was initially up. Once the leader has flipped the switch down 44 times then the leader knows everyone has visited the room. If the switch was initially down, then all 22 prisoners will flip the switch up twice. If the switch was initially up, then there will be one prisoner who only flips the switch up once and the rest will flip it up twice.

The prisoners can not be certain that all have visited the room after the leader flips the switch down 23 times, as the first 12 prisoners plus the leader might be taken to the room 24 times before anyone else is allowed into the room. Because the initial state of the switch might be up, the prisoners must flip the first switch up twice. If they decide to flip it up only once, the leader will not know if he should count to 22 or 23.

In the example of three prisoners, the leader must flip the first switch down three times to be sure all prisoners have visited the room, twice for the two other prisoners and once more in case the switch was initially up.

Hint:

Try to build a question whose answer is predictable even if Random is the one who answers it. One classic trick is to embed one question inside another, e.g. “If I were to ask you X, would you say da?”

Solution:

Label the gods A, B, C in the order they stand. Our first step is to force the answer to ignore Random’s behavior. Let us use the following helper idea.

Key trick — the double question: The expression

“If I were to ask you ‘Is P true?’ would you say da?”

behaves like a normal yes–no question whose answer we can interpret safely. Whatever “da” means, a truthful god will answer da precisely when the embedded proposition P is true, and a lying god will answer da precisely when P is false. Random may still answer arbitrarily, but when Random is not being asked, we are shielded from lies by this device.

---

Step 1. Ask God A:

Q1: “If I were to ask you ‘Are you Random?’ would you say da?”

If A answers da, then either A is True/False and is Random (impossible), or A is Random. Therefore:

• If the answer is da, A is Random.
• If the answer is ja, A is not Random (so Random is either B or C).

We now split on these two possibilities.

Case 1: A is Random (Q1 answered da)

We must determine which of B and C is True. Direct all remaining questions to one of them, say B. Because we are no longer addressing Random, B will respond consistently.

Q2 to B: “If I were to ask you ‘Is C Random?’ would you say da?”

If the reply is da, then C is Random (hence B is either True or False). But we already know A is Random, so this cannot be; therefore the reply must be ja, telling us that C is not Random. Hence C is False and B is True. (The symmetric reasoning works if the other word meanings are swapped.)

Finally, Q3 is unnecessary — we have the gods identified.

Case 2: A is not Random (Q1 answered ja)

So Random is B or C, and A is a consistent god (True or False).

Q2 to A: “If I were to ask you ‘Is B Random?’ would you say da?”

If the answer is da, then (for the same reasons as before) B is Random. If the answer is ja, then B is not Random, so C is Random.

Assume the da answer (B is Random); the other branch is symmetric with B and C swapped.

Now C is a consistent god. Ask C:

Q3 to C: “If I were to ask you ‘Are you True?’ would you say da?”

The answer da identifies C as True (and therefore A as False). The answer ja identifies C as False (and A as True).

---

In every branch we have used no more than three questions and always learn which god is which. Therefore the puzzle is solved.

Hint:

Try making the first orb jumps of decreasing size so that, no matter where it breaks, the total number of drops (first orb so far + second-orb search) is the same.

Solution:

The fewest drops required in the worst case is 14.

Let the first orb be dropped successively from floors spaced 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 floors apart. Concretely, drop it from floors:

14, 27 (14+13), 39 (+12), 50 (+11), 60 (+10), 69 (+9), 77 (+8), 84 (+7), 90 (+6), 95 (+5), 99 (+4), 102 (+3) – but we only need up to floor 100, so stop there. (The final two theoretical steps of +2 and +1 are automatically covered.)

There are two cases:

1. If the first orb never breaks, F = 100 and you have used 14 drops.
2. If it breaks on some floor, suppose it broke on the k-th drop. At that moment you have used k drops, and you know the highest safe floor lies between the previous safe floor and the current one – an interval whose length is at most 14 − k. Now use the second orb to test each floor within that interval sequentially from the bottom up. In the worst case this costs another 14 − k drops, bringing the total to k + (14 − k) = 14.

Thus, no matter where the critical floor lies, you will never exceed 14 drops.

Why 14 is optimal
The sum 14 + 13 + ⋯ + 1 = 105 ≥ 100 guarantees every floor is reachable in at most 14 drops. If you tried to finish in only 13 drops, the maximum number of distinct outcomes (the 13 triangular number) would cover at most 91 floors, insufficient for 100. Therefore 14 is the minimum possible.

Solution:

The young man could say, 'If you do not let me marry your daughter, I will be put to death.' If the Sultan chooses to give him the diamonds or the genie, the statement becomes true, and he must be executed, creating a paradox. Therefore, the only resolution is for the Sultan to give him Arlena's hand in marriage.

Solution:

Separate the cards into two piles: one with 13 cards and the other with 39 cards. Flip all the cards in the pile of 13. This way, if the pile of 39 has x face-up cards, the pile of 13 will have 13-x face-up cards, and flipping it will result in both piles having x face-up cards.

Solution:

Each dwarf will observe the number of red dots on the backs of the other dwarfs. If a dwarf sees Y red dots, they will assume that the total number of red dots, X, is either Y (if their own dot is blue) or Y + 1 (if their own dot is red). Therefore, they will wait for X days. If no one gathers after Y days, it indicates that they must have a red dot themselves, and they will gather on the Xth day. This way, all dwarfs with red dots will gather at the correct time.

Hint:

Think of the problem backwards: if you are allowed at most k drops and still have b balls left, how many floors can you distinguish between? Work out a recurrence for that quantity.

Solution:

Let T(b, r) be the maximum number of floors that can be resolved using b balls and at most r remaining drops. One final drop either leaves the ball intact (so we can still use b balls and now have r − 1 drops) or breaks it (leaving b − 1 balls and r − 1 drops). Hence

T(b, r) = 1 + T(b, r − 1) + T(b − 1, r − 1),  with  T(0, r) = 0,  T(b, 0) = 0.

Solving this recurrence gives

T(b, r) = \(\displaystyle \sum_{i=0}^{b} \binom{r}{i}\).

Therefore, if we are allowed r drops we can cope with at most \(\sum_{i=0}^{m} \binom{r}{i}\) floors. Conversely, the minimum worst-case number of drops, call it k, is the smallest integer satisfying

\(\displaystyle \sum_{i=0}^{m} \binom{k}{i} \;\ge\; n.\)

Strategy (constructive): keep two counters, b (balls left, initially m) and r (drops left, initially k). After having already proved safe the highest floor saf, compute

step = 1 + \(\displaystyle \sum_{i=0}^{b-1} \binom{r-1}{i}\).

Move up step floors from saf and drop a ball there.

• If it breaks, set b ← b − 1; if it survives, set saf to that floor. In both cases set r ← r − 1 and repeat until either all floors are resolved or no balls remain.

This procedure guarantees that no matter how the drops turn out we will never require more than k drops, and k is the smallest number for which such a guarantee is possible. Hence the puzzle’s answer is:

Minimum worst-case drops = smallest k with \(\sum_{i=0}^{m} \binom{k}{i} \ge n.\)

Examples:

• m = 1 (one ball): need k = n drops → linear search.
• m = 2, n = 100: smallest k is 14 (since 14·15/2 = 105 ≥ 100).

Thus the presented strategy is optimal.

Solution:

The prisoners can use the parity of the number of heads on the chessboard to communicate the indicated square. They agree that if the indicated square is (x, y) and the total number of heads is even, prisoner A will flip the coin at (x, y) to tails; if odd, he will leave it as is. Prisoner B can then determine the indicated square based on the parity of heads after A's action. This strategy can be extended to larger boards, but the patterns may become more complex.

Solution:

The prisoners can use the parity of the number of red hats they see in front of them to communicate. The last prisoner in line counts the number of red hats in front of him and announces 'red' if the count is odd and 'blue' if it is even. Each subsequent prisoner can then deduce their own hat color based on the previous guesses and the number of red hats they see, allowing at least 29 prisoners to be freed with certainty.

Solution:

The prisoners can agree beforehand to use the sum of the visible numbers modulo 100 as a strategy. Each prisoner will calculate the total of the numbers they see, take that total modulo 100, and then subtract it from the expected total if they could see their own number. This way, each prisoner can deduce their own number based on the others' hats, maximizing the chances of at least one correct guess. Additionally, if the prisoners have a way to communicate their guesses, they can use the first guess to relay information to help others deduce their own numbers.

Solution:

The prisoners designate one as the 'leader' (or 'counter') and the others as 'visitors.' Each visitor will turn the lamp on the first time they enter the room if it is off, and they will not touch the lamp again after that. The leader will switch the lamp off if it is on, or do nothing if it is off. The leader counts how many times they have switched the lamp off. Once the leader has switched off the lamp 99 times, they can confidently declare that all prisoners have visited the room at least once. This strategy assumes the lamp starts in the off position; if the initial state is unknown, the logic remains similar but requires adjustment in the counting method.

Solution:

The prisoners can use a strategy based on the numbers associated with their names. Each prisoner starts by opening the box with their own number. If they find their name, they succeed; if not, they take the number found in that box and open the box with that number. They repeat this process for up to 50 boxes. This strategy leverages the structure of permutations, forming chains of boxes that lead back to the starting box. If the chain is shorter than 50 boxes, the prisoner will find their name within the limit. The probability of success, based on the random arrangement of names in the boxes, is approximately 31.8%, as no chains exceed 50 boxes in length.

Hint:

Consider the implications of your statement being true or false.

Solution:

You should say, "You will boil me in oil." If this statement is true, they must burn you at the stake, which makes it false. If it is false, they must boil you in oil, which makes it true. Therefore, they cannot carry out either punishment and must let you go.

Hint:

Consider asking a question that reveals the truth regardless of whom you are asking.

Solution:

He should ask either of them, 'If I were to ask the other one which way leads to heaven, what would he say?' Then he should take the opposite path.

Solution: The tactic is:

Each dwarf counts how many red dots he can see on the others. Call that number r.

Then he follows this rule:

“If nobody has gone to the meeting point before, I will go on day r + 1.”

Why it works, assuming everyone publicly knows there is at least one red dot:

Day 1:
A red dwarf who sees 0 red dots knows he must be the only red. So he goes on day 1.

Day 2:
If there are 2 red dwarfs, each sees 1 red. Each thinks: “Maybe I am blue, and the other red dwarf sees 0 red dots. If so, he would go on day 1.” Nobody goes on day 1, so each realizes: “I must also be red.” Both go on day 2.

Day 3:
If there are 3 red dwarfs, each sees 2 red. Each thinks: “If I am blue, those 2 red dwarfs would figure it out and go on day 2.” Nobody goes on day 2, so each realizes he is red. All 3 go on day 3.

And so on.

So if there are X red dwarfs, each red dwarf sees X − 1 red dots, waits through the first X − 1 days, then goes on day X.

Blue dwarfs see X red dots, so their rule would make them wait until day X + 1. But the red dwarfs already correctly gather on day X, so the game is solved.

Important catch: if the dwarfs are not told that at least one red dot exists, the puzzle is impossible. A lone red dwarf seeing zero red dots cannot distinguish “I am red” from “everyone is blue.”

Solution:

The promise is impossible: with random, independent selection, the numbers of visits almost surely never all tie, so the warden cannot ever make each prisoner visit the switch room the same number of times.