04-BS-16 · May 2013

Question 3 of 12: Pigeonhole and Induction Proofs

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, May 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 3: Pigeonhole and Induction Proofs (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.

Approach. Part (a) is strong induction with four base cases (to clear a gap of four before the +4 inductive step applies cleanly). Part (b) is the pigeonhole principle applied to the total sum 55 split across 3 groups.

(a) Base cases $n=12,13,14,15$. $12=4+4+4$; $13=4+4+5$; $14=4+5+5$; $15=5+5+5$. All four are achievable with 4- and 5-cent stamps.
(a) Strong-induction step. Let $k\ge 15$ and assume every amount from 12 to $k$ is formable. Consider $k+1$: since $k\ge 15$, $(k+1)-4 = k-3 \ge 12$, so by the inductive hypothesis $k-3$ cents is formable using 4s and 5s; adding one more 4-cent stamp forms $k+1$ cents. Because the four base cases already span every residue class mod 4 (12,13,14,15 $\equiv$ 0,1,2,3), the induction covers every integer $\boxed{n\ge 12}$.
(b) Compute the total. $\displaystyle\sum_{i=1}^{10}i = \frac{10\cdot 11}{2}=55$.
(b) Apply the pigeonhole principle. Suppose, for contradiction, that every one of the 3 groups has sum $\le 18$. Then the total sum would satisfy $55=\text{(sum of the 3 groups)} \le 3\times 18 = 54$, a contradiction since $55>54$. Therefore $\boxed{\text{at least one group has sum}\ge 19}$.

Final results — Question 3
Part	Result
(a)	Proved for all $n\ge12$ via 4 base cases + $n\mapsto n+4$ induction step
(b)	Total = 55; 3 groups all $\le18$ would give $\le54<55$ — contradiction, so some group $\ge19$

Topic: Strong induction with multiple base cases; the pigeonhole principle via a counting bound.

Key relations: Pigeonhole (generalized form): if $N$ objects are split into $k$ groups, some group has $\ge \lceil N/k \rceil$; here $\lceil 55/3\rceil=19$.

Why this works: The postage proof needs four consecutive base cases (not one) because the inductive step adds exactly 4, so it can only "reach" $n+4$ from $n$ — starting from a single base case would skip 3 out of every 4 integers. The pigeonhole bound is really an averaging argument: if the average per group exceeds 18, some group must be at least the ceiling of that average.

Common pitfall: Using only one base case for a step size of 4 (leaves 3 residue classes unproved); using a strict inequality in the pigeonhole contradiction instead of $\le18$ vs. $55>54$.

Source: Rosen, Discrete Mathematics and Its Applications, §5.2 (strong induction), §6.2 (the pigeonhole principle).

← Question 2 Next: Question 4 →