04-BS-16 · May 2013

Question 9 of 12: Pigeonhole (Ramsey R(3,3)) and Inclusion-Exclusion

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 9: Pigeonhole (Ramsey R(3,3)) and Inclusion-Exclusion (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.

Find. (a) A pigeonhole proof of a monochromatic triangle in every 2-colouring of $K_6$. (b) The number of students who took exactly one course.

(a) Apply pigeonhole at one vertex. Pick any vertex $v$ of $K_6$. It has $5$ edges to the other vertices, coloured red or blue. By the pigeonhole principle, $\left\lceil 5/2\right\rceil=3$ of these edges share the same colour — say (WLOG) $v$ has red edges to vertices $u_1,u_2,u_3$.
(a) Case-split on the triangle among $u_1,u_2,u_3$. Consider the 3 edges among $u_1,u_2,u_3$ themselves. If ANY of these edges (say $u_1u_2$) is red, then $v,u_1,u_2$ forms an all-red triangle (edges $vu_1,vu_2,u_1u_2$ all red). If NONE of $u_1u_2,u_1u_3,u_2u_3$ is red, then all three are blue, and $u_1,u_2,u_3$ forms an all-blue triangle.
(a) Conclude. Either case produces a monochromatic triangle, so $\boxed{\text{every red/blue colouring of } K_6 \text{ contains a monochromatic triangle.}}$
(b) Recover the sum of individual set sizes. At least one course $=120-15=105$. By inclusion-exclusion, $|C\cup A\cup G|=|C|+|A|+|G|-(|C\cap A|+|C\cap G|+|A\cap G|)+|C\cap A\cap G|$, so $$|C|+|A|+|G| = 105 + (35+45+25) - 25 = 105+105-25 = 185.$$
(b) Apply the "exactly one" inclusion-exclusion formula. $$\text{Exactly one} = (|C|+|A|+|G|) - 2(|C\cap A|+|C\cap G|+|A\cap G|) + 3|C\cap A\cap G|$$ $$= 185 - 2(105) + 3(25) = 185 - 210 + 75 = \boxed{50.}$$ Cross-check: exactly-two $=105-3(25)=30$; exactly-three $=25$; none $=15$; total $=50+30+25+15=120$ ✓, matching the given 120 students.

Final results — Question 9
Part	Result
(a)	Monochromatic triangle forced by pigeonhole on one vertex's 5 edges
(b) $\|C\|+\|A\|+\|G\|$	185
(b) Exactly one course	50 students

Topic: Ramsey-type pigeonhole argument ($R(3,3)=6$); inclusion-exclusion for "exactly one" of three overlapping sets.

Key relations: Pigeonhole: $5$ edges in $2$ colours $\Rightarrow\ge\lceil5/2\rceil=3$ share a colour. Inclusion-exclusion: $|C\cup A\cup G|=\sum|{\cdot}|-\sum|{\cdot}\cap{\cdot}|+|{\cdot}\cap{\cdot}\cap{\cdot}|$; exactly-one $=\sum|{\cdot}|-2\sum(\text{pairs})+3(\text{triple})$.

Why this works: Part (a) is the classical proof that $R(3,3)\le6$: forcing 3 same-coloured edges from one vertex reduces the problem to a 3-vertex sub-triangle, which is trivially monochromatic either directly (an edge matches the spokes) or by being the "all-opposite-colour" fallback. Part (b)'s "exactly one" formula subtracts each pairwise overlap twice (once for over-counting in each of the two sets it belongs to) and adds the triple back three times to net out to zero extra count for elements in all three sets.

Common pitfall: In (a), forgetting the WLOG case split covers BOTH the "some spoke-triangle edge is red" and "all spoke-triangle edges are blue" possibilities exhaustively; in (b), trying to read off $|C|,|A|,|G|$ individually when only their SUM is determined by the given data (individually they are under-determined, but the "exactly one" total only needs the sum).

Source: Rosen, Discrete Mathematics and Its Applications, §6.2 (pigeonhole, Ramsey numbers), §8.1 (inclusion-exclusion, principle for three sets).

← Question 8 Next: Question 10 →