Saturday, May 19, 2012

H2Maths VJC/2007/P2/Q9 The Power of Rephrasing




Introduction

     Today we discuss a question taken from one of the top junior colleges in Singapore’s 2007 preliminary examinations (final school internal examinations before the actual A-levels).  The seemingly difficult problems dissolve quickly using the right heuristics (rules-of-thumb / guidelines / problem-solving tactics).  Once the correct approach is determined, the calculation is simply a matter pressing buttons on the graphing calculator (e.g. TI-84 Plus or Casio fx-9860G).  This question can be tackled using heuristics.

     Try to guess what heuristic(s) will be useful in solving the above problem.  In a typical examination question, they will not tell you what topic or concepts are being tested in that question.  Try to determine what concepts are involved.

     Let’s tackle the question part by part.  As usual, we use the 5 step problem-solving process with metacognition (self-prompting, self-monitoring).




Part (i)

 



Part (i) Stage 1:  Understanding the Problem

What concept(s) is being tested?
     That seems to be something to do with probability …

Do you understand the question?  Can you put it in your own words?
When Ai Wan (爱玩 “loves to play”?) rolls the die for the eight time, he gets exactly three ‘6’ to win the prize.  What are the chances of this event happening?



Part (i) Stage 2:  Planning the approach

Is there a heuristic you can use?
     How about “9. Restate the problem in another way” …

So how do you rephrase the question?
     “win on 8th roll” means “two ‘sixes’ on the first 7 rolls” and “a ‘six’ on the 8th roll”.

How will you proceed?
Break down the problem into parts (“11. Solve part of the problem”).
     (1) find probability of “two ‘sixes’ on the first 7 rolls”
     (2) find probability of “a ‘six’ on the 8th roll” (this is easy.  Obviously  1/6)
Then multiply them together, since these are independent.

How do you write out probability of “two ‘sixes’ on the first 7 rolls” in symbols?
P(X = 2)

Think backwards:  What is X?  How do you define it?
X  is a random variable.  It is the number of ‘sixes’ in the first 7 rolls.



What distribution does it follow?  How do you know?
It follows a Binomial Distribution: Because there are only two outcomes: either you get a ‘six’, or you don’t.  There is a fixed number of trials and these are independent, giving a constant probability. 

So what’s the number of trials (n)?
There are 7 rolls, so seven.  Each roll is a trial.

What is the probability of “success” (p)?
One out of six.


Is this a probability distribution function (p.d.f. ) or a cumulative distribution function (c.d.f.)?  How do you calculate it?


This is just probability for a single value of  X, so it’s a p.d.f.  It can be found from the graphing calculator.  [ Or use the formula nCx px qn–x = 7C2 (1/6)2(5/6)5 ]

Part (i) Stage 3:  Executing the plan




Part (i) Stage 4:  Evaluating the answer

Does this answer feel correct?  Is it believable?
     Yes.  It’s quite small, which tallies with my intuition, as getting three sixes in 8 rolls is highly unlikely.  If I get an answer like 0.4 something, I might smell a rat.  If I get a probability that is less than 0 or more than 1, then I know for sure it’s definitely wrong.



Part (ii)

Remark

     This problem is related to the Geometric Distribution, which is not in the syllabus.  Nevertheless it is solvable using the knowledge contained in the syllabus, so it is within the student’s reach.

Part (ii) Stage 1:  Understanding the Problem

What concept(s) is being tested?
     probably probability again … maybe Binomial or something related

Do you understand the question?  Can you put it in your own words?
Ai Ying (爱赢 “loves to win”?) already has got 2 ‘6’ and 2 ‘1’.  That means she needs just one more ‘6’.  She needs to throw exactly four more times (no more and no less).  What are the chances of this happening?

Part (ii) Stage 2:  Planning the approach

Is there a heuristic you can use?
     “9. Restate the problem in another way” … but the problem still seems complicated because of the initial conditions (two “sixes” and two “ones” ) …

Is there a way to simplify the problem or another way to think about it?  Is there a feature about the situation … ?
     Ah!  Since all the trials are independent, what happens in the past does not affect the future.  This is the memoryless or forgetfulness property of the (Bernoulli) trials.  That means I don’t need to worry about the two “sixes” and two “ones”.  I can forget the past!  It is as though I can just start from a clean slate!

