AMC 8 · 2000 · #20

• "각 종류 한 개씩" 조건을 먼저 써서 문제를 줄입니다.
• 1센트, 5센트, 10센트, 25센트를 한 개씩 따로 놓아요.
• 동전 $4$ 개로 $1 + 5 + 10 + 25 = 41$¢ 가 정해집니다.
• 남은 것은 $5$ 개의 동전으로 $102 - 41 = 61$¢ 를 만드는 일입니다.

💡 "적어도 한 개" 조건을 먼저 처리하면 네 변수 문제가 최솟값 조건 없는 더 작은 문제로 바뀝니다.

• 약수·배수로 페니 개수를 결정합니다.
• 5센트·10센트·25센트는 모두 $5$ 의 배수라서, 이들 끼리 더하면 끝자리는 $0$ 이나 $5$ 가 됩니다.
• 남은 $61$¢ 의 끝자리는 $1$ 이므로 그 "$1$" 은 페니가 책임져야 합니다 — 즉 추가 페니 개수를 $5$ 로 나눈 나머지가 $1$ 이어야 합니다.
• $\{0,1,2,3,4,5\}$ 중 조건을 만족하는 값은 $1$ 또는 $6$ 인데, 남은 동전이 $5$ 개뿐이라 $6$ 은 불가능합니다.
• 따라서 추가 페니는 정확히 $1$ 개.

💡 끝자리 ($1$ 의 자리) 만 봐도 다른 동전은 건드리지 않고 페니 개수가 정해집니다.

• 남은 예산을 갱신합니다.
• 페니 $1$ 개를 더 놓고 나면, 아직 배정할 동전은 $5 - 1 = 4$ 개이고 남은 금액은 $61 - 1 = 60$¢.
• 이 $4$ 개는 5센트·10센트·25센트 중에서만 고릅니다.

💡 페니가 정리되고 나면 남은 동전은 모두 $5$ 의 배수 값이라, 이제부터는 작은 표 위에서의 단순 시도뿐입니다.

• 추가 10센트의 개수로 경우를 나눠 봅니다.
• 남은 $4$ 개 중 10센트의 개수를 $d$ 라 하면, 나머지 $4 - d$ 개는 5센트·25센트로 $60 - 10d$ 센트를 만들어야 합니다.
• $d = 0, 1, 2, 3, 4$ 를 차례로 확인합니다.\n\n• $d = 4$: $0$ 개로 $60 - 40 = 20$¢.
• 불가능.\n• $d = 3$: $1$ 개로 $30$¢.
• $30$¢ 인 동전 한 개는 없으니 불가능.\n• $d = 2$: $2$ 개로 $40$¢.
• 가능 조합은 $5+5=10$, $5+25=30$, $25+25=50$.
• $40$ 이 없으므로 불가능.\n• $d = 1$: $3$ 개로 $50$¢.
• 25센트 $q$ 개라 하면 $25q + 5(3-q) = 15 + 20q = 50 \Rightarrow 20q = 35$.
• 정수 해가 없으니 불가능.\n• $d = 0$: $4$ 개로 $60$¢.
• $25q + 5(4-q) = 20 + 20q = 60 \Rightarrow q = 2$, 5센트는 $n = 2$ 개.
• 성립.

💡 다섯 가지 작은 경우, 각각 한 번의 확인이면 끝 — 빠짐없이 나열하기 도구가 빛나는 상황입니다.

• 처음에 빼 놓았던 10센트를 다시 더해 줍니다.
• 최종 동전 묶음은 페니 $1 + 1 = 2$ 개, 5센트 $1 + 2 = 3$ 개, 10센트 $1 + 0 = 1$ 개, 25센트 $1 + 2 = 3$ 개.
• 확인: $2 + 3 + 1 + 3 = 9$ 개, $2(1) + 3(5) + 1(10) + 3(25) = 2 + 15 + 10 + 75 = 102$¢.
• 10센트의 개수는 $1$.

💡 맨 처음에 빼 놓았던 10센트를 다시 더하는 걸 잊지 마세요 — 답 $1$ 은 그 첫 한 개에서 나옵니다.