Awesome Problem

[Ender]

Once again, this is taken from a book that I will not name.

I invite 10 couples to a party at my house. I ask everyone present, including my wife, how many people they shook hands with. It turns out that everyone shook hands with a different number of people. If we assume that no one shook hands with his or her partner, how many people did my wife shake hands with? (I did not ask myself any questions.)

Have fun

[rabbit]

Try to change the wording so people can't Google it, or make up one of your own :\
[size=0pt]At first the problem may seem impossible. There doesn’t appear to be enough
information. Nevertheless, we can make it easier by looking at a simpler case: one
where there are 2 couples invited over to my house, and, of course, my husband Eric.
I, the hostess, have interrogated all 5 people other than myself and there were 5
different “handshake numbers.” Since there numbers range from 0 to 4 inclusive (no
one shakes hands with their spouse, ruling out 5), the 5 handshake numbers are 0, 1,
2, 3 and 4. Let’s call these people P
0
, P
1
, P
2
, P
3
and P
4
, respectively, so that P
N
shook
hands with N people. Now let’s draw a picture, including myself in the picture with
the label A for Angela.
It is interesting to look at the two people with the extreme handshake numbers, i.e. P
0
and P
4
, respectively. Since P
4
shook hands with everyone possible, which means that
everyone except for P
4
’s partner shook P
4
’s hand? So P
4
and P
0
must be partners.
Moving on to P
3
, we can see that P
3
shook hands with all but one person other than
his or her partner. If we exclude P
0
and P
4
, then P
1
and P
3
play the same role that P
0
and P
4
played. (P
3
shakes hands with 2 out of 3 people P
1
, P
2
and A, and we know
that P1 doesn’t shake hands with P
3
, so the only possible person P
3
can be partnered
with is P1.
The only people left are P
2
and A. They must be partners, so P
2
is my husband Eric
and he shook hands with 2 people.
Angela
P
0
P
1
P
2
P
3
P
4
Page 2
It is easy to adapt this argument to the general case of N couples.
Formal solution:
We shall use induction. For each positive integer N, define the statement P(N) to be:
If the Angela invites N couples, and if no one shakes hands with his
or her partner, and if each of the 2N+1 people interrogated by
Angela shook a different number of hands, then Eric shook N hands.
It is easy to check P(1). We need to show that P(N) implies P(N+1), and we’ll be
done. So, assume that P(N) is true. Now consider a party with N+1 couples (other
than Eric and I) satisfying all of our criteria. Then, all handshake numbers from 0 to
2(N+1)=2N+2 inclusive will occur among the 2N+3 people interrogated.
Consider the person P
2N+2
(who shook hands with 2N+2 hands). This person shook
hands with all but two of the 2N+4 people at the party. Since no one shakes hands
with themselves or their partner, P
2N+2
shook hands with everyone possible. So the
only person who could be partnered with P
2N+2
had to have be the person P
0
, who
shook zero hands, for everyone else shook hands with P
2N+2
and is hence ineligible as
a partner for P
2N+2
.
Now, let us remove P
2N+2
and P
0
from the party. If we no longer count handshakes
involving these 2 people, we are reduced to a party with N invited couples and
everyone’s handshake number (other than Angela, about whom we have no
information) has dropped by exactly 1, since everyone had shaken hands with P
2N+2
and no one had shaken hands with P
0
. But the inductive hypothesis P(N) tells us that
Eric shook hands with N people at this smaller party. In reality, Eric shook one more
hand – that of P
2N+2
whom we just removed. So in the party with N+1 invited
couples, Eric shook hands with N+1 hands, establishing P(N+1).
In our case, we invited 10 couples over to our house. Thus, Eric shook 10 hands[/size]
[size=0pt]Source: http://72.14.209.104/search?q=cache:BelCWwdOSPsJ:www.mathstat.dal.ca/~siegel/math3790/pdf/Assignment1Solutions.pdf+%2210+couples+to+a+party+at+my+house.%22&hl=en&gl=us&ct=clnk&cd=1&client=firefox-a[/size]

[Ender]

I tried googling the whole thing. There are much better ways of cheating on this but the one I mentioned is the laziest. If someone were really motivated to cheat on this, they'd be able to cheat on it anyway even if I fudge the wording... so I think it's not worth the extra effort =p

[rabbit]

Quote my post.

[Ender]

Rabbit, I think you killed this thread. And to your last post: ditto.

Come on guys, get out your pencils and paper!