MHB How Many Handshakes Did the Hostess Make at the Party?

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Machines
AI Thread Summary
The discussion revolves around a mathematical problem involving handshakes at a party with k couples and a host and hostess. Each person shakes hands with others, excluding themselves and their spouse, leading to 2k+1 unique handshake counts reported to the host. The analysis reveals that the hostess must have shaken hands with exactly k people, as the pattern of handshakes eliminates other possibilities. The conversation also touches on the calculation of total handshakes and the mechanics of deterministic and non-deterministic machines in relation to the problem. Ultimately, the conclusion is that the hostess's handshake count is directly linked to the number of couples present.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
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?
 
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)
 
Wilmer said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
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)
 
mathmari said:
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
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top