So what does it mean to say “Ai Ying needs to throw exactly four more times”?
     It means after throwing three more times, she does not get any six, and then she gets a six on the next throw.

How do you write this out mathematically?
P(S’, S’, S’, S)

What do you mean by S?  What is S’ ?
S  is the event of getting a ‘6’ in a roll of the die.  S’  means not getting a ‘6’.



Now, how do you proceed?

The chain of events can be broken down.  (“Split the problem into smaller parts”)
P(S) = 1/6P(S’) = 1 – 1/6 = 5/6.  Since the four events are independent, I can just multiply their probabilities  all together!  This is easy!

Part (ii) Stage 3:  Executing the plan

 

Part (ii) Stage 4:  Evaluating the answer

Does this answer feel correct?  Is it believable?
     Yes.  Again the answer is quite small, which tallies with my intuition.


Part (iii)



Part (iii) Stage 1:  Understanding the Problem


What concept(s) is being tested?
     Probability, Binomial Distribution and … er … rephrasing?
Do you understand the question?  Can you put it in your own words?
Ai Du (爱赢 “loves to win”?) cannot win in eight rolls, so he needs to roll some more.  What are the chances of this happening?

Part (iii) Stage 2:  Planning the approach

Is there a heuristic you can use?
     “9. Restate the problem in another way”

So how do you restate the question?
 “requires more than eight rolls of the die to win a prize” means “after 8 rolls, he does not get three ‘sixes’”.

Which means?
Which means “after 8 rolls, he gets only 2 or less ‘sixes’”.

How do you write the required probability mathematically?
P(D < 2)

Think backwards:  What do you mean by D?
D  is a random variable that counts the number of ‘sixes’ within 8 rolls.


What distribution does it follow?  Why?
Binomial Distribution, again.  Same reasons as in part (i).

So what’s the number of trials (n)?  What is the probability of “success” (p)?
n = 8,  p = 1/6.


Is this a probability distribution function (p.d.f. ) or a cumulative distribution function (c.d.f.)?  How do you calculate it?
Because it is a “<” probability, it’s a c.d.f, which can be found from the graphing calculator, or checking tables.  [ Calculation by hand is possible, but tedious.  Also, there is a recurrence formula that can help a bit, but this is out of syllabus. ]

Part (iii) Stage 3:  Executing the plan
 

Part (iii) Stage 4:  Evaluating the answer

Does this answer feel correct?  Is it believable?
     Yes.  The answer is high, which tallies with my intuition.  Since it is hard to win, my gut feel is that you would very likely need more rolls of the die to win.


Stage 5:  Reflection

What did you learn from solving this problem?
     I learned that the memoryless (forgetfulness) property of Bernoulli trials (i.e. the type of trials involved in the Binomial distribution) is useful to allow me to disregard past events and simplify the problem.
     I learned that whenever I encounter a maths problem that seems difficult, I should not despair.  I should try the following heuristics:-
     * rephrasing the problem (heuristic 9)
     * breaking the problem into smaller parts (heuristic 11)
     * writing in mathematical notation (heuristic 13)
     * thinking backwards (heuristic 5)
     * simplify the problem (heuristic 10)
Rephrasing is particularly useful, as it helps to tackle all three parts of this exam question.  Even though part (ii) was on the fringes of the syllabus (just barely in the syllabus), we could still solve it by using heuristics, metacognition and using what we know already.

Conclusion

     Heuristics and metacognition will guide you when you seem to be in uncharted territory.  Use what you know (basic probability) to tackle what you do not know.  Do not be afraid.  Have faith.  May the Heuristics be with you!




 







Monday, April 23, 2012

JCCDQBHWHCB037(ii) Combinatorics : Grouping and Insertion Method




Introduction

     This question is from a source that does not credit the original source.  In the original question was poorly worded.  It did not have the words “the letters of the word”.  Instead of “each vowel must be separated”, it said “a vowel must be separated”, which is might mean there is just one such instance.  This is ambiguous.  I have taken the liberty to rephrase some parts of the question to make its meaning clearer.  In this article, I shall discuss only part (ii) of this question.

