Massachusetts Institute of Technology Handout 11 6.042J/18.062J: Mathematics for Computer Science September 18, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 2

1. Handshakes. I recently went to a party with my spouse; there were 11 other married couples there. A lot of handshaking happened (but of course no one shook hands with their spouse). At the end, it turned out that for every k from 0 to 22, someone other than me had shaken hands with exactly k people. How many people did I shake hands with? Prove your answer.

2. Geometric mean vs Arithmetic mean. Show that for any non-negative real numbers x_{1}, x_{2}, …, x_{n},

(x_{1}x_{2} … x_{n})^{\frac{1}{n}} ≤ (\frac{x_{1} + x_{2} + … + x_{n}}{n} )