Handshake Problem?

Question

At a given party there are n different couples. At this particular party, some people shake other peoples’ hands. No one shakes their own hand, and no one shakes his or her spouse’s hand. After
all the handshaking is said and done, Bob asks the other people at the party how many different peoples’ hands they shook. Strangely, he gets a different answer from every person. Prove by
induction that Bob’s wife, Alice, shakes exactly n hands.

Answer 1

For this to work I think you need Bob and his wife to invite over n couples (so that there are 2n+2 people total), and you need that all 2n+1 people except Bob's wife shook a different number of hands. Now if this is the case, I believe we can show that Alice shook exactly n hands.

Base case:
0 couples are invited (so it is just Bob and his wife). They each shook 0 hands.

Now assume this is true if k-1 couples (other than Bob and his wife) are invited. When need to prove Alice shakes k hands if k couples are invited. If k couples were invited (so counting Bob and his wife there are 2k+2 people), then the number of handshakes is between 0 and 2k. So, considering all the people except Alice, there are 2k+1 people and 2k+1 possible numbers of handshakes so each number of handshakes must have happened. So there is someone who shook 2n hands and someone who shook 0 hands. They must be a couple, since the person who shook 2n hands, must have shaken all hands except his spouse.

But suppose that couple did not come to the party, then everyone else would have shaken one fewer hand. Thus all except Alice would have shaken a distinct number of hands, thus by our inductive assumption, Alice would have shaken k-1 hands. But, since they did come to the party, Alice shook one additional hand, thus she shook k hands.

So we have proven by induction that when Alice and Bob are at a party with 2n other couples, and all the 2n+1 people other than Alice shakes a different number of hands, then Alice shakes exact n hands.

Answer 2

This is not possible.

Since n=1 is trivial, let's start with n=2.
There are 2 couples: A&B and C&D.
We require that A shakes hands with 2 people, which have to be C and D. So already C and D shake hands with one person, A.
The only other person C and D could shake hands with is B. So the possible combinations are:
A=2, C=1, D=1
A=2, C=1, D=2
A=2, C=2, D=1
A=2, C=2, D=2

In every case, B will NOT get a different answer from each person.
So the most basic scenario (n=2) does not work, hence the proof by induction cannot be sustained for this problem.

*EXTRAS*
I can also prove to you that the problem does not work.

Bob (B) gets a different answer from every person. If every person includes Alice (A), then consider this. There are 2n-1 other people, and at most one person can shake hands with 2n-2 people. So to have 2n-1 different answers, each of the values 0 to 2n-2 must be given by the 2n-1 different people. So one person must shake hands with 0 people, and another must shake hands withh everyone else. Already we have a problem. But all those responses (from 0 to 2n-2) add up to an odd number. The sum of all the responses should be double the total number of handshakes, thus cannot be odd. The problem cannot work.

Now suppose "every one" does not include Alice. Consider the following counter example which contradicts the problem. There are n=4 couples:
A: C D E
B: C D
C: A B E F G H
D: A B E G H
E: A C D G
F: C
G: C D E
H: C D

In this example, B gets a different response from each person C-H, and still A only shakes hands with n-1=3 people.

The problem cannot be proven since it is not true.

Answer 3

I don't think that's even true, so it certainly wouldn't be provable. Bob got a different answer from everyone he asked. Which means that someone might have answered n (or maybe no one answered n), but it also means that someone answered something other than n. And Alice could have been one of the people who answered something other than n. There's no reason she couldn't.