Questions about the world of GMAT Math from other sources and general math related questions.
ahistegt4
 
 

Combinatorics series I

by ahistegt4 Wed Nov 19, 2008 11:49 am

Guys, I have trouble solving a few difficult math question types, so I will post some questions that I made up myself.
I ll start with combinatorics:

Q: A dice with 10 sides ( :lol: do you care?!). You throw it 3 times. In how many ways the numbers add up to 12?

Please explain your answer constructively for everyones benefit.
ahistegt4
 
 

by ahistegt4 Sun Nov 23, 2008 7:26 am

Please can someone help with the above! :D
JonathanSchneider
ManhattanGMAT Staff
 
Posts: 370
Joined: Sun Oct 26, 2008 3:40 pm
 

by JonathanSchneider Wed Dec 10, 2008 10:11 pm

It took me about 5 or 6 minutes to list the possibilities an add them up: not a winning solution.

An easier path is to first ask: what is the lowest total we could get? what is the highest total we could get?
Notice that the lowest total will be 3 (this is from 1 + 1 + 1), while the highest will be 30 (from 10 + 10 + 10).
Notice moreover that there is only 1 way of constructing each of these scenarios, as all rolls must have the same value.

What I tried was to see if a pattern develops in counting the number of ways to total each subsequently higher number.

So I drew a sequence like this:

3 4 5 6 7 8 9 10 11 12 ... 28 29 30

Above the 3 and the 30 I placed a 1, representing the 1 way to achieve that outcome.
Next, I sought the # of ways to get a 4.
This must be done with 2 + 1 + 1. However, there are 3 ways we can arrange these rolls (2/1/1; 1/1/2; 1/2/1; or just call it 3!/2!). So, I placed a 3 above the 4 in the sequence above.
Next, I found the number of ways to get a 5 and the number of ways to get a six. These came out to 6 and 10, respectively.

At this point the pattern was:

1 3 6 10

This is a pattern of progressive addition. Start with 1. Add 2. Add 3. Add 4.
If you want to find the number of possibilities for rolling a 12, you need to move forward six more spaces, or +5+6+7+8+9+10 = 55.

I couldn't prove it to you without spending some more time to develop a proof, but that pattern is good enough for me. (And it happens to match the answer I came up with by brute force.)

I'm not sure I would have come up with that on the actual exam, but it works for now :)

