A king has a daughter and wants to choose the man she will marry.  There are three suitors from whom to choose, a Knight, a Knave, and a Commoner.  The king wants to avoid choosing the Commoner as the bridegroom, but he does not know which man is which.  All the king knows is that the Knight always speaks the truth, the Knave always lies, and the Commoner can do either.  The king will ask each man one yes/no question, and will then choose who gets to marry the princess.  What question should the king ask and how should he choose the bridegroom?

A followup question:

Suppose the three suitors know each other (an assumption that’s not needed in the original problem).  Then find a new strategy for the king where the king only needs to ask a question of any two of the three suitors in order to pick the bridegroom.

In this problem, you and a partner are to come up with a scheme for communicating the value of a hidden card.  The game is played as follows:

• Your partner is sent out of the room.
• A dealer hands you 5 cards from a standard 52 card deck.
• You look at the cards, and hand them back to the dealer, one by one, in whatever order you choose.
• The dealer takes the first card that you hand her and places it, face up, in a spot labeled “0”‘.  The next three cards that you hand her, she places, similarly, in spots labeled “1”, “2”, and “3”.  The last card that you hand her goes, face down, in a spot labeled “hidden”.  (While you control the order of the cards, you have no control over their orientations, sitting in their spots; so you can’t use orientation to transmit information to your partner.)
• Your partner enters the room, looks at the four face-up cards and the spots in which they lie and, from that information (and your previously-agreed-upon game plan), determines the suit and value of the hidden card.

Question: What is the foolproof scheme that you and your partner settled on ahead of time?

As a follow-up question, consider the same problem but with a 124-card deck.

You’re an electrician working at a mountain.  There are N wires running from one side of the mountain to the other.  The problem is that the wires are not labeled, so you just see N wire ends on each side of the mountain.  Your job is to match these ends (say, by labeling the two ends of each
wire in the same way).

In order to figure out the matching, you can twist together wire ends, thus electrically connecting the wires.  You can twist as many wire ends as you want, into as many clusters as you want, at the side of the mountain where you happen to be at the time.  You can also untwist the wire ends at the side of the mountain where you’re at.  You are equipped with an Ohm meter, which lets you test the connectivity of any pair of wires.  (Actually, it’s an abstract Ohm meter, in that it only tells you whether or not two things are connected, not the exact resistance.)

You are not charged [no pun intended] for twisting, untwisting, and using the Ohm meter.  You are only charged for each helicopter ride you make from one side of the mountain to the other.  What is the best way to match the wires?  (Oh, N>2, for there is no solution when N=2.)

Given N points randomly distributed around the circumference of a circle, what is the probability that all N points lie on the same semi-circle?

In a finite, undirected, connected graph, an integer variable v(n) is associated with each node n.  One node is distinguished as the anchor.  An operation OP(n) is defined on nodes:

OP(n):
if node n is the anchor, then do nothing,
else set v(n) to the value 1 + min{v(m)}, where m ranges over all neighbors of n that are distinct from n.

An infinite sequence of operations <OP(n),OP(m), …> is executed, the node arguments n, m, … for the operations being chosen arbitrarily and not necessarily fairly.  Show that eventually all v(n) stabilize.  That is, that after some finite prefix of the infinite sequence of operations, no further operation changes v(n) for any node n.

A square table has a coin at each corner.  Design an execution sequence, each of whose steps consists of one of the following operations:

• ONE:  The operation chooses a coin (possibly a different one with each execution of the operation) and flips it.
• SIDE:  The operation chooses a side of the table and flips the two coins along that side.
• DIAG:  The operation chooses a diagonal of the table and flips the two coins along that diagonal.

such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.

N prisoners get together to decide on a strategy.  Then, each prisoner is taken to his own isolated cell.  A prison guard goes to a cell and takes its prisoner to a room where there is a switch.  The switch can either be up or down.  The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.  The prisoner is then taken back to his cell.  The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners.  That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”.  If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.  What strategy should the prisoners use to ensure their eventual freedom?

(Just in case there’s any confusion:  The initial state of the switch is unknown to the prisoners.  The state of the switch is changed only by the prisoners.)

As a warm-up, you may consider the same problem but with a known initial state of the switch.

100 persons are standing in line, each facing the same way.  Each person is wearing a hat, either red or blue, but the hat color is not known to the person wearing the hat.  In fact, a person knows the hat color only of those persons standing ahead of him in line.

Starting from the back of the line (that is, with the person who can see the hat colors of all of other 99 persons), in order, and ending with the person at the head of the line (that is, with the person who can see the hat color of no one), each person exclaims either “red” or “blue”.  These exclamations can be heard by all.  Once everyone has spoken, a score is calculated, equal to the number of persons whose exclamation accurately describes their own hat color.

What strategy should the 100 persons use in order to get as high a score as possible, regardless of how the hat colors are assigned?  (That is, what strategy achieves the best worst-case score?)

For example, if everyone exclaims “red”, the worst-case score is 0.  If the first 99 persons exclaim the color of the hat of the person at the head of the line and the person at the head of the line then exclaims the color he has heard, the worst-case score is 1.  If every other person exclaims the hat color of the person immediate in front and that person then repeats the color he has just heard, then the worst-case score is 50.  Can you do better?

Hint: Instead of using just red and blue as the possible hat colors and exclamations, use N different colors.