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) 50 arbitrary days, each falling on one of 7 weekdays. (b) Real numbers $x,y$.

Find. (a) A pigeonhole proof that some weekday contains $\ge8$ of the 50 days. (b) A proof of the stated inequality.

Approach. (a) apply the generalized pigeonhole principle with 7 boxes; (b) recognize the left side as $|a|+|b|$ for a clever choice of $a,b$ that sum to $x+y$, then invoke the triangle inequality.

1. (a) At least 8 of 50 days share a weekday. Treat the 7 weekdays (Sunday–Saturday) as pigeonholes and the 50 days as pigeons; each day is assigned to exactly one weekday-box. The generalized pigeonhole principle states that if $N$ objects are placed into $k$ boxes, some box contains at least $\lceil N/k\rceil$ objects: $$\left\lceil \dfrac{50}{7}\right\rceil = \left\lceil 7.142\ldots\right\rceil = 8$$ (if every weekday had at most 7 days, the total would be at most $7\times7=49\lt50$, a contradiction). So some weekday must contain at least 8 of the 50 days. $\boxed{\text{At least 8 of any 50 days fall on the same weekday, by the pigeonhole principle with }\lceil50/7\rceil=8}$
2. (b) $|x-1|+|y+1|\ge|x+y|$. Let $a=x-1$ and $b=y+1$. Then $a+b=(x-1)+(y+1)=x+y$. The triangle inequality for real numbers states $|a|+|b|\ge|a+b|$ for any reals $a,b$ (a special case of the general triangle inequality, provable by squaring both sides or by cases on the signs of $a,b$). Applying it here: $$|x-1|+|y+1| = |a|+|b| \ \ge\ |a+b| = |x+y|$$ $\boxed{|x-1|+|y+1|\ge|x+y|\text{ for all real }x,y}$