**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.**

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

## No comments:

## Post a Comment