Handshake Problem - Machines

[mathmari]

Hey!

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 receives $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? (Wondering)

 

[Wilmer]

Soooo...if c couples, then n = 2c = number of people

If everybody shakes hands with everyone except wife,
then there are n(n - 2) / 2 total handshakes.

Example: 3 couples; then n = 6
6(6 - 2) / 2 = 12 handshakes

The 3 couples (odd = husband!, even = wife):
(1,2),(3,4),(5,6)

Handshakes:
(1,3)(1,4)(1,5)(1,6)
(2,3)(2,4)(2,5)(2,6)
(3,5)(3,6)
(4,5)(4,6)
= 12 handshakes

35 couples:
70*68/2 = 2380 handshakes ...party's over!

Have I got that correct?

 

[I like Serena]

Hey mathmari!

If I understand correctly, we're looking for a deterministic or non-deterministic machine that reads $k$ and that outputs $k$, don't we? (Thinking)

 

[mathmari]

Soooo...if c couples, then n = 2c = number of people

If everybody shakes hands with everyone except wife,
then there are n(n - 2) / 2 total handshakes.

Example: 3 couples; then n = 6
6(6 - 2) / 2 = 12 handshakes

The 3 couples (odd = husband!, even = wife):
(1,2),(3,4),(5,6)

Handshakes:
(1,3)(1,4)(1,5)(1,6)
(2,3)(2,4)(2,5)(2,6)
(3,5)(3,6)
(4,5)(4,6)
= 12 handshakes

35 couples:
70*68/2 = 2380 handshakes ...party's over!

Have I got that correct?

You mean that the number of different possible handshakes is $\frac{n\cdot (n-1)}{2}$ ? Then yes!

But in this case we are asked about the handshakes of the hostess. (Thinking)

If I understand correctly, we're looking for a deterministic or non-deterministic machine that reads $k$ and that outputs $k$, don't we? (Thinking)

I think so (Thinking)

Could you give me a hint how such a machine works? (Wondering)

 

[I like Serena]

I think so

Could you give me a hint how such a machine works?

Suppose we have a deterministic machine with a single state, which is both the initial and the final state.
And for each symbol we have state transition that reads the symbol, and that outputs the symbol.
That would do the job, wouldn't it? (Thinking)

 

[Wilmer]

You mean that the number of different possible handshakes is $\frac{n\cdot (n-1)}{2}$ ? Then yes!

But in this case we are asked about the handshakes of the hostess. (Thinking)

I was asking "in general"; not related to your question.

I don't agree with your n(n-1)/2; isn't it n(n-2)/2)?
Everybody shakes hands, except a husband and his wife:

Take 1 couple ; n=2: 2(2-2)/2 = 0 handshakes
Take 2 couples; n=4: 4(4-2)/2 = 4 handshakes