Puzzles: Set 7
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Five Card Trick

A mathemagician asks a volunteer to give him five cards drawn from a pack of fifty-two. He hands one card back to the volunteer and arranges the remaining four in some sequence he chooses. He then hands the sequence to a second volunteer and leaves the room. His assistant enters. The assistant asks the second volunteer to read out aloud the sequence handed to him. The assistant ponders a little and correctly announces the identity of the card held by the first volunteer. How could this be done? In general, how large a deck of cards can be handled if n cards are drawn initially?
Sum and Product

P is told the product of two integers chosen from [2, 99] and S is told the sum. The following dialogue ensues:

(1) P says, "I do not know the two integers."

(2) S replies, "I knew that already."

(3) P exclaims, "Ah! I now know the two numbers.",

(4) S smugly replies, "Now I know them too."

What are the two numbers?

Fast Bit Counting

Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer?
Empty the Bucket

Three buckets have marbles. You are allowed to double the number of marbles in a bucket by borrowing from one of the other two buckets. Prove that it is possible to produce an empty bucket with a series of such operations.
Balanced Coloring

Given k arbitrary points in a grid of size m by n, is it always possible to color them either red or black such that each row and each column is balanced? A row or column is said to be balanced if the difference in the number of red and black points in it is at most one.
Horses on Auction

You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. You are a connoiseur of horses, and can judge whether one horse is 'better' than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?
Polya's Urn Process

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the urn with fewer balls?
Flipping Bits in a Matrix

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?
Rectangle with Integer Side

A big rectangle is composed of smaller non-overlapping rectangles, each having integer width or integer height or both. Prove that the big rectangle enjoys the same property.
100 Prisoners and 100 Boxes

A room has 100 boxes labeled 1 thru 100. The names of 100 prisoners have been placed in these boxes by the warden. The prisoners shall visit the room one by one. Each prisoner is allowed to inspect the contents of at most 50 boxes, one after the other and leave the room with no communication with other prisoners. If the prisoner discovers his own name in the boxes he inspects, he is released. The prisoners are allowed to collude before hand and devise a strategy to maximize the chances of releasing each and every prisoner. What is their strategy?