Puzzles: Set 6
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9

Given the head of a linked list, find if it contains a loop or not, in linear time. Can you accomplish it with only O(1) extra space? Can you do it without modifying the list in any way?
Solution
Perplexing Polynomial

Alice is allowed to choose an arbitrary polynomial p(x) of any degree with nonnegative integer coefficients. Bob can infer the coefficients of p(x) by only two evaluations as follows. He chooses a real number a and Alice communicates p(a) to him. He then chooses a real number b and Alice communicates p(b) to him. What values of a and b helped Bob succeed and how?
Solution
Poisoned Wine Barrels

An enemy spy has poisoned one out of 1000 barrels of wine in a king's cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel?
Solution
Two Eggs and a Building

With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped? Followup: What if the number of floors of the building is unknown?
Solution
Number Guessing Game

Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar's chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number?
Solution
Cutting a Cake with Icing

One day, grandma baked a cake with a square top and dimensions 30cm x 30cm x 10cm. What is a simple strategy for cutting the cake into 9 equal pieces? The next day, grandma baked another cake with the same dimensions. This time, she put a thin layer of icing on top and on all four sides but not on the bottom. What is a simple strategy for cutting such a cake into 9 pieces such that all pieces have the same amount of cake by volume and the same amount of icing by surface area?
Solution
Number Guessing Game II

Shankar chooses a number uniformly at random between 1 and 1000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. If Geeta's guess is larger than the number, Shankar replaces the number with another number chosen uniformly at random [1, 1000]. What should Geeta's strategy be?
Solution
Cube Cutting with Stacking

How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids.
Solution
What's the Number on My Hat?

A goblin forewarns N gnomes as follows: "Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free." The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy?
Solution
Tiling a Chessboard with Dominoes

(A) An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2x1 rectangles (dominoes) such that all squares are covered?

(B) Under what circumstances would removal of two squares from an 8x8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black square, can the remaining board be tiled?

(C) A hospital has 16 isolation rooms. Patient 13 is cured. He wants to pass by all other patients before leaving but he can't see the same patient twice or he will get sick again. Is that possible?

[Also known as 'Patient in Room 13 Puzzle' or 'Quarantine Puzzle'; it surfaced in 2020 after Covid-19 caught us by surprise.]

(D) In the above puzzle, imagine that we have a helicopter in one of the squares to bail us out of the hospital (instead of a door as suggested by the red arrow above). Is there a room such that if the helicopter were in that room, the puzzle would be impossible to solve?

Solution