There are 4 buttons in front of you, each with a different color, right beside it is a scoreboard showing your score. Starting from 0 points, your goal is to achieve exactly 386 points (because why not?), by pushing the buttons a total of 20 times.
If you push the red button, your score will increase by 17 points.
If you push the blue button, your score will increase by 41 points.
If you push the yellow button, your score will increase by 25 points.
If you push the green button, your score will increase by 11 points.
There are many ways to do this, 2 of them are listed below:
3 red, 4 blue, 2 yellow, 11 green
13 red, 2 blue, 2 yellow, 3 green
What is the total number of ways can this be done?
Note: You do not have to push all 4 of the buttons at least once.
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.
Suppose we need to press the red button a times, blue button b times, yellow button c times, and the green button 2 0 − a − b − c times. Here, a , b and c are non-negative integers. You can get the following equation 1 7 a + 4 1 b + 2 5 c + 1 1 ( 2 0 − a − b − c ) = 3 8 6 which upon simplifying yields 3 a + 1 5 b + 7 c = 8 3 This is a linear Diophantine equation with 3 variables, and this question is actually asking you how many non-negative integer solutions ( a , b , c ) satisfy 3 a + 1 5 b + 7 c = 8 3 .
To solve this, we move 1 5 b to the right to get 3 a + 7 c = 8 3 − 1 5 b Because a ⩾ 0 , c ⩾ 0 , so 3 a + 7 c = 8 3 − 1 5 b ⩾ 0 , thus 0 ⩽ b ⩽ 5 .
Let 8 3 − 1 5 b = n where n is a non-negative integer, now we have a new linear Diophantine equation 3 a + 7 c = n We first observe the L.H.S. of the equation, the unknown with the smallest coefficient is a which is 3. Divide both sides by 3 and we would get a + 2 c + 3 c = 3 n Then, we move all fractions to the right and all the integers to the left. We get a + 2 c = 3 n − c Because a and c are integers, therefore a + 2 c is also an integer, 3 n − c must be also an integer. Let 3 n − c = k where k is an integer. Then c = n − 3 k Substitute c in 3 a + 7 c = n with n − 3 k you get a = 7 k − 2 n We have generated our 'solutions formula'. { a = 7 k − 2 n c = n − 3 k From a = 7 k − 2 n ⩾ 0 , c = n − 3 k ⩾ 0 , and a + c < 2 0 , we would get 7 2 n ⩽ k ⩽ 3 n , k < 4 n + 5 We now have 2 cases:
Then n ⩾ 6 0 ⟹ 8 3 − 1 5 b ⩾ 6 0 ⟹ 0 ⩽ b ⩽ 1 , and we have 7 2 n ⩽ k < 4 n + 5
By substituting back n = 8 3 − 1 5 b you'll get 2 3 − 4 b + 7 5 − 2 b ⩽ k < 4 3 − 3 b + 2 5 − 3 b Since k is an integer, 2 3 − 4 b + ⌈ 7 5 − 2 b ⌉ ⩽ k < ⌈ 4 3 − 3 b ⌉ + 2 5 − 3 b ( ⌈ x ⌉ is the smallest integer greater or equal to x )
Denote the number of integer solutions k that satisfy this inequality as S k ( b ) , then S k ( b ) = ( ⌈ 4 3 − 3 b ⌉ + 2 5 − 3 b ) − ( 2 3 − 4 b + ⌈ 7 5 − 2 b ⌉ ) = b + 2 + ⌈ 4 3 − 3 b ⌉ − ⌈ 7 5 − 2 b ⌉
Because 0 ⩽ b ⩽ 1 , we have ⌈ 7 5 − 2 b ⌉ = 1 , and S k ( 0 ) = 0 + 2 + ⌈ 4 3 ⌉ − 1 = 2 S k ( 1 ) = 1 + 2 + ⌈ 0 ⌉ − 1 = 2
Then n < 6 0 ⟹ 8 3 − 1 5 b < 6 0 ⟹ 2 ⩽ b ⩽ 5 , and we have 7 2 n ⩽ k ⩽ 3 n Substitute n = 8 3 − 1 5 b , 2 3 − 4 b + 7 5 − 2 b ⩽ k ⩽ 3 2 + 2 7 − 5 b Since k is an integer, 2 3 − 4 b + ⌈ 7 5 − 2 b ⌉ ⩽ k ⩽ ⌊ 3 2 ⌋ + 2 7 − 5 b = 2 7 − 5 b ( ⌊ x ⌋ is the greatest integer smaller or equal to x ) ∴ S k ( b ) = ( 2 7 − 5 b ) − ( 2 3 − 4 b + ⌈ 7 5 − 2 b ⌉ ) + 1 = 5 − b − ⌈ 7 5 − 2 b ⌉ We have S k ( 2 ) = 2 , S k ( 3 ) = 2 , S k ( 4 ) = 1 , S k ( 5 ) = 0
b = 0 ∑ 5 S k ( b ) = 9 , therefore, there are 9 possible positive integer solutions for k , substitute k into our previously generated 'solutions formula' and you would get 9 pairs of solutions for a and c .