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 = ²C₁ = 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   ⁷C₃ = 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 ¹ / _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  ⁴P₄  = 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 = ³C₁ = 3

Number of ways to choose the “lucky” 2 ladies                = ⁴C₂ = 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.

³C₂ = 3 pairs of men.  Thus for the case of 3 couples, the calculation is:

          3 x (2 x 3 – 2) – ³C₂ = 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) – ¹³C₂ = 247 ways.

         

FYI, the general formula is

          n x (2n – 2) – ⁿC₂

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 M₁ and M₂, they form one entity.  There are ³C₂ x 2!

= ³P₂ = 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! / ₅).  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 ⁶C₂ = 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

 

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  x²  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)  =  x² + 2x – 1  =  x² + 2x + 1² – 1² – 1  =  (x + 1) ² – 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.  R_g = [-2,` \oo `).

So what now?

     With the two-stage method, suppose now we have

                  x ` \in ` R_g

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.                            R_fg = [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  R_fg = [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.

JCCDQBHWH_FN014(c) Condition for Composite Functions

[original source unknown]

Introduction

     This (part of a) question is taken from a certain book sold in Singapore which did not credit the original sources, so I do not know which junior college or which year it is taken from.   This is a common type of question regarding condition for the existence of composite functions, with a little twist.  Many students do not feel confident solving this kind of question, which tests one’s understanding of concepts besides algebraic manipulation.  I shall show you how.

     Note that composite functions are written with a right-to-left convention i.e. the function on the right comes first.  That means in the function  gf,  f  is applied first, then g.  This seems counter-intuitive.  Think of it like this:  gf(x)  means  g(f(x))  by definition.  Start with  x.  First we apply  f.  This  gives  f(x)  i.e.  f( )  wraps around the  x.  Next, we apply  g,  so we take g( )  and wrap it around  f(x)  to get  g(f(x)).  This is like putting on a shirt/blouse and then putting on a coat.

     As usual, metacogntion and heuristics are very important for solving this question.

Stage 1:  Understanding the Problem

What is this (part of a) question about?

Condition for existence composite functions, (domain) restriction of functions

What is the question asking?

Find the least value of  k  and the value of  a  so that the function  gf  exists.

Stage 2:  Planning the approach

Have you solved a similar problem before?  How was it solved last time?

Yes, it was solved by considering the condition for existence of  gf,  interpreting their meaning, and using appropriate inequalities.  Use the “thinking forward” heuristic: keep asking “what does this mean?”  and “So what? ”.

What is different this time?

There is an additional  “x  not equal to something”  type of condition.

Do you think the same tactic can work?

Maybe.  I can try.

Stage 3:  Executing the plan

What does it mean for the composite function  gf  to exist?

It means the range of  f  (the first function)  is contained in the domain of  g.

Write:  R_f ` \subseteq ` D_g.  Here  f  means the new  f  with the restricted domain.

So what does this mean?

It means  f(x)  is a member of  the domain of  g

Write:  f(x) ` \in ` (1, ` \oo `)\{2}.   [all the numbers bigger than one, except the number 2]

So what does this mean?

It means  f(x) > 1  and  f(x) ` != ` 2.

which means  x² + 2x > 1  and  x² + 2x ` != ` 2.

figure 1 – working forward

We continue the line of reasoning using the technique of competing the square for the ‘>’ and ‘` != `’ inequalities.  We need to be careful when taking square roots.  Fortunately, in this situation, we know that  x + 1 > 0,  since  x > -1  (x being in the domain of f).  So we only need to consider the positive square root.  We end up with

                     x > -1 + ` \sqrt(2) `   and                  x ` != ` -1 +  ` \sqrt(3) `

Obviously,  a = -1 +  ` \sqrt(3) `  (the value that  x  is not supposed to be equal to).

The statement     x > -1 + ` \sqrt(2) `  actually implies that a whole plethora of statements

                           x > k  with  k = -1 + ` \sqrt(2) ` = 0.4142…

                           x > k  with  k = 0.5

                           x > k  with  k = 0.6

                           x > k  with  k = 1.1

                           x > k  with  k = 999

                           x > k  with  k = 9 999

                           x > k  with  k = 99 999

                           x > k  with  k = 1 000 000 000

                           … etc.

can be true.  Among these the least possible  k  is -1 + ` \sqrt(2) ` (of course!!!).

Stage 4:  Evaluation

Is it possible to check your answer?  How?

     We can store  X² + 2X  as a function.  For example, on the TI-84, we can store the formula into function variable Y₁.  We can numerically evaluate  Y₁(-1 + ` \sqrt(2) `) = 1  and  Y₁(-1 + ` \sqrt(3) `) = 2.  We can verify numerically that, for example,  Y₁(0.5),  Y₁(0.6159),  Y₁(1.3546) ,  Y₁(99)  … etc gives values greater than 1  i.e. values in the domain of  g.  We check through the above steps to make sure every step is correct and makes sense.

Stage 5:  Reflection

What did you learn from solving this question?

     I learned to make use of the condition  R_f ` \subseteq ` D_g  for composite function.

     I learned to work forward  by systematically refining the above statement.

     I remembered the “completing the square” technique learned from secondary school.

     I remembered being careful when dealing with square roots in inequalities.

     I learned to check my work using the calculator.

Anything else you have learned from this question?  Post your comments below.