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.
"The game ends when someone announces he/she can deduce his/her own color."
a terribly silly counterexample would be one where i just ask another
person what color is on my back. "i deduce by so-and-so's answer
that the colour on my back is xxx." but since it's their
favourite game, i'm guessing they wouldn't do that ... it'd get boring
if every game was played out like that. any given game can be
ended that way in a worst case scenario.
another silly counterexample would be one where there are x number of
players and x+y number of stickers. since you can see all the
other players' stickers, you're only left with (x-1)+y guesses.
if we can assume that all players have perfect photographic memory,
then it would depend on the number y.
if y is large, but variety is little (example: all blue, except for
one, or a few, red), then it's possible to end the game in a few
turns. if y is large, and variety also (example: take one of
those paint sample books and cut out all the colour in the spectrum),
then it's probably impossible to begin with, except in the method
above. since it's their favourite game, it would probably mean
they wouldn't mind playing it over and over, so they can probably name
all the colours in play.
if y is little, then it would not be hard to guess.
y would not be zero, as this is their favourite game (replay value),
and it would be too simple for logicians to announce they can deduce it
in the first turn.
since it's their favourite game, however, i would rule out large y with
large variety. also, these are logicians playing. they would
probably not want to guess and just give the correct answer the first
try.
my question with this problem is this: what if you get it
wrong? the rules state that the game ends when someone announces
he/she can deduce his/her own colour. i mean, anyone can do that
at any time; it's just a matter of whether they are correct or
not. what if they are incorrect? does the game end?
are they penalized? does it keep going?
pardon a rambling novice; it's early and the coffee hasn't kicked in yet.
maybe i'm just being silly
