Question 9 of 12

Question 9

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) 1100 people, 365 possible birthdays. (b) real numbers $x,y$.

Find. (a) a pigeonhole proof that some day has $\ge4$ people. (b) a proof of the inequality.

Approach. (a) generalized pigeonhole principle, $\lceil N/k\rceil$. (b) write $x+y$ as the sum $(x-3)+(y+3)$ and apply the triangle inequality $|u+v|\le|u|+|v|$.

1. a) At least 4 of 1100 people share a birthday. $k=365$ possible birthdays (pigeonholes), $N=1100$ people (pigeons). Some pigeonhole holds at least $$\left\lceil\frac{1100}{365}\right\rceil=\lceil3.0137\rceil=4.$$ Directly: if every day had at most 3 people, there could be at most $3\times365=1095<1100$ people, a contradiction. $\boxed{\text{At least 4 people share a birthday}}$. (Including 29 February, $3\times366=1098<1100$, so the conclusion survives leap years too.)
2. b) Prove $|x-3|+|y+3|\ge|x+y|$. Let $u=x-3$ and $v=y+3$; then $u+v=x+y$ (the $\mp3$ cancel). By the triangle inequality $|u+v|\le|u|+|v|$: $$|x+y|=|(x-3)+(y+3)|\le|x-3|+|y+3|.$$ $\boxed{|x-3|+|y+3|\ge|x+y|\ \text{for all real } x,y}$, with equality exactly when $x-3$ and $y+3$ have the same sign (or one is zero).

Part (b) works because the two shifts are chosen to cancel: $-3$ inside the first absolute value and $+3$ inside the second add to zero, so the sum of the two inner quantities is exactly $x+y$. Had the shifts not cancelled (for example $|x-3|+|y-3|$), the same argument would bound $|x+y-6|$ instead, and the stated inequality would need a separate argument.