1 Suppose that eight people attend a math mixer Prove that i

1) Suppose that eight people attend a math mixer. Prove that if each person shake hands with some (possible none) of the other guest, and no pair of individuals shakes hands more than once, then there must exist two guests who shook the same total number of hands.

2)suppose instead that in the game of Snatch players may only remove 1,3 or 4 pennies on each turn. Now which values of n constitute a losing position? Write your answer and explanation as before.

Solution

1) If no two persons have shaken hands with equal number of persons then there handshake count must differ atleast by 1.

So the possible choices for handshake count would be 0, 1, 2, 3,4,5,6,7. There are exactly 8 choices and 8 people.But now if a person has 7 choice of handshakes then no person can have 0 handshakes.Thus it will reduce the possible choices to 7 choices.

So there are 8 persons and 7 choices of handshake and hence by Pigeon hole principle, we have atleast two persons who will have same number of handshake count