Todos menos $35$ valores pueden ser pagados con monedas de $a$ y $b$ y $58$ no se puede pagar. Encuentre $a$ y $b$ .

Question

Dejar $a<b$ sean enteros positivos, utilizando monedas de valores $a$ y $b$ exactamente $35$ Los valores no pueden pagarse exactamente sin cambios. $58$ está entre estos valores. Encuentre $a$ y $b$ . He conseguido resolverlo, pero me ha costado casi veinte minutos, ¿hay alguna solución rápida para esto, también es buena mi solución? Gracias y saludos.

Mi solución:

Claramente $(a,b)=1$ . Observe que cada número entero $v$ puede escribirse canónicamente de forma única como $sa+tb$ con $s\in\{0,1\dots b-1\}$ y $t\in \mathbb Z$ . Un valor $v$ no puede formarse si y sólo si $t<0$ en esta expresión. Si un entero positivo tiene una expresión canónica con $b$ negativo entonces $s\in\{1,\dots b-1\}$ y $t\in\{-1,-2\dots,-a+1\}$ . De todas estas expresiones la mitad son negativas porque si $x$ se expresa así por lo que es $-x$ . Por lo tanto, $(a-1)(b-1)=70\implies (a,b)=(2,71),(3,36),(6,15)$ o $(8,11)$ . El primero no funciona como $58=29\times 2$ El siguiente $2$ no funcionan ya que no son coprimos. El último funciona como $58=10\times 8 - 2\times 11$ . Así que $a=8,b=11$ .

Answer 1

Su solución es buena, y no es mucho más rápida.

Más generalmente, el resultado estructural relevante es la siguiente simetría agradable:

1. Dejemos que $a, b \ge 0$ sea coprima. Entonces para todo $x \in \mathbb{Z}$ , $x$ puede formarse si $(ab-a-b) - x$ no se puede formar.

Entonces los siguientes (que son más conocidos) son corolarios inmediatos:

2. El mayor número entero que no se puede formar es $ab - a - b$ .

3. Hay exactamente $\frac{ab-a-b+1}{2}$ enteros no negativos que no se pueden formar.

Para resolver la cuestión, mediante (3) $(a-1)(b-1) = 70$ y $ab-a-b = 69$ . Entonces, por (1), ya que $58$ no se puede formar, $69 - 58 = 11$ puede formarse. Así que estamos buscando $a,b$ tal que $(a-1)(b-1) = 70$ y $11$ es una suma de $a$ s y $b$ s. $a = 8$ , $b = 11$ rápidamente.

---

Observación final: Lamentablemente, no creo que haya ninguna estructura agradable análoga a (1) cuando hay 3 o más variables.