How many ways can the number 3 0 be written as an ordered sum of 2s and 5s?
Details and assumptions
There are four ways to write 12 as an ordered sum: 2 + 2 + 2 + 2 + 2 + 2 = 1 2 , 2 + 5 + 5 = 1 2 , 5 + 2 + 5 = 1 2 , and 2 + 5 + 5 = 1 2 . The ordered sum can use 0 5's, and it can also use 0 2's.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice.I was stupid enough to define the recursion
F ( n ) = F ( n − 2 ) + F ( n − 5 )
where F ( n ) denotes the number of ordered ways to write n as an ordered sum of 5 s and 2 s.Using this repeatedly,we get,
F ( 3 0 ) = F ( 2 0 ) F ( 1 7 ) + + 2 F ( 1 9 ) + 2 F ( 1 6 ) + 2 ( F ( 1 9 ) + F ( 1 6 ) + F ( 1 8 ) ) + 2 F ( 1 3 ) + F ( 1 0 )
Then we compute F ( x ) upto x = 2 0 and then plug in the values.
Sorry for writing here.But I see in the details and assumptions section, there are two same ways among the four ways to write 12 as an ordered sum. There are two 2+5+5=12 `s.
One of them is 5+5+2=12. :-)
But I think users including me still can understand it. ...
Log in to reply
Yeah he is right. Staff please correct the question.
Easiest solution there,
Let us consider the possible number of fives we can have in our ordered sum. We cannot have an odd number of fives because that would leave an odd number, which cannot be expressed as a sum of twos. Therefore, we can only have an even number of fives. We can have 0 , 2 , 4 , or 6 fives in our ordered sum.
If we have no fives in our ordered sum, there is only 1 ordered sum possible, which is an addition of 15 twos.
If we have 6 fives in our ordered sum, there is also only 1 ordered sum possible, which is the addition of the 6 fives.
Now let's look at the case of 2 fives. If we have 2 fives in our ordered sum, then we have 10 twos. Imagine our ordered sum is a row of numbers. 10 twos are lined up in a row, with gaps on either side of them. The gaps are spaces where the 2 fives can go. We need to choose 2 (not necessarily distinct) spots for the fives to go into. The number of ways to pick 2 spots is 2 ! ( 1 1 − 1 ) ! ( 1 1 + 2 − 1 ) ! = 2 ! 1 0 ! 1 2 ! = 6 6 using the formula for combinations with repetition.
Now we consider the case with 4 fives. In this case, there are 5 twos in a row, and 6 gaps where the fives can be placed. Using the formula for combinations with repetition again, we get 4 ! ( 6 − 1 ) ! ( 6 + 4 − 1 ) ! = 4 ! 5 ! 9 ! = 1 2 6 possible ordered sums.
Adding all these up, we get 1 + 1 + 6 6 + 1 2 6 = 1 9 4 possible ordered sums.
Clearly the number of 5's is an even number because the sum is 30 and that the other number to be used is also even, i.e., 2. Also the number of 5's is 6 or less. If there are six 5's, then there will be no two's. If there are four 5's, then there will be five two's. If there are two 5's, there will be ten two's. There will be fifteen two's for no 5's. Now we note that if there are x five's and y two's then the number of ways of arranging the x+y numbers will be
( x ! ) ( y ! ) ( x + y ) ! = ( x x + y ) .
Thus the total number of ordered sums are
( 6 6 ) + ( 4 9 ) + ( 2 1 2 ) + ( 0 1 5 ) = 1 9 4 .
By parity, any such sum will have an even number of 5s.
Then there are four cases: 1. no 5s: only one way to write 30 as a sum of only 2s. 2. two 5s: then there are ten 2s and two 5s. There are (10+2=) 12 places to put numbers, so 12 choose 2 = 66 ways to write 30 as a sum with two fives. 3. four 5s: similarly, then there are five 2s and four 5s. There are (5+4=) 9 places to put numbers, so 9 choose 4 = 126 ways to write 30 as a sum with four fives. 4. six 5s: only one way to write 30 as a sum of six 5s.
In sum, there are 1+66+126+1 = 194 ways to write 30 as an ordered sum of 2s and 5s.
Since there are only four ways of making up 30 with addition of factors of 2 and 5:
l c m ( 2 , 5 ) = 1 0
3 0 = 5 × 6 + 2 × 0
3 0 = 5 × 4 + 2 × 5
3 0 = 5 × 2 + 2 × 1 0
3 0 = 5 × 0 + 2 × 1 5
Therefore, the number of ways of 'ordering' each one can be looked at the different types of combination for a single number, say for instance we choose 5, for each equation we do 'number of 5s' choose 'total numbers'.
( 6 6 ) + ( 4 9 ) + ( 2 1 2 ) + ( 0 1 5 ) = 1 9 4
First, we find how many ways the number 3 0 can be written as an un-ordered sum of 2 s and 5 s.
Clearly, we need an even number of 5 s, or else we will need to add some number of 2 s together to make an odd number. If we have zero 5 s, we need fifteen 2 s; if we have two 5 s, we need ten 2 s; four 5 s and five 2 s; six 5 s and zero 2 s. Essentially, we just found the non-negative integer solutions to the linear Diophantine equation 5 ⋅ a + 2 ⋅ b = 3 0 , which are ( a , b ) = ( 0 , 1 5 ) , ( 2 , 1 0 ) , ( 4 , 5 ) , ( 6 , 0 ) . Clearly, we can't have a negative number of 2 s or 5 s, and so we are done. These solutions each represent an un-ordered sum of 2 s and 5 s which equals 3 0 .
Now we must order each sum. The number of ways to order a 2 s and b 5 s is ( a a + b ) , since we have a total of a + b spots to fill with numbers and choosing which a of those spots the 2 s fill produces a unique ordered sum.
Let S = ( 0 , 1 5 ) , ( 2 , 1 0 ) , ( 4 , 5 ) , ( 6 , 0 ) , which are the solutions from above. Our answer is then simply ( a , b ) ∈ S ∑ ( a a + b ) = ( 0 1 5 ) + ( 2 1 2 ) + ( 4 9 ) + ( 0 6 ) = 1 + 6 6 + 1 2 6 + 1 = 1 9 4 .
We can break the question into different cases:
(i) 6 fives and no twos
6 fives can be arranged in only 1 way. Hence, no. of ways is 1.
(ii) 4 fives and 5 twos
4 fives and 5 twos can be arranged in 4 ! 5 ! 9 ! = 126 ways.
(iii) 2 fives and 10 twos
2 fives and 10 twos can be arranged in 1 0 ! 2 ! 1 2 ! = 66 ways.
(iv) No fives and 15 twos
15 twos can be arranged in 1 way only.
Adding up the cases, we get 1+126+66+1=194 which is the answer.
The number 30 can be written as the sum of 5s and 2s in the following ways:
(I) 30 = 5 + 5 + 5 + 5 + 5 + 5
(II) 30 = 5 + 5 + 5 + 5 + 2 + 2 + 2 + 2 + 2
(III) 30 = 5 + 5 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
(IV) 30 = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
The cases (I) and (IV) give us only one sequence each
The number of sequences in case (II) is the permutation of 9 elements, with 4 items and 5 items repeated:
9!/(4!.5!) = 126 cases
The number of sequences in case (II) is the permutation of 12 elements, with 10 items and 2 items repeated:
12!/(10!.2!) = 66 cases
The total number of cases is 1 + 126 + 66 + 1 = 194 cases.
There are 4 combinations of 2's and 5's that sum to 30: 0 2's and 6 5's (1) 5 2's and 4 5's (9C4 = 126, you're picking spots to put the 5's) 10 2's and 2 5's (12C2 = 66) 15 2's and 0 5's (1) 1+126+66+1=194
We make use of the following formula: the number of ways of ordering a + b objects of which a are alike of one kind and b are alike of another kind is given by:
a ! b ! ( a + b ) !
We look for the number of 5's used in the ordered sum.
we can use 0 5's , 2 5's , 4 5's or 6 5's .
Case 1: 0 5's
the sum will be written entirely of 2's hence there is only 1 way.
Case 2: 2 5's
we have 2 5's and 10 2's , so the number of ways of ordering them will be
1 0 ! 2 ! 1 2 ! = 6 6 w a y s
Case 3: 4 5's
we have 4 5's and 5 2's , so the number of ways of ordering them will be
5 ! 4 ! 9 ! = 1 2 6 w a y s
Case 4 : 6 5's
the sum will be made entirely of 5's hence there is only 1 way.
So the total number of ways = 1 + 6 6 + 1 2 6 + 1 = 1 9 4 ways.
First, it could be noted that 2 and 5 are coprime. Hence, we could say that five 2 s could equal two 5 s.
We now consider two kinds of arrangement of these 2 s and 5 s to make 3 0 , each of which has special cases.
CASE 1 A : all 5 s
3 0 = 5 × 6 , so 3 0 could be expressed using six 5 s. This could be likened to ordering six (like) objects, which could be done in 6 ! 6 ! = 1 way.
CASE 1 B : all 2 s
Using the similar argument for 1 A , and noting that 3 0 = 2 × 1 5 , we could use fifteen 2 s to write 3 0 in exactly 1 5 ! 1 5 ! = 1 way.
CASE 2 : some 5 s, some 2 s
We could start from 1 A , where 3 0 = 5 + 5 + 5 + 5 + 5 + 5 , and use the property of 2 and 5 that we mentioned to replace two of the 5 s by five 2 s. This will now be identical to ordering 4 + 5 = 9 objects; four of them are alike (the 5 s), and so are the other five (the 2 s). They can be ordered in 4 ! 5 ! 9 ! = 1 2 6 ways.
We could replace two more 5 s in the sum by five 2 s, giving us a sum of ten 2 s and two 5 s. Using the previous argument, the numbers could be ordered in 2 ! 1 0 ! 1 2 ! = 6 6 ways.
(If we continue the process of replacing 5 s by 2 s from 1 A , we end up with 1 B , both of which had been accounted for.)
(Also, 1 A can be thought of as ordering six 5 s and zero 2 s, which could be done in 6 ! 0 ! 6 ! ways. Similarly, 1 B can be done in 0 ! 1 5 ! 1 5 ! ways.)
Hence, the total number of ways 3 0 could be written as an ordered sum of 2 s and 5 s is 1 + 1 + 1 2 6 + 6 6 = 1 9 4 .
1º) 2+2+2+2+2+2+2+2+2+2+2+2+2+2+2 --> 1 forma
2º)5+5+5+5+5+5 --> 1 forma
2+2+2+2+2+2+2+2+2+2+5+5 --> podemos permuta da seguinte forma: 2 ! 1 0 ! 1 2 ! = --> 66 formas
2+2+2+2+2+5+5+5+5 --> podemos permuta da seguinte forma: 5 ! 1 4 ! 9 ! = --> 126 formas
A quantidade de maneiras possíveis é : 1+1+66+126 = 194
Each pair of 5s can be replaced with a quintuplet of 2s. The first way we'll look at is: 6 × 5 + 0 × 2 This can be arranged in (6+1-1) nCr (1-1) = 6 nCr 0 = 1 way, because there are 6 identical items to place in 1 distinct spot. Then we replace 2 5s with 5 2s and we get: 4 × 5 + 5 × 2 There are now 6 places to place each 5 so this can be arranged in (4+6-1) nCr (6-1) = 9 nCr 5 = 126 ways. Then: 2 × 5 + 1 0 × 2 0 × 5 + 1 5 × 2 Which can be arranged in respectively (2+11-1) nCr (11-1) = 12 nCr 10 = 66 and (0+16-1) nCr (16-1) = 15 nCr 15 = 1 ways. So in total, we get 1 + 1 2 6 + 6 6 + 1 = 1 9 4
And this is what I did. LOL, thanks Tim.
I can make 30 by 6 5's or 15 2's.so we have got 2 way separately.
Let's shuffle them:
First we consider 2 5's and 10 2's.In this case we can rearrange or permutate this 12!/(2!*10!) or 66 times as there are 2 identical 5's and 10 identical 2's.
Again, by taking 4 5's and 5 2's we can rearrange the case 9!/(4!*5!) or 126 times.
So we can make 30 in 2+66+126=194 ways.
First, we note that there are 4 ways of composing 30: 2 × 1 5 2 × 1 0 + 5 × 2 2 × 5 + 5 × 4 5 × 6 Thus the amount of ways in which you can rearrange them is: 1 5 ! 1 5 ! + 1 0 ! × 2 ! 1 2 ! + 5 ! × 4 ! 9 ! + 6 ! 6 ! = 1 + 6 6 + 1 2 6 + 1 = 1 9 4 Note that the numerators are just the number of ways in which you can arrange that amount of numbers, and the denominators are the amount of ways you can arrange the separate groups of 2s and 5s.
Consider the result is stored in count .
We can write the given question in equation form as,
2 x + 5 y = 3 0
We have to find all the integer pairs ( x , y ) that satisfies above equation.
Since 5 is greater, we start with substituting values for y .
When y = 0 , x = 1 5 .......... (i)
When y = 1 , x = not an integer value, so x is a fraction when y is odd.
When y = 2 , x = 1 0 .......... (ii)
When y = 4 , x = 5 .......... (iii)
When y = 6 , x = 0 .......... (iv)
So, from (i), we can write the ordered sum as 2 + 2 + . . . + ( 1 5 times ) . So, count = 1 .
From (iv), we can write the ordered sum as 5 + 5 + 5 + 5 + 5 + 5 . So, count = 1 + 1 = 2 .
From (ii), we can write the ordered sum as 2 + 2 + . . ( 1 0 times ) + 5 + 5
Now, this can be rearranged in 1 0 ! × 2 ! ( 1 0 + 2 ) ! = 6 6
So, count = 2 + 66 = 68
From (iii), we can write the ordered sum as 2 + 2 + . . ( 5 times ) + 5 + 5 + 5 + 5
Now, this can be rearranged in 5 ! × 4 ! ( 5 + 4 ) ! = 1 2 6
So, count = 68 + 126 = 194
That's the answer!
Side Note:
The word "AABBBCCCCDDDDD" can be rearranged in
\frac{14!}{2! \times 3! \times 4! \times 5!
where the denominator terms refer to the repetitions of each letter.
Same is applied in this question,
2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 5 + 5
can be rearranged in
1 0 ! × 2 ! ( 1 0 + 2 ) !
Some people remember it as 2 1 0 + 2 C
Log in to reply
Ahh, wrong formatting.
The boxed term represents:
2 ! × 3 ! × 4 ! × 5 ! 1 4 !
Constructive counting is one way to approach this problem. What we need is a way to organize and count our ordered sums. A nice way to count our sums is by using our 5's. There can only be 0 fives , 2 fives, 4 fives, or 6 fives in our sum, since 30 is an even number. Our first case, with 0 fives is all 2's. There is only one ordered sum in this case. Our next case has two fives. There are 12C2 or 66 ordered sums in this case. The next case has 4 fives. There are 9C4 or 126 ordered sums in this case. Lastly, there is the case of six fives. There is one ordered sum in this case. Thus, we have 1 + 66 + 126 + 1 or 1 9 4 ordered sums.
Problem Loading...
Note Loading...
Set Loading...
We only have 4 cases: (0 fives and 15 twos, 2 fives and 10 twos, 4 fives and 5 twos and 6 fives and zero twos).
We will use the fives as separators.
Case 1: Using 0 fives: We'll use 15 2s and 0 separators (5s) which is 1 5 C 1 5 = 1 .
Case 2: Using 2 fives: 1 0 + 2 C 2 = 6 6 .
Case 3: Using 4 fives: 5 + 4 C 4 = 1 2 6 .
Case 4: Using 6 fives: 1 solution only.
So the sum of the solutions = 1 + 66 + 126 + 1 = 1 9 4