Track / Stage 5 / 379 of 400 #1459 of 2444

Problem 1459

AIME late

Number theory Difficulty 5.9 Prove it HMMT November · United States · 2018

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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.