Maths Olympiad Prep

Library / /369 of 520

Combinatorics Difficulty 6.4 National olympiad Find 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,zx, 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\begin{array}{l} x+2 y+5 z=18 \\ x+y+z=10 \end{array}

Subtracting the second equation from the first, we get y+4z=8y+4 z=8.
We need to find the non-negative integer solutions to the above equations. First, solve
u+4v=1u+4 v=1

Since 4=3+14=3+1, we get 1=3+41=-3+4. Therefore, u=3,v=1u=-3, v=1 is a set of integer solutions to u+4v=1u+4 v=1. Thus,
y=8×(3)=24,z=8×1=8y=8 \times(-3)=-24, z=8 \times 1=8

is a set of integer solutions to y+4z=8y+4 z=8. The complete set of integer solutions is
y=244t,z=8+t,t=0,±1,±2,y=-24-4 t, \quad z=8+t, \quad t=0, \pm 1, \pm 2, \cdots

Therefore,
x=10yz=26+3tx=10-y-z=26+3 t

According to the problem, we need x0,y0,z0x \geqslant 0, y \geqslant 0, z \geqslant 0. From x=26+3t0x=26+3 t \geqslant 0, we get t263t \geqslant-\frac{26}{3}; from y=244t0y=-24-4 t \geqslant 0, we get t6t \leqslant-6; and from z=8+t0z=8+t \geqslant 0, we get t8t \geqslant-8. Therefore, 8t6-8 \leqslant t \leqslant-6 (taking t=8,7,6t=-8, -7, -6) corresponds to the following three sets of solutions:
{x=2y=8z=0,{x=5y=4z=1,{x=8y=0z=2\left\{\begin{array} { l } { x = 2 } \\ { y = 8 } \\ { z = 0 , } \end{array} \quad \left\{\begin{array}{l} x=5 \\ y=4 \\ z=1 \end{array},\left\{\begin{array}{l} x=8 \\ y=0 \\ z=2 \end{array}\right.\right.\right.

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.