Library / /730 of 740

, 2018

Number theory Difficulty 5.9 AIME, harder Prove it United States

Problem:

I have two cents and Bill has $n$ cents. Bill wants to buy some pencils, which come in two different packages. One package of pencils costs 6 cents for 7 pencils, and the other package of pencils costs a dime for a dozen pencils (i.e. 10 cents for 12 pencils). Bill notes that he can spend all $n$ of his cents on some combination of pencil packages to get $P$ pencils. However, if I give my two cents to Bill, he then notes that he can instead spend all $n+2$ of his cents on some combination of pencil packages to get fewer than $P$ pencils. What is the smallest value of $n$ for which this is possible?

Note: Both times Bill must spend all of his cents on pencil packages, i.e. have zero cents after either purchase.

Solution

Solution:

Suppose that Bill buys $a$ packages of 7 and $b$ packages of 12 in the first scenario and $c$ packages of 7 and $d$ packages of 12 in the second scenario. Then we have the following system:
$\begin{aligned} & 6a + 10b = n \\ & 6c + 10d = n + 2 \\ & 7a + 12b > 7c + 12d . \end{aligned}$
Since the packages of 12 give more pencils per cent, we must have $b > d$ . Subtract the first two equations and divide by 2 to get
$3(c - a) - 5(b - d) = 1$
Note that the last inequality is $12(b - d) > 7(c - a)$ . The minimal solutions to the equation with $b - d > 0$ are
$(c - a, b - d) = (2,1), (7,4), (12,7), (17,10)$
$(17,10)$ is the first pair for which $12(b - d) > 7(c - a)$ . Hence $b \geq 10$ so $n \geq 100$ . We can easily verify that $(a, b, c, d, n) = (0, 10, 17, 0, 100)$ satisfies the system of equations.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.