[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

[AM_20151117] An “Unorthodox” Technique for Trigonometric Proof

Question

Introduction

     When proving trigonometrical identities, one usually starts from the “more difficult” side and try to work towards the other side.  The above identity looks like a tough nut to crack.  Both sides look equally complicated.  Where do we even begin?

     Here is one way to “cheat”.  Starting from, say, the LHS, we multiply the RHS expression and also multiply by its reciprocal i.e. dividing by the same amount.  It is like using a magic wand to create something out of nothing (无中生有 in Chinese), but doing so does not change the value of the LHS expression.  Now we do not touch the part that is equal to the RHS (highlighted in yellow below), but we try to find a way to cancel away the other stuff, as shown here.

Solution

Remarks

     In the third step, I had replaced  cos²A  with  1 – sin²A  and  sin²B  with  1 – cos²B.  This leads to the required cancellation and we are left with the yellow patch, which was never touched since the first step and it is the RHS.  This completes the proof.

     Just as in martial arts where deadly opponents require deadly strokes to counter them, evil questions require “unorthodox” techniques.  Even though most people would not have thought of it, all the steps presented above are actually legitimate.  This is because at every step, the equality is preserved.  All the “=” are really equal, and it’s legit (either work hard or you might as well quit), although my “can’t touch this” tactic seems a bit clairvoyant.

. 

Heuristics Used

H04. Look for pattern(s)

H05. Work backwards

H08. Make suppositions

H09. Restate the problem in another way

H10. Simplify the problem

H11. Solve part of the problem

H13* Use Equation / write a Mathematical Sentence

Suitable Levels

* GCE ‘O’ Level Additional Mathematics

* other syllabuses that involve proof of trigonometric identities

* anyone who loves mathematical challenges

[IB-HL_FTPR20150402] Periodicity cos a fortiori

     In this article, I give a rigorous proof of the period of cosine functions, using an a fortiori argument, signaled by the use of the words “in particular”.  When something is generally true for, say, all real numbers, it is “all the more” true for a particular case of a real number like zero.  I use this logic to nail down the answer.

Question

Solution

Suitable Levels

* revision for IB Mathematics HL / SL

* other syllabuses that teach trigonometry

[Pri20150330CPF] How to #Compare #Fractions

Comparing Positive Fractions

     How do you compare positive fractions, which are taught in primary (elementary) school?  For example, which is bigger:  ⁵/₆  or  ³/₄ ?

The “orthodox” method is to put them both to a common denominator.  The Lowest Common Multiple (LCM) of  6  and  4  is  12.  Multiplying the left fraction by  ²/₂  and the right fraction with  ³/₃  gives, respectively,  ¹⁰/₁₂  and  ⁹/₁₂.

Since  ¹⁰/₁₂  >  ⁹/₁₂,  we conclude that  ⁵/₆  >  ³/₄.

Another Method

     Here is a “short-cut” that I learned from a schoolmate in primary school.  Basically you “cross-multiply”: multiply the left numerator with the right denominator, and multiply the right numerator with the left denominator, and then compare the products so formed.  That will give you the correct inequality or equality sign (viz. ‘<’, ‘=’ or ‘>’).

As we can see, since  20 > 18,  we conclude that  ⁵/₆  >  ³/₄. 

     Does this method work?  Yes, definitely.  You can try it out with a few pairs of fractions and you can see for yourself that it is so.  Is this method legit?  Why does it work?    I give a formal proof of the method below.

Further Discussion

     Use the above method with care.  Some school teachers may not accept the method not because it is not correct, but it sounds “dubious” to them because they have not heard of it or they are not able to prove it for themselves.  Pupils can use this short-cut to give them a quick look-ahead to certain questions, and as a back-up to check their answer after using the Lowest Common Denominator method.  In questions that ask pupils to arrange a few fractions in ascending and descending order, this “crossing method” may give some speed advantage if done carefully.

     In primary school, pupils focus on positive fractions.  In secondary school, negative numbers and fractions are introduced.  Does the above trick work for negative fractions?  Was my theorem and proof above carefully phrased enough to cover the negative fractions? 

     Note that this method works for comparing two fractions at a time only.  Sometimes this cross-multiplying gives rather big numbers.  In that case, it is better to multiply each fractions by the LCM of their denominators.  Essentially this is the same as the orthodox method, except that we do not write the denominators.  Can the above proof be extended to cover this new short-cut?  What do you think?

[Maths History] #Newton's #proof that #pi is #transcendental ?

Article (from Quora, re: Alejandro Jenkins)
How do you prove that a number is a transcendental number?

Summary
Although the concept of "transcendental number" was not defined during Newton's time, Newton's Principia contained the germ of idea that seems to lead to a relatively easy proof of the idea that p  is transcendental.  Arnol'd described how Newton showed that the trajectory of planets cannot be expressed in terms of any polynomial function of time.