Stage 1:  Understanding the question

What is the given in the problem?  Can you organise the information?
     Though not absolutely necessary, it is helpful to draw a diagram that separate the letters into vowels and consonants and write the stack up the same letters in columns.




     There are  5  vowels (of which  O is repeated)  and  6  consonants (of which  N  and  S  are repeated).

Can you explain the problem in your own words?
     The letters of the word ‘CONNOISSEUR’ are re-arranged, which means that all the 11 letters are used.  Each vowel must be separated from another with exactly one consonant, which means that the letters must contain the pattern  “v c v c v c v c v” (where v = vowel, c = consonant).  Important: Note that the question does not say that the first letter must be a consonant.



Stage 2:  Planning

Have you seen a similar problem before?
     Yes, but this looks a bit more challenging.  There are more possibilities as first letter need not be a consonant.

What heuristics can you try?
     ·  Solve part of the problem
     ·  Split the problem into smaller problems

What topic-specific tactics can you try?
     The “v c v c v c v c v” pattern can be treated as a group (Grouping Method).  Since there are six consonants, there are two more “c”s (consonants) in the full pattern.  This looks like a problem that can use the Insertion Method.

Stage 3:  Execution



The number of ways to insert the group = 3C1 = 3
     [these are the patterns “ccvcvcvcvcv”, “cvcvcvcvcvc” and “vcvcvcvcvcc”  ]

For each pattern,
     the vowels can be arranged in  5! / 2!  ways (division because there are 2 ‘O’)
     the consonants can be arranged in  6! / 2! 2!  ways (division because of 2 ‘N’ and 2 ‘S’)

Hence the total number of ways is


Stage 4:  Evaluation

Is the answer correct?
     Yes, the answer is correct.



Stage 5:  Reflection

What have we learned by solving this problem?
     We have learned once again that heuristics and metacognition are useful in solving mathematical problems.  Specifically, we have used the following heuristics:-
          ·  Drawing a diagram
          ·  Solve part of the problem
          ·  Split the problem into smaller problems

     We have also used the following techniques that are useful for combinatorical problems:-
          ·  Grouping Method
          ·  Insertion Method
          ·  Division Method (for dealing with repeated letters)

     It is also important to understand the problem correctly and not make unfounded assumptions.  If the wording is not clear, you may want to rephrase it.




Friday, April 6, 2012

JCCDQBHWHCB014 Combinatorics : Permutations & Multiplication Principle



Suggested Approach and Solution:-

     Since the order is important, we use permutations (which are just multiplications) instead of combinations.  No over-counting or division is involved.

 

The guys can be chosen and arranged in 10P3 = 10 x 9 x 8 = 720 ways.
The gals can be chosen and arranged in 6P3 = 6 x 5 x 4 = 120 ways.
Total number of ways = 720 x 120 = 86 400 ways.

JCCDQBHWHCB009(ii) Combinatorics : Case-by-case Analysis (Addition Principle)



Suggested Approach and Solution:-

     For questions with special conditions, a good approach is to consider to the special conditions first.  It matters whether the last digit is a ‘3’ or not.  This is a complication that is handled by a Case-by-case Analysis and then totaling up the number of possibilities.

Case 1: 3 is the last digit

 

If 3 is the last digit, we have 1 choice (i.e. Hobson’s choice) for the last digit.  The first digit must be either a 1 or a 5 i.e. 2 choices.  The remaining 5 digits can be filled in  5P5 = 5!
= 5 x 4 x 3 x 2 x 1 = 120  ways.
Number of ways for this case = 2 x 5! = 240 ways.

Case 2: 3 is not the last digit

 

In this case, the last digit must be either a 1 or a 5 i.e. 2 choices.  Because these digits only occur once, the first digit will definitely be different from the last digit.  So we need not worry about the first-digit condition as it is automatically satisfied.  The front 6 digits can be filled in
          6! / 2! = 360
We divide by 2! because the digit 3 is definitely repeated.
Number of ways for this case = 2 x 360 = 720 ways.

