[H2PCRP20150406] Colouring The Pentagon (Combinatorics)

Introduction

     This is a question suitable for the mainstream Junior College students taking H2 mathematics, but is some primary school olympiad question from somewhere.  Whatever!  Mathematics is for everybody, young and old.  Anybody can solve this problem if  s/he makes observations and uses the right approach and thinking skills.

An Incisive Insight

     Although this pentagon is not a regular pentagon, the colouring scheme depends just on the order of colours on the edges.  We can start from one edge and see what colours are possible.  And then we can rotate the colouring scheme around.  [ We are breaking down and simplifying the problem. ] 

     Fiddling around with various possibilities, you might realise that:-

·  you cannot have three of the same colour going round the pentagon

·  you cannot have three sets of pairs of edges with the same colour.

·  you cannot two single colours and one double colour

There must be one single colour and two pairs of doubled colours.  All colouring schemes will have a  “12123”  colouring pattern going around in a loop.  The diagram below shows an example where colour 1 = yellow (Y), colour 2 = red (R)  and colour 3 = blue (B).

Do we need to consider a “21213”  pattern?  If  “12123”= “YRYRB”, we can later reassign colours, swapping R and Y to give 1=R and 2=Y and then “12123”=“RYRYB”.  So we have got that covered.  Let us worry about the reassignment later. 

Solution

     Observe that the position of the “3” (the single colour) can be rotated round the edges of the pentagon in  5  ways.

     Observe also that there are  3! = 3 ´ 2 ´ 1 = 6  ways to shuffle the colours i.e. assign colours 1, 2 and 3  to  Y, R and B.

The above two processes (rotation and shuffling) are independent of each other.  Rotation of the single colour can be done with or without the shuffling of colours.  Hence we can use the Multiplication Principle and calculate

          the total number of ways = 5 ´ 6 = 30.

Tada!

Heuristics Used

H02. Use a diagram / model

H04. Look for pattern(s)

H09. Restate the problem in another way

H10. Simplify the problem
H11. Solve part of the problem

Suitable Levels

* GCE ‘A’ Level H2 Mathematics

* IB Mathematics HL / SL

* Primary School Maths Olympiad

* other syllabuses that include combinatorics

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 = ³C₁ = 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.

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 ¹⁰P₃ = 10 x 9 x 8 = 720 ways.

The gals can be chosen and arranged in ⁶P₃ = 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  ⁵P₅ = 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.

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

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.