[OlymLSec20160201PHHE] Pigeonhole Principle and Harry’s emails

Problem / Question

Handsome Harry has a secret email account that only four friends know.  Today he received 8 emails in that account. Which of the following is certainly true? (A)  Harry received two emails from each friend. (B)  Harry cannot have received eight emails from one of his friends. (C)  Harry received at least one email from each friend. (D)  Harry received at least two emails from one of his friends (E)  Harry received at least two emails from 2 different friends.

Introduction

      This question is from some Kangaroo Mathematics Competition, which tests students on logic and not necessarily things from Singapore Mathematics syllabus. 

Solution

      (D)  Harry received at least two emails from one of his friends

Explanation

      This is an example of the Pigeonhole Principle.  Perhaps the easiest way to understand this is to imagine an array of pigeonholes with four columns (one for each of Harry’s friends) and pigeons (representing individual emails sent from the friends).  In the diagram below, I draw dots instead of pigeons.

As you can see, no matter how the eight dots / pigeons are placed, at least one of the friends will have at least two dots.  It is not possible for all the friends to have less than two emails.

Formal Proof

     We can use a proof by contradiction argument.  Suppose it were not true that Harry received at least two emails from one of his friends.  That would mean each of his  4  friends sent at most one email.  But then the total number of emails would be  4  or less.  This contradicts the given fact that Harry received  8  emails.  So this state of affairs is not possible.  Therefore, the opposite is true.  We conclude that Harry received at least two emails from one of his friends.

Final Remarks

      The Pigeonhole Principle is very useful in many situations, including computer science.  In general, if you have more objects (“pigeons”) than there are containers or slots (“pigeonholes”), one of the containers must have at least two of those objects.

Heuristics Used

H02. Use a diagram / model

H04. Look for pattern(s)

H05. Work backwards

H08. Make suppositions

H09. Restate the problem in another way

Suitable Levels

* Lower Secondary Mathematics Competition / Olympiad

* other syllabuses that involve logic, combinatorics or Pigeonhole Principle

* any precocious or independent mathematics problem solver who is interested