The total number of ways = 240 + 720 = 960.




JCCDQBHWHCB007(ii) Combinatorics : “Choose, then Automatically fill” technique



     The question says “the captain must stand between the two youngest players” which I interpret literally to mean: not necessarily directly next to each other, but there can be intervening players.  Although I suspect that the one who set this question might have meant that the captain is supposed to be in between directly next to the two youngest players, I shall attempt the question according to its prima facie meaning.  Later, I shall consider what if the captain and two youngest players are together next to one another with the captain in the middle.

Suggested Approach and Solution:-


 

Number of rows to choose from = 2

The condition that “the captain must stand between the two youngest players” seems difficult, because there can be one or more intervening players.  Generally we do not favour complicated case-by-case analyses.  The good news is that we can use a “choose, then automatically fill” technique to tackle this.  Within the row with the captain, there are 5 positions and we choose 3 of them.  Then we automatically fill them with a youngest player, the captain and then the other youngest player.  The number of ways to do this is  5C3 = 10.

Number of ways the two youngest players can swap around = 2!.
Number of ways the rest of the players can shuffle around   = 7!.

Total number of ways = 2 x 5C3 x 2! x 7! = 201 600.



What if …
     What if the captain is in between directly next to the two youngest players?
 

Number of rows to choose from = 2

     If the captain is in between and directly beside the two youngest players, we treat these 3 players as a unit.  There are 3C1 = 3 ways to position this group within the row.  Note that within this group, the two youngest players can still swap around while the captain stays in their middle.  Everything else is the same as above.

Total number of ways = 2 x 3C1 x 2! x 7! = 60 480.


JCCDQBHWHCB007(i) Combinatorics : Choosing with special conditions



     This sort of question has appeared in the GCE ‘A’ levels before.  For questions with special conditions, a good approach is to consider to the special conditions first.

Suggested Approach and Solution:-
 

Number of ways to choose the young player = 2C1 = 2
The captain must be in, so two vacancies have been taken up and there are 3 left.  These places must be filled from the 7 eligible other players (excluding the captain and the two youngest players).  There are   7C3 = 35  ways to do this.  The total number of ways is
          35 x 2 = 70

JCCDQBHWHCB002(iii) Combinatorics : Partitioning and team shuffling


Suggested Approaches and Solutions:-

     Though not compulsory, a diagram is very useful to help visualise the situation.



There are three subgroups, with sizes 1,1,2.  Let’s call them teams A, B, and C.  Within each team, the order of individual members does not matter.  However, human beings are deemed to have distinct identities.

Now, how many ways are there to partition the ladies into the above three teams?  Think of an equivalent problem (another heuristic): Imagine the ladies lining up and then put on T-shirts, with letters A, B, C, C for the teams.  So how many words can you spell with four letters, two of which are repeated?
Number of ways to partition the ladies into the three teams = 4! / 2!

Number of ways to put the men into the teams                     = 3!

Note that teams A and B, which have the same number of people, are interchangeable (the team names do not matter, but rather who gets teamed up with who), so we need to divide by 2!
So the answer is
          4! / 2! x 3! x 1 / 2! = 36


Reflection
Are there other methods or ways to think about this problem?
Yes!  Having different methods that give you the same answer increases your confidence that the answer is correct.  If you have different answers, try to find out why.  You might learn something valuable!

Method 2 (“Phantom” or “Joker” method)
     Imagine that, in lieu of the missing guy, we have a ghost (or a Joker card).  We try to pair up the ladies with the men (or ghost) as usual, and there are  4P4  = 4! = 4 x 3 x 2 x 1 = 24 ways to do this.  The lucky/unlucky lady who got the ghost or Joker card joins one of the 3 actual men.  So there are 24 x 3 = 72 ways … Ooops!  Why is this not the same as the above method?  That is because in each case, the other lady who ended up with the same guy could have been the one that had the Joker card and this possibility was already counted.  That means we have uniformly over-counted by exactly a factor of 2! = 2, so we must divide by this number.  Thus the correct calculation using this approach is
          4! x 3 / 2! = 36

