EJC 2026 H3 Mathematics - Pigeonhole Principle - Notes, Tutorial, and Solutions to Tutorial

1 H3 MATHEMATICS (9820) PIGEONHOLE PRINCIPLE The Pigeonhole Principle (PP) (Simple form) Let n be any positive integer. If at least n + 1 objects are distributed among n boxes, then (at least) one of the boxes must contain at least 2 objects. (Strong form) Let k and n be any two positive integers. If at least kn + 1 objects are distributed among n boxes, then (at least) one of the boxes must contain at least k + 1 objects. Proof If no boxes contain k + 1 or more objects, then every box contains at most k objects. This implies that the total number of objects put into the n boxes is at most kn, a contradiction. Alternatively, we can also formulate the pigeonhole principle as: If m objects are distributed among n boxes, then (at least) one of the boxes must contain at least m n   objects. Two main skills are required . Firstly we need to work through the logic of the solution, which often includes identifying appropriate “pigeons” and “pigeonholes”. Secondly we need to write the proof in a form that is readable and rigourous (and not too long). The two are somewhat connected; often a clear definition of appropriate variables or objects helps with both.

Example 1 Show that among any 4 integers, there are two whose difference is divisible by 3. Solution Let the four integers be a, b, c, d. Since each must be 0, 1, or 2≡ (mod 3), by pigeonhole principle there must be two of them that are congruent to the same remainder mod 3; without loss of generality let these be a and b. Then ab≡ (mod 3) (by transitivity of ≡), so 0ab−≡ (mod 3) and ab− is divisible by 3.  Example 2 Show that for any set of 5 points chosen within a square whose sides are of length 2 units, there are two points in the set whose distance apart is at most 2 . Thought process With 5 points, we will be able to partition the square into 4 pieces and use pigeonhole principle to conclude “there must be at least 2 points in one of the partitions ”. So, for the proof to work, we must create partitions such that the distance between any 2 points in the same partition is not more than 2 . In particular, the below is not helpful: Solution Divide the square into 4 sub-squares of unit length: Since there are 5 points, by pigeonhole principle there must be one sub- square with at least 2 points in/on it. But the distance between any two points in/on the same sub-square is at most 2 . So, the two points in/on the same sub-square are distance at most 2 apart. 

Example 3 Let { }12345,,,,B bbbbb= be a set of 5 distinct positive integers. Show that for any permutation (i.e. rearrangement of the elements) 1 2345iiii ibbbbb of B, the product ( 1 1ibb− )( 2 2ibb− ) ... ( 5 5ibb− ) is always even. For example, if B = {26, 7, 1, 22, 11} and a permutation of B is (1, 22, 26, 11, 7). Then the product (1 − 26)(22 − 7)(26 − 1)(11 − 22)(7 − 11) is even. Thought process A product is even if and only if one or more factors is even. The fact that 5 is odd seems to be important, since that means there must be more of one type… Solution 1 By pigeonhole principle, at least 5 32  = of the integers must be of the same parity. WLOG suppose 123,,bbb are of the same parity. Then a maximum of two of 45 ,iibb can be 12,bb or 3b . That implies that one of 231 ,,ii ibbb is equal to 12,bb or 3b . So one of ( ) ( ) ( )12 3 12 3,,ii ibbbb bb−−− is a difference of two integers of the same parity, which means the difference is an even integer. So the entire product is even.  Thought process While the above is a valid proof, the second half of the solution feels a little awkward to write. In this particular case, the somewhat unnatural step of combining the permuted and non- permuted integers makes the solution shorter. Solution 2 By pigeonhole principle, at least 5 32  = members of B have the same parity. This means that at least 6 of 51 23412345,,,,,,,,, i iiiibbbbbbbbbb have the same parity. By pigeonhole principle, when these 10 integers are distributed into 5 factors, there must be at least two of them in the same factor, say kikbb− . Then this factor is even, so the entire product is even. 

Example 4 (Handshake Problem, also appeared as 2018/Q6a) Consider any group of n students where 2n≥ . Prove that there are at least two students who have the same number of friends in the group. State clearly any assumption you have made about friendships. Assumptions We assume that friendship is: - non-reflexive (no one is a friend of themself) and - symmetric (if A is a friend of B, then B is a friend of A). Thought process With the two assumptions, the number of friends a person can have ranges from 0 to 1n− . At first sight, this is not enough because we have n people and n possible number of friends. By thinking deeper about the “0 friends” case, we might find a breakthrough. Initial Solution Case 1: There is at least 1 student with no friends. Then the maximum number of friends a student can have is 2n− . So there are only 1n− different possible numbers of friends, namely { }0,1, ..., 2n− , among n students. By pigeonhole principle, there must be two students who have the same number of friends. Case 2: There are 0 students with no friends. Then the minimum number of friends a student can have is 1. So there are only 1n− different possible numbers of friends, namely { }1, 2,..., 1n− , among n students. By pigeonhole principle, there must be two students who have the same number of friends.  Thought process Looking back at the cases, the crux is that there cannot be both a student with 0 friends and a student with 1n− friends. But this means that we can lump both into one pigeonhole. Refined Solution Divide the students into 1n− categories , 1,2,..., 1kAk n = − as follows: 12 2 1 ... 1 friend 2 friends ... 2 friends 0 or 1 frie nds nnAA A A nn −− −− By pigeonhole principle, there must be at least 2 students in 1 category. If there are 2 students in any of the first 2n− categories, they must have the same number of friends. For the last category, if there are 2 students in that category, they must also have the same number of friends because it is not possible for one student to have 1n− friends (so is friends with everyone) and another to have 0 friends at the same time. 

One lesson from Example 4 is that sometimes when we don ’t seem to have enoug h pigeons, we can think about looking for more pigeons or combining some pigeonholes. Example 5 (2018/Q6b) Let x be any positive real number and let n be any positive integer. Prove that there are integers a and b, with 1 bn≤≤ , such that 1ax b bn−< . Thought process The condition 1ax b bn−< can be re-written as 1bx a n−< . Since a is integer, this hints at examining the fractional part of bx as b varies. A natural thing is to divide the unit interval into segments of length 1 n . But there are n intervals, and we only have n different values of bx . Keeping this unresolved issue in mind, let us first confirm that the logic works if any pigeonhole contains two pigeons: Trial Solution For any positive number y, we define frac( )yyy= −  . Consider the n numbers ( ) ( ) ( )frac , frac 2 , , fracx x nx  and the n intervals 1230, 12 1,,, ,, , , 1 n nn n nnn              −     . Suppose one interval contains both frac( )px and frac( )qx where pq> . Since the difference between two numbers in the same interval must be smaller than 1 n , ( ) ( ) 1frac fracpx qx n−< 1px px qx qx n− −+ <   ( ) ( ) 1p q x px qx n−− − < ( ) 1px qxpq x pq n  −−− < − ( ) 1px qxx pq pq n −−< −− So, letting a px qx= − and b pq= − , we get the required result 1ax b bn−< .

Thought process So