A logician has a favorite game to play at parties. He shows a set of solidly colored stickers to all his logician friends. Each logician, without looking, puts a random sticker on his/her own back. Each logician can only see the stickers on other people's backs, and no one can look at the unused stickers. The logicians take turns announcing whether they can deduce their own color. The game ends when someone announces he/she can deduce his/her own color.
One time while playing this game, no one had yet ended the game even though everyone had a turn. Should they continue to take second turns, or should they just give up and start a new game? Prove that it is impossible for a game that hasn't ended after everyone's first turn to ever end, or provide a counterexample.
(In reply to
Proof: by Eddy Karat)
Definitions:
A game consists of a positive number of people k and a set of positive
numbers {N1, ... , Nn} that represent the number of stickers of each
color. (The exact colors do not matter. A game with 2 red and 1 blue
sticker is the same game as 2 blue and 1 red sticker.) The total
number of stickers N=N1+...+Nn must be greater than or equal to the
number of players k in order to form a valid game.
A setup is a mapping of players to stickers with no two players being
given the same sticker, and an order for the players to guess. If a
player is mapped to a sticker, that sticker is "assigned" to that
player. If no player is given a particular sticker, that sticker is
unassigned.
A player can "guess" only when he can deduce rationally what sticker he has.
Otherwise, that player "passes."
An unguessable game is a game where no player can ever guess what color
he has, no matter what the setup.
A round is where each of the players gets a turn in order.
Lemma: If there is no hypothetical setup for a game in which the first
player can guess what color sticker he has, then the game is unguessable.
Proof: If there is no setup where the first player can guess, the second
player knows that the first player will pass -- the second player
gets no information from the first player's move. Therefore, the second
player acts as if he were the first player, but we know that the first player
can never guess by assumption, so the second cannot either. This inducts over
all the players, so the game is unguessable.
Corollary: A game with k players and n stickers must have a color
with at least n-k+1 stickers or it is unguessable.
Proof: For the first player to guess, he must see all the stickers
that are not of a particular color. Since he sees k-1 stickers, in
order to guess there must be a color such that there are at most k-1
stickers not of that color. Since there are n total stickers, there
are at least n-k+1 stickers of that color.
Theorem to prove:
If a game is not unguessable by the Corollary above, then at least
one of the players can guess his color by his turn in the first round.
Proof:
Let us look at all games {#, #, #, ...} that are not unguessable by
the corollary above. Call the most numerous sticker blue and count
the number of not-blue stickers. Say there are x > 0 blue stickers and y >= 0
not-blue stickers. The corollary says that x >= x+y-k+1 (equivalently
k >= y+1). Let us induct on k, the number of players:
k=1 player: y <=0, so there is only 1 color sticker.
The first player can guess without additional information.
Now assume that the proposition holds for all k-1 player games and y-1 not-blue
stickers for (k-1) >= (y-1)+1 -> k >= y+1.
Consider the k player game with y not-blue stickers with k > 2 and k >= y+1
The first player knows that there are only y not-blue stickers
assigned to all the players. If all y not-blue stickers are assigned
to players other than the first (this includes the case y=0), then the
first player knows he is blue and guesses blue. Otherwise, depending
on additional information, the first player may or may not be able to
figure it out. If he does, then it was guessed in the first round and
we are done. So, let us consider the case where the first player
passes. All other players know that there are at most y-1 not-blue
stickers assigned to players other than the first. All other players
can see the first player's sticker. So, we have reduced the problem
down to the game with y-1 not-blue stickers and k-1 people. Since
k >= y+1 -> (k-1) >= (y-1)+1, one of the remaining players can guess
this game in the first round.
Proof:
