Scores achievable in a game of darts

This is from an italian math competition. In the game of darts below a player is able to reach points only of 105, 30, 14 (either exact center or on the border). The final score is the sum or all points obtained.

There is a maximum score that cannot be reached in a game, above which all scores are feasible. What is this number ?

I think I have a solution, but it is not really elegant. Looking on the internet for inspiration I found this.

Chicken-Nugget lemma: Given a,b coprimes, we consider the set $S=\{am+bn,m\ge0,n\ge0\}$. Than the maximum number not belonging to $S$ is $ab-(a+b)$.

Using this we can proceed like that. A generic score is of the form $s=105a+14b+30c$, where $a,b,c$ are positive. We can write is as $105a+2(7b+15c)$. According to the lemma all numbers higher than $105-15-7=83$ are of the form $7b+15c$, therefore we subsitute $7b+15c \rightarrow 84+t$, where $t\ge 0$ (note that also smaller numbers are feasible, but we do not consider this). Substituting $s=168+(105a+2t)$. Now again according to lemma all numbers higher than $210-105-2=103$ can be written as $105a+2t$. Therefore we substitute $105a+2t \rightarrow 104 +q$, with q positive and obtain $s=272+q$. This shows that all scores larger than $272$ are feasible.

It remains to show that $271$ is not feasible. At this point I think it is mere luck if it is not, but we can give it a try. We suppose:

$271=105a+14b+30c$

We have $a \le 2$ and by parity we must have $a=1$. Therefore we have $166=14b+30c$, or $83=7b+15c$. This shows that $c \le 5$, but for neither $c \in \{0,1,2,3,4,5\}$ is $b$ integer. Therefore $271$ is the answer. c.v.d.

What I do not like in this solution is the second part. Is there some "theory", like in the chicken nugget theorem that assures that 271 should not be achievable ? I read some proofs of the chicken nugget theorem for two variables, but I am not sure that they apply to the 3-variables case. As it is, it looks to me by chance that the score 271 is not achievable. It could have been, and than I would have needed to check by hand also 270, 269,... which is not really elegant nor general ...

Any ideas/comments/proposals for other solutions ?

Solution 1:

$105$ is the only odd point value, so it is a necessary inclusion to reach any odd total. As $2\cdot 105 = 15\cdot 14$ is reachable without $105$, any reachable odd number can be reached with exactly one $105$, and any reachable even number can be reached with no $105$.

As a consequence, if $e$ is an unreachable even number, then $e+105$ is an unreachable odd number, and vice versa. So clearly, the highest unreachable number $x$ is odd. And $x-105$ is the highest unreachable even number.

This means that $\frac{x-105}2$ is the highest unreachable number using $\frac{14}2, \frac{30}2, \frac{42}2$ and $\frac{70}2$ (the last two are redundant, so I will ignore them). And the largest unreachable number using $7$ and $15$ is $7\cdot 15 - 7 - 15 = 83$. So we have $\frac{x-105}2 = 83$, which gives us $x = 271$.

Solution 2:

Given two coprime integers $a,b>1$, a slick argument that $ab-a-b$ is not of the form $am+bn$ with $m$ and $n$ nonnegative integers, is that then $$am+bn=ab-a-b\equiv-a\pmod{b},$$ $$am+bn=ab-a-b\equiv-b\pmod{a},$$ and so $m\equiv-1\pmod{b}$ and $n\equiv-1\pmod{a}$. As $m$ and $n$ are positive it follows that $m\geq b-1$ and $n\geq a-1$ and so $$am+bn\geq a(b-1)+b(a-1)=2ab-a-b>ab-a-b,$$ a contradiction. A similar approach works here; we are given three integers $14,30,105>1$ with $\gcd(14,30,105)=1$. If $14k+30m+105n=271$ then \begin{eqnarray*} 14k+30m+105n&\equiv&271&\equiv&1\pmod{\gcd(14,30)},\qquad&\text{ so }&\qquad n&\equiv&-1\pmod{2}\\ 14k+30m+105n&\equiv&271&\equiv&5\pmod{\gcd(14,105)},\qquad&\text{ so }&\qquad m&\equiv&-1\pmod{7}\\ 14k+30m+105n&\equiv&271&\equiv&1\pmod{\gcd(30,105)},\qquad&\text{ so }&\qquad k&\equiv&-1\pmod{15}\\ \end{eqnarray*} from which it follows that $k\geq14$, $m\geq6$ and $n\geq1$. But then $$14k+30m+105n\geq14\times14+30\times6+105\times1>271,$$ a contradiction.

Old rambling answer:

A slight variation on your approach; note that $30=2\times15$ and $14=2\times7$, and $15$ and $7$ are coprime. Then the Chicken-nugget lemma tells you that every number greater than $$15\times7-15-7=83,$$ can be achieved with $15$ and $7$, and so every even number greater than $2\times83=166$ can be achieved with $14$ and $30$. Then adding $10$ shows that every integer greater than $166+105=271$ can be achieved with $14$, $30$ and $105$.

Your argument that $271$ cannot be achieved seems quite elegant and efficient. A more 'symmetric' approach would be to note that \begin{eqnarray*} a&\equiv&1\pmod{2}\\ b&\equiv&14\pmod{15}\\ c&\equiv&6\pmod{7}, \end{eqnarray*} where $2=\gcd(14,30)$, $15=\gcd(30,105)$ and $7=\gcd(14,105)$. But already for $a=1$, $b=14$ and $c=6$ you exceed $271$.

Note that this first argument can be applied to the other two pairs; we have $30=15\times2$ and $105=15\times7$, and $2$ and $7$ are coprime. Then the Chicken-nugget lemma tells you that every number greater than $$2\times7-2-7=5,$$ can be achieved with $2$ and $7$, and so every multiple of $15$ greater than $5\times15=75$ can be achieved with $30$ and $105$. We can get all other cosets modulo $15$ by adding $14$ up to $14$ times, which shows that every integer greater than $75+14\times14=271$ can be achieved.

Similarly, we have $14=7\times2$ and $105=7\times15$, and $2$ and $15$ are coprime. Then the Chicken-nugget lemma tells you that every number greater than $$2\times15-2-15=13,$$ can be achieved with $2$ and $15$. Then every multiple of $7$ greater than $13\times7=91$ can be achieved with $14$ and $105$. We can get all other cosets modulo $7$ by adding $30$ up to $6$ times, which shows that every integer greater than $91+6\times30=271$ can be achieved.

This suggests the following proposition:

Proposition: Let $a$, $b$ and $c$ be three positive integers with $\gcd(a,b,c)=1$. Then every integer greater than $$\frac{ab}{\gcd(a,b)}-a-b+c(\gcd(a,b)-1),$$ is of the form $ax+by+cz$ for some nonnegative integers $x$, $y$ and $z$.