, 2011

Combinatorics Difficulty 6.3 National olympiad Prove it Croatia

Spouses Ana and Tomislav attended a party with four other couples. Upon arrival there was a certain number of handshaking, but no one shook hands with his or her spouse nor with himself/herself. When later Tomislav asked everyone at the party how many people they shook hands with, he got nine different answers. How many people did Ana shake hands with? (www.masa.on.net)

Solution

No one shook hands with more than eight people so the responses that Tomislav got are: "0", "1", "2", "3", "4", "5", "6", "7", "8".

Ana certainly did not shake hands with eight people. Namely, if we assume that she did shake hands with eight people, all the others (except Tomislav) had to shake hands with her, so no response would be "0".

Let the person who shook hands with eight people be $A_1$ . We can conclude that the only person who could shake hands with zero people is the spouse of $A_1$ . Let's call this person $A_2$ .

If now we assume that Ana shook hands with seven people, then all the others except Tomislav and person $A_2$ had to shake hands with Ana, so no response would be "1" (since all of them also shook hands with $A_1$ ).

Let the person who shook hands with seven people be $B_1$ . Again we conclude that the person who gave the response "1" is the spouse of $B_1$ because all the others shook hands with person $A_1$ and person $B_1$ . Let's call this person $B_2$ .

By similar reasoning we conclude that spouses $C_1$ and $C_2$ gave responses "6" and "2", and spouses $D_1$ and $D_2$ gave responses "5" and "3".

Finally we conclude that Ana gave the response "4", i.e. she shook hands with four people.

The graph below shows that this is really possible:

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.