Method 3 (MCP method)
     Here I shall use a Multi-stage Combination Product method.  Just kidding.  There is no such term.  Actually MCP means “Must Choose Properly” for Male Ch….. P...  We first arrange the guys in order.

Number of ways to choose the “lucky” guy with 2 ladies = 3C1 = 3
Number of ways to choose the “lucky” 2 ladies                = 4C2 = 6
Number of ways to shuffle the other 2 ladies                    = 2!   = 2
Total number of ways = 3 x 6 x 2 = 36




JCCDQBHWHCB015 Combinatorics : Conditional Over-counting



Introduction

     This question is particularly challenging, because it does not conform to any of the usual types of problems taught at ‘A’ level.  However, we can still use the following problem solving heuristics:-
     · drawing a diagram
     · considering a simpler problem first

Suggested Approach and Solution:-

     Consider first the case for 3 couples and draw a diagram with arrows.

Suggested Approach and Solution:-

     We use the same problem-solving tactics as for question 11.  Consider first the case for 3 couples and draw a diagram with arrows.

 

We now discover that this problem is a little more complicated than that of question 11. 
Each of the 3 men has arrows coming out to 2 x 3 – 2 = 4 persons (everyone except himself and his wife).  So there are 3 x (2 x 3 – 2) = 12 arrows.  There is double-counting (arrows in both directions), but only among the men.  So we need to subtract the number of lines connecting i.e.
3C2 = 3 pairs of men.  Thus for the case of 3 couples, the calculation is:
          3 x (2 x 3 – 2) – 3C2 = 12 – 3 = 9
We verify by counting from the diagram that this is correct.

For 13 couples, we have
          13 x (2 x 13 – 2) – 13C2 = 247 ways.
         
FYI, the general formula is
          n x (2n – 2) – nC2

JCCDQBHWHCB019 Combinatorics : Circular Permutations



Suggested Approach and Solution:-

     Draw a diagram.  Let’s assume that the special woman (W*) is at the 12 o’clock reference position.  [If not, we can always rotate our heads or rotate the table so that she is.] 

 

Together with the two lucky(?) men M1 and M2, they form one entity.  There are 3C2 x 2!
= 3P2 = 6 ways to choose and arrange these two men to sit besides this special woman.  The other 4 persons can arrange themselves relative to the reference entity in 4! = 24 ways (this is same as (5 – 1)! or 5! / 5).  Hence the number of ways = 6 x 24 = 144.



JCCDQBHWHCB011(i) Combinatorics : Uniform Over-counting (Division Principle)



     [ As an ice-breaker game, this is stupid!  Anyway … ]

Suggested Approach and Solution:-

     If the problem seems difficult, try a simpler problem first.  This is a useful heuristic / tactic, especially for permutation and combination problems.  Let’s say there are only six students.  Draw a diagram (a heuristic) with dots representing students, and arrows from each dot to other dots except the two dots beside it.  You will soon realize that each arrows goes in two directions.  This means there is over-counting by a factor of 2.  Whatever answer you get by counting the arrows forward must be divided by 2.


 

How many arrows are there?  (Heuristic: Think of an equivalent problem).  For each of the 6 dots, there are 6 – 3 = 3 arrows coming out (minus 3 because excluding itself and two beside it).
So the number of arrows is 6 x (6 – 3) = 18.  But we don’t really care about the direction of the arrows.  Because of the double-counting (and this is uniformly true for every pair of arrows), we must now divide this answer by 2 to get 9.  We can verify by counting from the diagram that this answer is correct.

Another approach: there are 6C2 = 15 possible line segments (connections between two dots).  But we don’t count those on the perimeter of the hexagon, so we subtract 6 (because there are six sides all round the hexagon).  This gives 15 – 6 = 9.

For 17 students, the answer is: 17 x (17 – 3) / 2 = 119


 

Sunday, February 26, 2012

JCCDQBHWH_FN021(b) Range of Composite Functions

[original source unknown]



