¿Cuál es el valor más pequeño de k de modo que se pueda formar un número entero mayor o igual a k usando monedas de 4 y 9 centavos?

Answer 1

Esto está estrechamente relacionado con la respuesta de Amitabha Tripathi a Si x, y, y N son todos enteros positivos, y 7x + 11y = N, ¿cuál es el mayor valor de N que hace esto imposible?

Recuerde de la respuesta anterior que [math] ab [/ math] es el número entero más grande que no se puede expresar en la forma [math] ax + por [/ math] con [math] x, y \ in \ mathbb N [ /matemáticas]. Si denotamos este número por [matemática] f (a, b) [/ matemática], entonces [matemática] f (a, b) = ab [/ matemática].

Tenga en cuenta que si [math] (x, y) \ in \ mathbb N \ times \ mathbb N [/ math] es una solución para [math] ax + by = n [/ math], entonces [math] (x ^ { \ prime}, y ^ {\ prime}) [/ math] es una solución [math] ax ^ {\ prime} + by ^ {\ prime} = n- (a + b) [/ math] con [math] x ^ {\ prime} = x-1 [/ math], [math] y ^ {\ prime} = y-1 [/ math].

Lo contrario también es cierto. Por lo tanto, existe una correspondencia uno a uno entre las soluciones para [math] ax + by = n [/ math] en pares enteros positivos [math] x, y [/ math] y las soluciones para [math] ax + by = n – (a + b) [/ math] en pares enteros no negativos [math] x, y [/ math]. Entonces, si denotamos por [math] g (a, b) [/ math] el entero más grande no expresable por la forma [math] ax + por [/ math] con [math] x, y \ in \ mathbb N \ cup \ {0 \} [/ math], luego [math] g (a, b) = f (a, b) – (a + b) = ab-ab [/ math].

---

Para una prueba directa de la fórmula [matemáticas] g (a, b) = ab-ab [/ matemáticas] , el lector interesado puede modificar fácilmente el argumento en la prueba que proporciono a mi respuesta a Si x, y y N son todos los enteros positivos, y 7x + 11y = N, ¿cuál es el mayor valor de N que hace esto imposible?

Answer 2

Tenga en cuenta que para hacer un número entero impar, necesita un número impar de nueves. Observe que [matemáticas] 23 <27 = 3 \ veces 9 [/ matemáticas]. Entonces, para hacer el número [matemática] 23 [/ matemática], necesitaría usar exactamente un nueve, pero eso requeriría que haga [matemática] 14 [/ matemática] usando solo cuatro. Obviamente esto no se puede hacer ya que [matemáticas] 14 [/ matemáticas] no es divisible por cuatro. Entonces concluimos que [math] 23 [/ math] no puede construirse de esta manera.

Luego, observe que [matemáticas] 24 = 6 \ veces 4 [/ matemáticas], [matemáticas] 25 = 4 \ veces 4 + 9 [/ matemáticas], [matemáticas] 26 = 2 \ veces 4 + 2 \ veces 9 [/ matemáticas] y [matemáticas] 27 = 3 \ veces 9 [/ matemáticas].

Finalmente considere cualquier [math] n \ in \ mathbb Z [/ math] tal que [math] n \ ge 24 [/ math]. Tenga en cuenta que [math] (n-24) [/ math] dividido entre cuatro debe dejar un resto de cero, uno, dos o tres.

1. Si [math] (n-24) [/ math] dividido por cuatro deja un resto de cero, entonces [math] n [/ math] puede formarse formando primero [math] 24 [/ math] y luego sumando cuatro monedas valoradas para llegar a [matemáticas] n [/ matemáticas].
2. Si [math] (n-24) [/ math] dividido por cuatro deja un resto de uno, entonces [math] (n-25) [/ math] es divisible por cuatro, por lo que [math] n [/ math] puede ser formado primero formando [matemática] 25 [/ matemática] y luego agregando suficientes cuatro monedas valiosas para alcanzar [matemática] n [/ matemática].
3. Si [math] (n-24) [/ math] dividido por cuatro deja un resto de dos, entonces [math] (n-26) [/ math] es divisible por cuatro, por lo que [math] n [/ math] puede ser formado al formar [math] 26 [/ math] y luego agregar suficientes monedas de cuatro valores para alcanzar [math] n [/ math].
4. Finalmente, si [math] (n-24) [/ math] dividido por cuatro deja un resto de tres, entonces [math] (n-27) [/ math] es divisible por cuatro, entonces [math] n [/ math] puede formarse formando primero [math] 27 [/ math] y luego agregando suficientes cuatro monedas valiosas para alcanzar [math] n [/ math].

Así que ahora hemos demostrado que [matemáticas] 23 [/ matemáticas] no es posible, pero todos los enteros de al menos [matemáticas] 24 [/ matemáticas] son ​​posibles, entonces [matemáticas] 24 [/ matemáticas] es la respuesta.

Answer 3

Estamos buscando enteros que puedan producirse mediante combinaciones lineales de 4 y 9. Debido a que 4 es menor que 9, si podemos encontrar 4 enteros consecutivos que podamos encontrar tales combinaciones lineales, al sumarles algunos múltiplos de 4, puede producir cualquier número entero superior.

Hice una lista de qué números podrían formarse mediante combinaciones lineales, y luego busqué 4 enteros consecutivos. Hice una hoja de cálculo que contiene valores para esto aquí 4 y 9 Lineal.

Los primeros 4 enteros consecutivos para los cuales podemos formar las combinaciones lineales requeridas son 24, 25, 26 y 27. Por lo tanto, para todos los valores de cambio de 24 centavos o más se pueden hacer con monedas de 4 y 9 centavos.