[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

[OlymLSec_20160118PPPC] A Square Proof by Contradiction

Question

Explanation

     If  a + b = 11,  then  2ab = (a + b)² – (a² + b²) = 121 – 100 = 21.  But  2ab  is an even number, whereas  21  is odd.  This is a contradiction.  So (B) is impossible.  ©

Remarks

     Short and sweet isn’t it?  This uses the square-of-sum identity   (a + b)² = a² + 2ab + b².  I used the tactic of assuming the answer is correct  [H08]  and showing that this leads to something nonsensical [H05].  So the original assumption must be wrong.  This is called “proof by contradiction” or reductio ad absurdum (in Latin).

     By the way, the correct answer option is (E) from the Pythagorean Triplet   8² + 6² = 10²  with  {a, b} = {8, 6}.  The question seems to be taken from some Kangaroo mathematics competition.

Heuristics Used

H05. Work backwards

H08. Make suppositions

H09. Restate the problem in another way

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* Lower Secondary Mathematics competition

* GCE ‘O’ Level “Elementary” Mathematics (challenge)

* other syllabuses that involve whole numbers and Pythagorean triplets

* any precocious or independent learner who loves a challenge

[AM_20160115SEAV] Simultaneous equations? Absolutely!

Problem / Question

Introduction

     This question was from a Facebook group not dedicated to “Singapore math”.  The thing is, mathematics is really an international experience, especially with modern social media.

     Simultaneous equations can pose a challenge to students, but this one is absolutely more challenging, because of the absolute value.

The Absolute Value

Strategy

     The problem is: we do not know whether each of  x  and  y  is negative or otherwise.  That potentially raises complications.  There seems to be  4  cases to check.  However, by making assumptions  [H08]  separately and checking for contradictions [H07], we can narrow down the possibilities.  [H10]  Finally, we can simplify the problem to a regular pair of simultaneous linear equations   [H10]  and solve it by the method of elimination.  [H10, H11]

Solution

Heuristics Used

H04. Look for pattern(s)        [deciding what to eliminate]

H07. Use guess and check     [is x negative?  is  y negative?]

H08. Make suppositions        [is x negative?  is  y negative?]

H10. Simplify the problem

H11. Solve part of the problem

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* Lower Secondary Olympiad

* GCE ‘O’ Level Additional Mathematics, “IP Mathematics” (challenge)

* other syllabuses that involve simultaneous equations and absolute values

* any precocious or independent learner who wants his/her mind tickled

[OlymLSec_20160109CBDR] Derangement of Cars in a Roundabout

Problem / Question

Introduction

     Some enthusiastic student posted this “deranged” question on Facebook.  It is taken from the Singapore Math Kangaroo Contest.  The question involves derangements, which does not appear in any syllabus in Singapore before university level.

     If the problem involved a circular permutation, the correct answer would have been  (5 – 1)! = 4 × 3 × 2 × 1 = 24.  But this is not a circular permutation, because the roads are distinguished by their different positions.  If one rotates the roundabout, this would be considered a different pattern.  If it were a permutation, the answer would have been  5! = 5 × 4 × 3 × 2 × 1 = 120.  However, it is not a permutation, because the cars cannot go back to their original road in the opposite direction.  That is what the Kangaroo phrase “drives less than one round” mean.

     A derangement is a some rearrangement in which things are not allowed to go back to their original position.  If one has not learned the formula for derangements, how could this be solved?

Strategy

     We can consider simpler cases [H10] of the problem and build up the answer from there.  We may also split the problem into two cases.  [H11]

Solution

     Let  !n  denote the number of derangements if there are  n  cars and  n  road branches in the roundabout.  [This is called the subfactorial of  n.]

     For  n = 1,  !n = 0  because the car has no way but to go back on the original road.

     For  n = 2,  !n = 1  because the only way is for the two cars to swap.

     For  n = 3:  Car  #1  has two choices: either road  #2  or road  #3.  But it cannot end up swapping roads with any car, else the remaining car would have to go back to its original road, which is not allowed.  So it is either  #1 ® #2 ® #3 ® #1  or  #1 ® #3 ® #2 ® #1.  Therefore  !3 = 2.

     For  n = 4:  Car  #1  has 3 choices.  For each of these choices, either it ends up (1) swapping roads with the other car, or  (2) it does not swap.  

Case (1):  If it swaps with the other car, then the remaining  2  cars will have  !2 = 1 way.

Case (2):  If car  #1  goes to some road but not swapping roads with it,  then the other  3  cars will have  !3 = 2  ways to choose roads different from their original roads.

Therefore  !4 = 3 × (!3 + !2) = 3 × (2 + 1) = 9.

     For  n = 5:  Car  #1  has 4 choices.

Case (1):  It swaps with the other car.  The remaining  3  cars will have  !3 = 2 ways.

Case (2):  It does not swap with any car.  The other  4  cars will have  !4 = 9  ways.

Therefore  !5 = 4 × (!4 + !3) = 4 × (9 + 2) = 44.

Ans:  (B)  44.

Remarks

     For more information regarding derangements, please refer to here and here.

Heuristics Used

H02. Use a diagram / model   (can be used for small number cases)

H03. Make a systematic list   (can be used for small number cases)

H04. Look for pattern(s)

H05. Work backwards

H09. Restate the problem in another way

H10. Simplify the problem

H11. Solve part of the problem

Suitable Levels

* Lower Secondary Mathematics Competition

* University / College Combinatorics

* other syllabuses that involve derangements

* any precocious or interested learner who is interested

[OlymLS_20151220INEQ] An Egyptian Fraction Partition of Unity?

Problem

Introduction

     This question appeared in a “holiday homework” from an IP school.  It is not the usual type of question in exams and tests, but it is a good mental-stretching exercise.  It is asking us to split unity (the number “1”) into three unit fractions (a.k.a. Egyptian fractions).

     The first part can be solved by trial and error or “guess and check”.  The second part, proving that this is the only solution (are there any other solutions?), seems challenging.  We can solve this by making suppositions and using inequalities.

Solution

                                              

Heuristics Used

H03. Make a systematic list

H05. Work backwards

H07. Use guess and check

H08. Make suppositions  [ which may lead to negative conclusions ]

H10. Simplify the problem

H11. Solve part of the problem

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* Primary School / Lower Secondary Olympiad

* other syllabuses that involve fractions and inequalities

* any learner who is itching for a mental challenge

[S1_20151124AESR] Slanted Rectangle does not need Pythagoras

Question

Introduction

     This is another “Bonus Question” at a secondary level from somewhere that the question poser did not mention, but I guess it is most likely an Integrated Programme school in Singapore.  It is a beautifully crafted question.  The presence of a slant line seems to necessitate the usage of Pythagoras’ Theorem.  However, we have seen that Pythagoras’ Theorem can actually be avoided even in Primary (Elementary) School problems.  So a 10 year old kid with a rudimentary knowledge of algebra could do this.  Can you spot a short cut?

Making Observations

     Stare at the diagram for a while.  What do you observe?

Solution

             area of  DDB_nC_n =  ½  of the area of  AB_nC_nD.

              area of  DDB_nC_n =  ½  of the area of  DB_nPQ.

        \  area of DB_nPQ  =  area of AB_nC_nD = n cm².

HeuristicsUsed

H04. Look for pattern(s)

H05. Work backwards

H09. Restate the problem in another way

H11. Solve part of the problem

Suitable Levels

* Lower Secondary Mathematics

* challenge for Primary school Olympiad

* other syllabuses that involve areas and a tiny bit of algebra

* anyone game itching for a challenge

[NumTh Expository] The Principle Behind Casting Out Nines

Introduction

Think of a number ... say 685932.  Divide by  9  and take the remainder.      685932 ¸ 9      = 76214 r 6  Add up the digits,  divide by  9  and take the remainder.      6+8+5+9+3+2 = 33 ¸ 9 = 3 r 6  What do you notice?  Try this with any other positive whole number.

Discussion

     Did you see that a number and its sum of digits always have the same remainder when divided by  9?  This is the principle behind the method of “casting out nines”, used in the past for checking arithmetical calculations.  Why does this work?  Where is its magic?

     The decimal number system that we use today is based on the number  10, which is just  1  larger than  9.  Observe that  9, 99, 999, 9 999, 99 999, ... etc are all divisible by  9.  Hence, the powers of 10, namely 10⁰ = 1,  10¹ = 10,  10² = 100,  10³ = 1 000,  10⁴ = 10 000,  10⁵ = 100 000,  etc  all leave a remainder of  1  when divided by  9.   Thus in our example,

     685932 = 6´10⁵ + 8´10⁴ + 5´10³ + 9´10² + 3´10¹ + 2´1

                  = 6´(99999+1) + 8´(9999+1) + 5´(999+1) + 9´(99+1) + 3´(9+1) + 2´1

                  = 6´99999+8´99995´999+9´993´9 + 6´1+8´1+5´1+9´1+3´1+2´1

                  = 9 ´ something + 6+8+5+9+3+2

As you can see, all the “´1” allow us to separate out the digits, and then the stuff with 9, 99, 999 etc can be lumped together as 9 ´ some whole number, but we do not need to care too much about this multiple of 9 as it would not make any difference to the remainder.  It is now obvious that  685932 and 6+8+5+9+3+2=33 will have the same number when divided by 9.

     Let us generalise the argument.   If two numbers  x  and  y  have the same remaider when divided by 9,  we say that  x  and  y  are congruent modulo 9, and we write     x  º  y  (mod 9).  Congruence is an equivalence relation and “º” behaves in many ways similar to “=”.

Theorem

For an arbitrary number  n   with digits  [dk...d3d2d1d0]                                         n º dk + ... + d3 + d2 + d1 + d0   (mod 9)

                 n = d_k ´10⁴ + ... + d₃´10³ + d₂´10² + d₁´10 + d₀.    

Since  10^k º 1 (mod 9)  for all integers  k > 0,  we have

                 n º d_k´1 + ... + d₃´1 + d₂´1 + d₁´1 + d₀

                 n º    d_k  + ... +   d₃   +    d₂  +   d₁    + d₀     (mod 9).   © (Q.E.D.)

As an example of application of this principle, please refer read thisarticle.

Suitable Levels

* Primary School Mathematics Olympiad

* syllabuses that involve congruences and Number Theory

* anybody who is interested

[OlymPri20151105NTC9] An x to Find by Casting Out Nine

Question

In class, John was thinking of a 6-digit number, A.  He added up all the digits and got the result, B.  Then, he subtracted  B  from  A, which gave a result, another 6-digit number, whose digits consist of 0, 2, 4, 6, 8 and  x.  Find a possible answer for  x.

Introduction

     This problem looks mind-boggling.  There are so many possible 6-digit numbers and there seems to be no clue as to how to even begin.  This problem hinges on a forgotten fact that many people used to learn when electronic calculators were not so prevalent.

Old Wine Most Fine

     It is a fact that any number is equivalent to its sum ofdigits in the sense that they both have the same remainder when divided by 9.  (see this article)  This is the principle behind the method of “casting out nines”, used in the past for checking arithmetical calculations.  Mathematics is never out-dated.  In fact, some of the old forgotten theory may sometimes turn out surprisingly useful.  If two numbers  x  and  y  have the same remaider when divided by 9,  we can write  x  º  y  (mod 9)  but in this article, I shall just write  x º y.  If   x º 0,  it just means that  x  has no remainder when divided by  9  i.e.    x  is a multiple of  9.

Solution

     Since                             A º B      where  B = sum_of_digits(A),

                                    A – B º 0

             sum_of_digits(A – B) º 0

           0 + 2 + 4 + 6 + 8 + x  º 0

                                  20 + x  º 0  [ 20 + x  is a multiple of  9]

                                     \  x  º 7  [x  is a digit & the next higher multiple of  9  is 27]

Remark

     One possible value of  A  is  864738.  Then  A – B = 864738 – 36 = 864702

Heuristics Used

H04. Look for pattern(s)

H05. Work backwards

H09. Restate the problem in another way

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* Primary School Mathematics Olympiad

* syllabuses that involve congruences and Number Theory

* anybody who is interested

[NumTh Expository] Divisibility Tests for 7 and other digits

Introduction

     Let  n = ...ABCDEFG = ... + A´10⁶ + B´10⁵ + C´10⁴ + D´10³ + E´10² + F´10 + G. 

I invent the notation  ‘n ¸ d’  to mean  “n  is divisible by  d”  (as integers).  For a definition

n ¸ d   Û   d | n   Û   n = kd  for some integer  k

Many of you may have heard of the following divisibility tests:-

n ¸ 1   is always true   n ¸ 2   Û   the last digit  G ¸ 2   Û   the last digit  G Î {0, 2, 4, 6, 8}   n ¸ 3   Û   the sum of digits  ... A+B+C+D+E+F +G ¸ 3   n ¸ 4   Û   the last digits  FG ¸ 4   n ¸ 5   Û   the last digit  G ¸ 5   Û   the last digit  G Î {0, 5}   n ¸ 6   Û   n ¸ 2  and  n ¸ 3  (see above)   n ¸ 8   Û   the last digits  EFG ¸ 8   n ¸ 9   Û   the sum of digits  ... A+B+C+D+E+F+G ¸ 9 n ¸ 10   Û   the last digit  G = 0

What about divisibility by 7?

Modulo Arithmetic

     Divisibility tests are all based on modular arithmetic (a.k.a. clock arithmetic), as part of number theory.  This arithmetic was developed initally by a very clever mathematician

called Carl Friedrich Gauss.  The key idea is that numbers can be grouped into separate classes.  For example, when considering division by  3,  we can split the integers into three equivalence classes called residue classes

     [0] = { ..., -3, 0, 3, 6,   9, 12, ... }

     [1] = { ..., -2, 1, 4, 7, 10, 13, ... }

     [2] = { ..., -1, 2, 5, 8, 11, 14, ... }

The members of each class have the same remainder when divided by  3.  For example 

     10 ¸ 3 = 3r1,  7 ¸ 3 = 2r1,  4 ¸ 3 = 1r1  (all the remainders are equal to 1).

So  10, 7, 4, 1 ... etc are all members of the class  [1]  represented by  1.  Members of the same class are called congruent.  For example  10 º 4 (mod 3),  read as “10 is congruent to  4  modulo 3” and it means  10  and  4  have the same remainder when divided by  3.

a º b (mod m)   Û   (a – b) ¸ m   Û   a = b + km  for some integer  k

As you know,  “a ¸ m  gives a remainder of zero”  means  “a  is divisible by  m”.  Hence

a º 0 (mod m)   Û   a ¸ m

Congruency (for a given modulo m) is a type of equivalence relation.  We have these laws

Reflexivity:   For every integer a,  a º a Symmetry:    If  a º b,  then  b º a. Transitivity: If  a º b  and  b º c,  then  a º c.

These properties are similar to ‘=’.  We also have some very neat arithmetical laws.

Suppose  a º b (mod m)  and  c º d (mod m).  Then      a + c º b + d  (mod m)      a – c º b – d  (mod m)          ac º bd      (mod m)

For a given number  n = ...ABCDEFG,  we can write  n = 1000x + y   where  x = ...ABCD,  y = EFG.  With the above laws, modular arithmetic helps simplify calculations and provide powerful insights.  For example, in modulo 8,

         10 º 2,  100 º 10² º 2² º 4,  1000 º 10 ´ 10²  º 2 ´ 4 º 0.  Hence

         n = 1000x + y  º  0×x + y  º  y.

This explains the divisibility test by  8:  To see if a number is divisible by  8, we just need to look at the last  3  digits  y = EFG.

Test for divisibility by 7

     Using modulo 7,  10 º 3,  100 º 3² º 2,  1000 º 3 ´ 2 º 6 º -1.

     n = 1000x + y º  -1×x + y º  y – x.  Thus

     n ¸ 7   Û   n º y – x º 0   Û   x º y   Û    x – y ¸ 7.  We have the rule

n ¸ 7   Û   ...ABCD º EFG (mod 7)

This means that a number is divisible  7  if (and only if) after breaking off the last three digits, both resulting pieces have the same remainder when divided by  7.

Example 1

       For 12 516:  12 º 5  and  516 º 5 (mod 7).  So  12 516 ¸ 7.

Example 2

       For 654 321:  654 º 3  and  321 º 6 (mod 7).  So  654 321 not ¸ 7.

Example 3

       For 1 494 787:  787 º 3 º 1494 (mod 7).  So  1 494 787 ¸ 7.

       Alternatively, 1 494 – 787 = 707 ¸ 7.  So  1 494 787 ¸ 7.

Works like magic, doesn’t it?