Introduction

     This question is from the usual book which did not credit the source.  It comes from some unknown junior college in an unknown year.  It is a challenging question because most students are poor at finding the range of composite functions.  Furthermore, this question has a little twist: you are given the range of the composite function, but you are required to solve for something.  So you need to, in a way, work backwards and/or use inequalities (another weak point for many students).

     Students are reminded of the right-to-left convention for functions in JC as well as GCE ‘A’ level examinations.  This means in ‘fg’ the  g  is done first before the  f.  There are some university professors who use a left-to-right convention, but here we do not.  So take note.

     Again metacogntion and heuristics are very important and I will illustrate their use.


Stage 1:  Understanding the Problem

What is this (part of a) question about?
range of composite functions, solving for unknown

What is given in the question?
The range of  fg.

What is the question asking for?
The value of  k  that leads to the given range.


Stage 2:  Planning the strategy

What heuristics do you think can be used for this question?
· Working forwards (considering the meanings, asking “so what?” “what next?”)
· Setting up equation/inequality
· Working/thinking backwards
· Consider equivalent expressions or rephrasing the problem

Can you recall the definition of the range of a function?  The range of a composite function?


Stage 3:  Execution

Any observations that can make your job simpler?
     Yes.  Observe that  g(x)  is a quadratic with positive  x2  coefficient.  So this is a parabola that looks like a happy smile.  To locate the minimum point, we can complete the square (a technique learnt in secondary school).
     g(x)  =  x2 + 2x – 1  =  x2 + 2x + 12 – 12 – 1  =  (x + 1) 2 – 2
when  x = -1,  g(x) = -2.  The minimum point is (-1,-2).  So the range of  g  is all the
numbers from  -2  upwards.  i.e.  Rg = [-2,` \oo `).

So what now?
     With the two-stage method, suppose now we have
                  x ` \in ` Rg
That means?
                  x > -2
That means?
                  x + k + 1 > -2 + k + 1
Why do you do that?
     I want to slowly manipulate the LHS to get  ln(x + k + 1)  which is  f(x).  Continuing,
                  ln(x + k + 1) > ln(k – 1)
                                f(x) > ln(k – 1)
i.e.                            Rfg = [ln(k – 1), ` \oo `).
Why is there no switching in the inequality sign?
     The slope of the graph of  the natural logarithm is always positive (albeit getting less steep for increasing  x).  So applying  ‘ln’  on both sides does not change the inequality.

What is the clue again?
     We are told that  Rfg = [ln 3, ` \oo `).  Aha!  *epiphany*  *light bulbs flashing*
ln(k – 1) must be equal to ln 3!!!  This can be solved easily!


figure 1 – working forward and backwards

Stage 4:  Evaluation

Is the answer correct?
     Substituting  k = 4,  we see that    ln(x + k + 1) =  ln(x + 5)  and with  x > -2,  this will be  > ln 3  as given in the clue.

And why  x > -2?
     This is because g(x) > -2, which we knew  from completing the square.  We treat the  ‘g(x)’  as the  ‘x’  when applying  f,  because this is what  fg(x)  really means.



Stage 5:  Reflection

What did we learn from solving this question?
     We used metacognition to do self-monitor and self-questioning during the 5 stage problem-solving process.
     We used the following heuristics.
· Working forwards (considering the meanings, asking “so what?” “what next?”)
· Setting up equation/inequality
· Working/thinking backwards
· Consider equivalent expressions or rephrasing the problem
     We learned to apply the definition of the range of fg.  There are two possible methods: the one-stage method and the two-stage method.  The latter is usually better.
     In the two-stage method, the range of  fg  is found by first finding the range of  g  and then applying the function  f  to it.  After the first step of finding the inequality for  g(x),  we can simply use  x  in the formula for  f.  How?  We set  x  to be in the range of  g(x) from the previous step,  then slowly manipulate the inequality until the expression for  f(x)  appears.  This will give us the range of  fg.
     From the formula for the range of  fg,  we learned how to make use of the given clue to work backwards to find the unknown k.
     Difficult questions can be tackled by thinking systematically and logically, and using heuristics and metacognition.  Mathematics is hard, but it is fun after you have learned it.  If you have really learned it, you become more powerful because you can use the same technique to solve all kinds of problems in future.

Any of your own reflections?  Please post in the comments below.