Problem No. 27, 2006

The problem

My two good friends Max and Lars-Göran want to play bridge, but unfortunately they have no opponents. So they decide to play another game instead, which they call "Majority or Minority". This is how it is played: They take an ordinary deck of cards (52 cards; no jokers) and deal the cards just like in bridge. Max and Lars-Göran pick one pile each and look at their 13 cards. Then, they shall deduce if they together hold more spades (at least seven, "majority") than the other two piles, or if it is the opposite (at most six, "minority"). They are not allowed to discuss or look at each other's cards. All they may do is use on of the three possible bids: "I don't know", I know – majority" or "I know – minority".
Max is the dealer and starts the bidding. Fairly quickly he says "I don't know". Lars-Göran, who is just as clever as Max, but not as fast, views his cards carefully and replies "Neither do I". It's Max' turn again, and he only needs two seconds to repeat his previous bid, "I don't know". Lars-Göran removes his glasses, thinks a little longer this time, and finally says "I still don't know". Max lights a cigarette, inhales, looks up and says proudly "But I do!". And then he says one more word ("majority" or "minority").
Max and Lars-Göran are both extremely clever, och neither of them would make an error in the bidding. Now the question is: How many spades did Max have, and what did he say?

Solution

At first it sounds as if the problem can't be solved, but if you realize that any "I don't know" tells something about your hand, it is possible to arrive at a solution with a bit of logical deduction.
Max begins with "I don't know". That means he can't say "minority" or "majority", so we know he has at most six spades. With seven or more, he could have said "majority". But there is no lower limit. Even if he has no spades, he can't say "minority", since it is still possible that Lars-Göran has seven or more spades. Therefore, the first call says: "I, Max, have 0-6 spades".
When Lars-Göran with his first call says "I don't know", we can reason in the same way and realize that he too has at most six spades. But since he also has Max' information to help him (at most six spades), Lars-Göran's first call also says he has at least one spade, since with a void he could have said "minority". Lars-Göran's first call therefore shows 1-6 spades.
When Max still can't say anyting, in spite of his knowing Lars-Göran has 1-6 spades, we know he can't have six ("majority") nor zero ("minority"). He can cut his interval with one in both ends, which means Max now has 1-5 spades.
Just like Max, Lars-Göran still doesn't know. He has neither one spade ("minority") nor six spades ("majority"). So he can, just like Max, cut his interval by one in both ends. So, Lars-Göran has 2-5 spades.
Now Max says "I know". His previous call said he had 1-5 spades. If he has only one, he knows it's minority, since Lars-Göran has at most five. So, there we have the solution to the problem. Do you agree?
Don't! I thought this was it, just like many of the solvers, but the truth is that there is another solution. If Max has five spades, he knows it's a "majority".