- Thread starter
- #1

- Apr 14, 2013

- 4,008

I am looking at the following problem:

There are $k$ couples and the host and the hostess. (So, in total $k+1$ couples.)

At the general greeting some people shake hands, others do not. Of course, nobody shakes hands with themselves or their spouse.

The host asks everyone else in the room how many people they shook hands with, and recieves $2k+1$ different answers.

How many hands did the hostess shake?

There are in total $2k+2$ people in the room (the guests and the host and the hostess).

Since no one shook his own hand or his spouse's, the largest answer to the host's question is $2k$.

Since he asks $2k+1$ people and gets $2k+1$ different answers, every number from $0$ to $2k$ must be given as answer.

We consider the person who shook $2k$ hands. That means he or she shook everyone's hand except his or her spouse's. So everyone other than the $2k$-shaker's spouse shook at least $1$ hand. The $2k$-shaker's spouse, then, is the only person who shook $0$ hands (because the answer $0$ must be given and this is the only possible person that can shook $0$ hands). Neither the host nor the hostess could have shaken $2k$ hands, because if they did, they would have shaken the $0$-shaker's hand.

Now we ignore the $2k$-shaker and his spouse, the $0$-shaker. So, there are now $k-1=:n$ couples left (among others the host and the hostess) and the host gets $2k+1-2=2(k-1)+1=2n+1$ different answers.

There are now in total $2n+2$ people in the room (the guests and the host and the hostess).

Since no one shook his own hand or his spouse's, the largest answer to the host's question is $2n$.

Since he asks $2n+1$ people and gets $2n+1$ different answers, every number from $0$ to $2n$ must be given as answer.

That means one person (other than the host) shook $2n$ hands, and by the same reasoning as above, neither the host nor his wife could have shaken $2n$ hands.

The problem that we get by ignoring a couple, is identical with the original one.

We continue in that way, by removing from the room the largest hand-shaker and his or her spouse, the smallest hand-shaker, until only the host and his wife remain. As each couple is ejected from the party, we are assured that one of them shook the hands of both the both and his wife, and the other shook the hand of no one who was then at the party, in particular neither the host's nor his wife's hand.

When none of the invited guests remain, i.e. when $k$ couples have left the room, both the host and his wife will have shaken exactly $k$ hands.

How can we solve that with deterministic or non-deterministic machines?