2

In a game of darts, the target is a bit special and has three regions which carry 13 points, 24 points and 31 points. Question: What is the largest total number of points that is impossible to reach?

Here is my attempt, and where I get stuck:

In other words, the question is the diophantine equation $13x+24y+31z=N$ and asks the highest number $N$ such that the equation has no positive solutions $(x,y,z)$. I managed to find the general solution of the equation:

$$x = -11(N+31k)+24m \\ y=6(N+31k)-13m\\ z=-k$$

where $k$ and $m$ are any integer.
Demanding that $x$, $y$, and $z$ are all non-negative imposes conditions on $k$ and $m$ for all $N$:

$$k\leq 0 \\ \frac{143}{312}(N+31k) \leq m \leq \frac{144}{312}(N+31k)$$

Clearly, with $N$ large enough, there will always be an integer $m$ that satisfies the condition. But now which $N$ is the largest one for which there does not exist any $m,k$ integer that satisfy the conditions?

Note: the answer is $N=121$, as I confirmed with trying all possibilities... Very curious how to find this result! Thanks!

Ottavio
  • 2,287
vin sands
  • 51

1 Answers1

1

When only two coprime numbers $a_1$, $a_2$ are given the largest number $N$ non representable in the form $N=ja_1+ka_2$ $(j, k\geq0)$ is given by $$N=a_1a_2-a_1-a_2\ ,$$ as Stirling has proved. This is the simplest case of the so-called Frobenius problem. When $n=3$ three coprime integers $a_i$ are given there is no such simple formula. The following paper treats the $n=3$ problem. A linear diophantine problem involving the $a_i$ has to be solved during the computations.

https://people.math.ethz.ch/~blatter/geomfrob.pdf

Christian Blatter
  • 226,825
  • Very interesting, this is exactly what I need, thanks! I have a problem understanding your article, though. Based on your notation, if we take $a_1=13$, $a_2=24$, $a_3=31$, then I have a hard time figuring out how to calculate the parameters $l_i$ that you define. Hard to find the smallest $l_3$ such that we can write $31 l_3 = 13x_3+24y_3$ with positive $x_3$, $y_3$. I can find a general solution $(x_3,y_3)=(-341l_3+24m, 186l_3-13m)$ with $m$ any integer. But finding the smallest multiplier $l_3$ necessary to guarantee both parameters $x_3, y_3$ are positive is exactly my problem. – vin sands Dec 15 '20 at 23:53
  • @vinsands: See the last 6 lines of page 2. – Christian Blatter Dec 16 '20 at 08:01
  • Sorry, I can't understand how to apply this concretely in this specific example. – vin sands Dec 16 '20 at 10:25
  • @vinsands: The method of the paper is thought for large numbers. I played around with your figures and quickly found the solution $N=121$. E.g., $13l_1=24 x_{12}+31 x_{13}$ asks for small $x_{12}$, $x_{13}$ such that $11x_{12}+5x_{13}=0$ mod $13$. One then guesses $x_{12}=1$, $x_{13}=3$, and obtains $l_1=9$. Later on formula $(4)$ of the paper helps also. – Christian Blatter Dec 16 '20 at 13:44