Puntuaciones alcanzables en una partida de dardos

Question

Esto es de un concurso de matemáticas italiano. En el juego de dardos de abajo un jugador es capaz de alcanzar puntos sólo de 105, 30, 14 (ya sea el centro exacto o en el borde). La puntuación final es la suma de todos los puntos obtenidos.

Hay una puntuación máxima que no se puede alcanzar en una partida, por encima de la cual todas las puntuaciones son factibles. ¿Cuál es este número?

Creo que tengo una solución, pero no es muy elegante. Buscando inspiración en internet encontré esto.

El lema de Chicken-Nugget: Dados los coprimas a,b, consideramos el conjunto $S=\{am+bn,m\ge0,n\ge0\}$ . Que el número máximo que no pertenece a $S$ es $ab-(a+b)$ .

Con esto podemos proceder así. Una puntuación genérica es de la forma $s=105a+14b+30c$ , donde $a,b,c$ son positivos. Podemos escribir es como $105a+2(7b+15c)$ . Según el lema, todos los números mayores que $105-15-7=83$ son de la forma $7b+15c$ por lo que sustituimos $7b+15c \rightarrow 84+t$ , donde $t\ge 0$ (nótese que también son factibles números menores, pero no lo consideramos). Sustituyendo $s=168+(105a+2t)$ . Ahora de nuevo según el lema todos los números mayores que $210-105-2=103$ puede escribirse como $105a+2t$ . Por lo tanto, sustituimos $105a+2t \rightarrow 104 +q$ con q positivo y obtener $s=272+q$ . Esto demuestra que todas las puntuaciones mayores que $272$ son factibles.

Queda por demostrar que $271$ no es factible. En este momento creo que es mera suerte si no lo es, pero podemos intentarlo. Suponemos:

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

Tenemos $a \le 2$ y por paridad debemos tener $a=1$ . Por lo tanto, tenemos $166=14b+30c$ o $83=7b+15c$ . Esto demuestra que $c \le 5$ pero para ninguno de los dos $c \in \{0,1,2,3,4,5\}$ es $b$ entero. Por lo tanto, $271$ es la respuesta. c.v.d.

Lo que no me gusta de esta solución es la segunda parte. ¿Hay alguna "teoría", como en el teorema de la pepita de pollo, que asegure que 271 no debería ser alcanzable? He leído algunas pruebas del teorema de la pepita de pollo para dos variables, pero no estoy seguro de que se apliquen al caso de 3 variables. Así las cosas, me parece que por casualidad la puntuación 271 no es alcanzable. Podría haberlo sido, y entonces habría necesitado comprobar a mano también 270, 269,... lo cual no es realmente elegante ni general...

¿Alguna idea/comentario/propuesta de otras soluciones?

Answer 1

$105$ es el único valor de puntos impar, por lo que es una inclusión necesaria para alcanzar cualquier total impar. Como $2\cdot 105 = 15\cdot 14$ es alcanzable sin $105$ cualquier número impar alcanzable puede ser alcanzado con exactamente una $105$ y cualquier número par alcanzable puede ser alcanzado sin $105$ .

En consecuencia, si $e$ es un número par inalcanzable, entonces $e+105$ es un número impar inalcanzable, y viceversa. Así que claramente, el mayor número inalcanzable $x$ es impar. Y $x-105$ es el mayor número par inalcanzable.

Esto significa que $\frac{x-105}2$ es el número más alto inalcanzable utilizando $\frac{14}2, \frac{30}2, \frac{42}2$ y $\frac{70}2$ (los dos últimos son redundantes, así que los ignoraré). Y el mayor número inalcanzable utilizando $7$ y $15$ es $7\cdot 15 - 7 - 15 = 83$ . Así que tenemos $\frac{x-105}2 = 83$ , lo que nos da $x = 271$ .

Answer 2

Dados dos enteros coprimos $a,b>1$ un argumento hábil que $ab-a-b$ no es de la forma $am+bn$ con $m$ y $n$ enteros no negativos, es que entonces $$am+bn=ab-a-b\equiv-a\pmod{b},$$ $$am+bn=ab-a-b\equiv-b\pmod{a},$$ y así $m\equiv-1\pmod{b}$ y $n\equiv-1\pmod{a}$ . Como $m$ y $n$ son positivos se deduce que $m\geq b-1$ y $n\geq a-1$ y así $$am+bn\geq a(b-1)+b(a-1)=2ab-a-b>ab-a-b,$$ una contradicción. Un enfoque similar funciona aquí; se nos dan tres enteros $14,30,105>1$ con $\gcd(14,30,105)=1$ . Si $14k+30m+105n=271$ entonces \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*} de lo que se deduce que $k\geq14$ , $m\geq6$ y $n\geq1$ . Pero entonces $$14k+30m+105n\geq14\times14+30\times6+105\times1>271,$$ una contradicción.

---

Respuesta de la antigua divagación:

Una ligera variación de su enfoque; tenga en cuenta que $30=2\times15$ y $14=2\times7$ y $15$ y $7$ son coprimos. Entonces el lema de Chicken-nugget nos dice que todo número mayor que $$15\times7-15-7=83,$$ puede lograrse con $15$ y $7$ y así cada incluso número mayor que $2\times83=166$ puede lograrse con $14$ y $30$ . A continuación, añadiendo $10$ muestra que todo número entero mayor que $166+105=271$ puede lograrse con $14$ , $30$ y $105$ .

Su argumento de que $271$ no se puede lograr parece bastante elegante y eficiente. Un enfoque más "simétrico" sería observar que \begin{eqnarray*} a&\equiv&1\pmod{2}\\ b&\equiv&14\pmod{15}\\ c&\equiv&6\pmod{7}, \end{eqnarray*} donde $2=\gcd(14,30)$ , $15=\gcd(30,105)$ y $7=\gcd(14,105)$ . Pero ya para $a=1$ , $b=14$ y $c=6$ usted excede $271$ .

Obsérvese que este primer argumento puede aplicarse a los otros dos pares; tenemos $30=15\times2$ y $105=15\times7$ y $2$ y $7$ son coprimos. Entonces el lema de Chicken-nugget nos dice que todo número mayor que $$2\times7-2-7=5,$$ puede lograrse con $2$ y $7$ y así cada múltiplo de $15$ mayor que $5\times15=75$ puede lograrse con $30$ y $105$ . Podemos obtener todos los demás cosets módulo $15$ añadiendo $14$ hasta $14$ veces, lo que demuestra que cada número entero mayor que $75+14\times14=271$ puede lograrse.

Del mismo modo, tenemos $14=7\times2$ y $105=7\times15$ y $2$ y $15$ son coprimos. Entonces el lema de Chicken-nugget nos dice que todo número mayor que $$2\times15-2-15=13,$$ puede lograrse con $2$ y $15$ . Entonces cada múltiplo de $7$ mayor que $13\times7=91$ puede lograrse con $14$ y $105$ . Podemos obtener todos los demás cosets módulo $7$ añadiendo $30$ hasta $6$ veces, lo que demuestra que cada número entero mayor que $91+6\times30=271$ se puede lograr.

Esto sugiere la siguiente proposición:

Propuesta: Dejemos que $a$ , $b$ y $c$ sean tres enteros positivos con $\gcd(a,b,c)=1$ . Entonces, todo número entero mayor que $$\frac{ab}{\gcd(a,b)}-a-b+c(\gcd(a,b)-1),$$ es de la forma $ax+by+cz$ para algunos enteros no negativos $x$ , $y$ y $z$ .