Question 10 of 12

Question 10 (10 marks)

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) 36 arbitrary calendar days. (b) Two arbitrary real numbers $x,y$.

Find. (a) A proof, via the pigeonhole principle, that some weekday is shared by at least 6 of the days. (b) A proof of the triangle inequality for real numbers.

Approach. (a) apply the generalized pigeonhole principle with 7 "pigeonholes" (weekdays) and 36 "pigeons" (days). (b) case-split on the signs of $x,y$ (or bound $x+y$ above and below using $-|x|\le x\le|x|$ and the same for $y$).

1. (a) At least six of 36 days share a weekday. There are 7 possible days of the week (the "boxes"), and 36 given days (the "objects") to be sorted into them. By the generalized pigeonhole principle, if $N$ objects are placed into $k$ boxes, some box receives at least $\lceil N/k\rceil$ objects: $$\left\lceil\frac{36}{7}\right\rceil=\left\lceil 5.142\ldots\right\rceil=6$$ So at least one weekday must be the day-of-week for at least 6 of the 36 days. $$\boxed{\text{At least } \lceil 36/7\rceil = 6 \text{ of the 36 days share a weekday}}$$
2. (b) Prove $|x+y|\le|x|+|y|$ (triangle inequality). For any real $x$, $-|x|\le x\le|x|$, and likewise $-|y|\le y\le|y|$. Adding the two inequalities: $$-(|x|+|y|)\le x+y\le |x|+|y|$$ This says $x+y$ is sandwiched between $-(|x|+|y|)$ and $|x|+|y|$. A standard fact about absolute value states that $-M\le t\le M \iff |t|\le M$ (for $M\ge 0$); applying it with $t=x+y$ and $M=|x|+|y|\ge0$ gives directly: $$\boxed{|x+y|\le|x|+|y|}$$