[Note: There is an easier solution listed below. See Ron's comment from Feb 18. The beauty of that solution is that it focuses on pattern recognition, definitely an underrated skill for the Quant section of this test. Have a look!]
michael_shaunn_india
 
 

combinatorics

by michael_shaunn_india Thu Jan 15, 2009 3:01 pm

in order to find the number of times the three numbers add up to 12...

consider the following: (x^1+x^2+x^3+................+x^10)^3
x raised to powers from 1 to 10 coz there are 10 sides in all.the sum is raised to power 3 coz the three numbers from among 1 to 10 are added.if u see the pattern while multiplying the above to get the result..u will understand that it will represent all possible combinations of 3 numbers from 1 to 10 adding to 12..........represented in the expansion as coefficient of the term x^12.
................................................................................................................................................................................................................................................................
to get the answer...find the coeficient of the term x^12 in the expansion................i.e in x^3(1+x^1+x^2+................+x^9)^3=x^3*(1-x^10)^3*(1-x)^-3 which
is like finding the coefficient of x^12 in x^3*(1-x)^-3....
as can be seen after expanding x^3*(1-x^10)^3...i.e we are loking for the coeffecient of x^9 in (1-x)^3 which is given b the formula (n+r-1)! divided by (r)!*(n+r-1-r)!.....convert the above in combinational notation. for the given question....n=3,r=9.
THANK YOU.
tyang
 
 

by tyang Sun Jan 25, 2009 12:50 pm

Can you be more elaborate and explain this problem? I have no clue what you explained :shock:
michael_shaunn
 
 

by michael_shaunn Fri Jan 30, 2009 8:44 am

Hi Tyang
You won't face such problems in the exam as they are pretty lengthy sometimes.You can make out that the question was answered for a long time until i tried it.
Since you showed curiosity,I will try to help you understand once again.Though it make take quite a lot of time.
michael_shaunn
 
 

by michael_shaunn Fri Jan 30, 2009 9:14 am

Consider (x1+x2+x3)^2...............(x1 is x^1 and so on) which when expanded becomes x1.x1+x1.x2+x1.x3+x2.x1+x2.x2+x2.x3+x3.x1+x3.x2+x3.x3.......can you make out that by expanding the given algebraic expression we have obtained all possible combinations of digits 1,2 and 3 when taken two at a time.
The above expansion can be further written as x2+x3+x4+x3+x4+x5+x4+x5+x6 (I have just added the powers of each summesion term since the bases are the same)which is further simplified as x2+2.x3+3.x4+2.x5+x6.
Before i move forward,something important you need to observe....

(x1+x2+x3)^2=(x1+x2+x3)(x1+x2+x3).....when you try to simplify the RHS of the given equation you will actually club every power of x with every other power of x including itself in pairs of two ( check out:we got pairs of two b'coz we considered square of the algebraic expression)....I hope this clears the fact that why I used power of 3 to answer the actual question as we require to consider the sum of three terms and this sum is reflected as the power of the terms in the expansion of the algebraic expression.Also I considered the algebraic expression x1+x2+.......+x10 to include all the numbers on the dice so that on expanding the algebraic expression (x1+x2+........+x10)^3 we can get all the possible combinations of any three numbers from 1 to 10.

Again,check out the expansion of (x1+x2+x3)^2 in simplified form and the respective co-effecients.In the simplified form see that the co-efecient of x6 is 1.Now,ask a question:In how many ways two numbers out of 1,2 and 3 add up to give six when the dice numbered 1 to 3 is thrown twice.The answer is the co-effecient of x6 in the simplified axpansion which is 1.You can check it orally as well if you want.Only 3+3 will give 6 and no other combination is possible.THE number of x6 terms in the expansion is actually the co-effecient of x6 in the expansion which is nothing but the number of times two numbers from 1 to 3 when clubbed together give 6.
I hope that I am clear till here.
------------------------------------
IF U FACE ANY DIFFICULTY UNDERSTANDING TILL HERE,DO LET ME KNOW.THEN ONLY I WILL PROCEED WITH THE MORE DIFFICULT PART WHICH IS FINDING THE CO-EFFECIENTS OF THE RESPECTIVE TERMS IN THE EXPANSION.
AND FEEL FREE TO ASK ME WHATEVER YOU DIDN'T UNDRESTAND.I WILL TRY TO HELP YOU.
I AM GLAD THAT ATLEAST YOU SHOWED INTEREST IN THIS QUESTION.
MICHAEL_SHAUNN
 
 

by MICHAEL_SHAUNN Fri Jan 30, 2009 9:19 am

Consider (x1+x2+x3)^2...............(x1 is x^1 and so on) which when expanded becomes x1.x1+x1.x2+x1.x3+x2.x1+x2.x2+x2.x3+x3.x1+x3.x2+x3.x3.......can you make out that by expanding the given algebraic expression we have obtained all possible combinations of digits 1,2 and 3 when taken two at a time.
The above expansion can be further written as x2+x3+x4+x3+x4+x5+x4+x5+x6 (I have just added the powers of each summesion term since the bases are the same)which is further simplified as x2+2.x3+3.x4+2.x5+x6.
Before i move forward,something important you need to observe....

(x1+x2+x3)^2=(x1+x2+x3)(x1+x2+x3).....when you try to simplify the RHS of the given equation you will actually club every power of x with every other power of x including itself in pairs of two ( check out:we got pairs of two b'coz we considered square of the algebraic expression)....I hope this clears the fact that why I used power of 3 to answer the actual question as we require to consider the sum of three NUMBERS (from 1 to 10) and this sum is reflected as the power of the terms in the simplified expansion of the algebraic expression.Also I considered the algebraic expression x1+x2+.......+x10 to include all the numbers on the dice so that on expanding the algebraic expression (x1+x2+........+x10)^3 we can get all the possible combinations of any three numbers from 1 to 10.

Again,check out the expansion of (x1+x2+x3)^2 in simplified form and the respective co-effecients.In the simplified form see that the co-efecient of x6 is 1.Now,ask a question:In how many ways two numbers out of 1,2 and 3 add up to give six when the dice numbered 1 to 3 is thrown twice.The answer is the co-effecient of x6 in the simplified axpansion which is 1.You can check it orally as well if you want.Only 3+3 will give 6 and no other combination is possible.THE number of x6 terms in the expansion is actually the co-effecient of x6 in the expansion which is nothing but the number of times any two numbers from 1 to 3 when clubbed together give 6.(Try understanding this as its vital to your further understanding)
I hope that I am clear till here.
------------------------------------
IF U FACE ANY DIFFICULTY UNDERSTANDING TILL HERE,DO LET ME KNOW.THEN ONLY I WILL PROCEED WITH THE MORE DIFFICULT PART WHICH IS FINDING THE CO-EFFECIENTS OF THE RESPECTIVE TERMS IN THE EXPANSION.
AND FEEL FREE TO ASK ME WHATEVER YOU DIDN'T UNDRESTAND.I WILL TRY TO HELP YOU.
THANKS!!
MICHAEL_SHAUNN
 
 

THE TRICKIEST QUESTION IN GENERAL MATHS SECTION EVER.

by MICHAEL_SHAUNN Fri Jan 30, 2009 9:24 am

IF ANYONE ELSE HAS ANY OTHER SOLUTION THEN DO LET ME KNOW.
RonPurewal
Students
 
Posts: 19744
Joined: Tue Aug 14, 2007 8:23 am
 

Re: Combinatorics series I

by RonPurewal Wed Feb 18, 2009 9:19 am

ahistegt4 Wrote:Guys, I have trouble solving a few difficult math question types, so I will post some questions that I made up myself.
I ll start with combinatorics:

Q: A dice with 10 sides ( :lol: do you care?!). You throw it 3 times. In how many ways the numbers add up to 12?

Please explain your answer constructively for everyones benefit.


making an organized list here is really not that bad, and it can easily be done within two minutes.
just arrange it by first throw.
IN ANY PROBLEM THAT OBVIOUSLY HAS TOO MANY STEPS TO "GRIND", START LOOKING FOR PATTERNS.
THEY WILL BE THERE.
PERIOD.

first throw = 10 --> second + third throws = 2. there's 1 way to do this (i.e., 1, 1).
first throw = 9 --> second + third throws = 3. there are 2 ways to do this (i.e., 1, 2 and 2, 1).
first throw = 8 --> second + third throws = 4. there are 3 ways to do this (i.e., 1, 3; 2, 2; and 3, 1)
the pattern is clear.
there will be four ways if the first throw is 7; five ways if the first throw is 6; etc.
all the way down to ten ways if the first throw is 1.
1 + 2 + 3 + ... + 10 = 55.
done.

pattern recognition is king.
JonathanSchneider
ManhattanGMAT Staff
 
Posts: 477
Joined: Wed Dec 12, 2007 5:40 am
Location: Durham, NC
 

Re: Combinatorics series I

by JonathanSchneider Thu Feb 19, 2009 10:38 am

One final thought on this problem:

There is actually an even SIMPLER solution, though it requires a conceptual leap from the start:

We have a total of 12 "points" to assign to the three rolls. Each roll has a minimum value of 1, meaning that 3 points are already assigned (a roll cannot yield a zero). Thus, we only have 9 remaining "points" to assign. How many ways can we distribute these nine points? Visualize a row of 9 P's and 2 D's, where P = point and D = divider. The dividers signal how we break up the P's into three groups. We just need to count the number of ways that we can arrange these P's and D's:

P P P P D P P D P P P = one possible outcome. (This would signal that we assign 4, then 2, then 3 additional points to the rolls.)

The result? A simple combination. We have 11 total items, including 9 P's and 2 D's. So, the result will be 11!/(9!2!) = 55.