CombinatoricsDifficulty 6.4National olympiadFind the answer
5. Take a total of ten coins of one cent, two cents, and five cents, to pay eighteen cents. How many different ways are there to do this?
保留源文本的换行和格式,直接输出翻译结果如下:
5. Take a total of ten coins of one cent, two cents, and five cents, to pay eighteen cents. How many different ways are there to do this?
A number or a short expression. Spacing and $ signs are ignored.
Solution
5. Solution: Let x,y,z represent the number of 1-cent, 2-cent, and 5-cent coins, respectively. Therefore, we have the following equations: x+2y+5z=18x+y+z=10
Subtracting the second equation from the first, we get y+4z=8. We need to find the non-negative integer solutions to the above equations. First, solve u+4v=1
Since 4=3+1, we get 1=−3+4. Therefore, u=−3,v=1 is a set of integer solutions to u+4v=1. Thus, y=8×(−3)=−24,z=8×1=8
is a set of integer solutions to y+4z=8. The complete set of integer solutions is y=−24−4t,z=8+t,t=0,±1,±2,⋯
Therefore, x=10−y−z=26+3t
According to the problem, we need x⩾0,y⩾0,z⩾0. From x=26+3t⩾0, we get t⩾−326; from y=−24−4t⩾0, we get t⩽−6; and from z=8+t⩾0, we get t⩾−8. Therefore, −8⩽t⩽−6 (taking t=−8,−7,−6) corresponds to the following three sets of solutions: ⎩⎨⎧x=2y=8z=0,⎩⎨⎧x=5y=4z=1,⎩⎨⎧x=8y=0z=2
Therefore, there are three different ways to take the coins, which are the three sets of solutions above.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.