Sellos de 7 céntimos y 11 céntimos Inducción matemática

Question

Suponga que sólo puede utilizar sellos de 7 y 11 céntimos.
a) Determina qué cantidades de franqueo pueden formarse con los sellos dados.
b) Demuestra tu respuesta utilizando el principio de inducción matemática.
c) Demuestra tu respuesta utilizando la inducción fuerte.

Al hacer a) descubrí que todos los números después del 59 se pueden crear usando una combinación de sellos de 7 latas y 11 céntimos
En la parte b , supuse que el $$ n=7k+11l$$ donde k es la cantidad de sellos de 7 céntimos y l es la cantidad de sellos de 11 céntimos. ¿Pero cómo procedo? Y en el paso de inducción fuerte ¿cuál es nuestra hipótesis inductiva?

Answer 1

Prueba pedestre elemental (aunque, me gusta generar series). - El menor porte es 7 - Entonces 11 - Después debe ser capaz de disminuir $l$ para alimentar $k$ (y a la inversa) un rápido examen de los casos le lleva a las siguientes cantidades [14,18,21,22,25,28,29,32,33,35,36,39,40,42 ... 60,61] - el último $61$ permite la recurrencia mediante

1. ) $1=2\times 11-3\times 7$
2. ) $1=8\times 7- 5\times 11$

entonces para su recurrencia utilice alternativamente la primera y la segunda expresión. A partir del número $61=3\times 11+4\times 7$ la recurrencia funciona porque, si $n=a\times 7+b\times 11\geq 61$ no puedes tener $a<8,b<2$ ambos ( $60=7\times 7+1\times 11$ ) y entonces puedes utilizar (1) o (2).

Answer 2

Para responder a la letra a) puedes utilizar funciones generadoras:

$\left(1+x^7+x^{14}+x^{21}+x^{28}+x^{35}+x^{42}+x^{49}+x^{56}\right) \left(1+x^{11}+x^{22}+x^{33}+x^{44}+x^{55}\right)$

$= 1+x^7+x^{11}+x^{14}+x^{18}+x^{21}+x^{22}+x^{25}+x^{28}+x^{29}+x^{32}+\ x^{33}+x^{35}+x^{36}+x^{39}+x^{40}+x^{42}+x^{43}+x^{44}+x^{46}+x^{47}+\ x^{49}+x^{50}+x^{51}+x^{53}+x^{54}+x^{55}+x^{56}+x^{57}+x^{58}$

Mirando las potencias podemos ver los números que se pueden representar. Por ejemplo, si vemos x^25 sabemos que 25 es representable. Ya sabemos por los números de Frobenius que 59 es el mayor número que no se puede representar ( ver mi comentario anterior ).

Answer 3

No es una respuesta completa, pero podría ayudar:

• $A_{60} = \{7,7,7,7,7,7,7,11\}$
• $A_{61} = \{7,7,7,7,11,11,11\}$
• $A_{62} = \{7,11,11,11,11,11\}$
• $A_{63} = \{7,7,7,7,7,7,7,7,7\}$
• $A_{64} = \{7,7,7,7,7,7,11,11\}$
• $A_{65} = \{7,7,7,11,11,11,11\}$
• $A_{66} = \{11,11,11,11,11,11\}$
• $A_{n} = \{7\} \cup A_{n-7}$ inductive step

Answer 4

Considere $n=7k+11 t$ , donde $k\geq 3$ o $t\geq 5$ . En caso contrario, donde $k<3$ y $t<5$ tenemos $n<58$ que es una contradicción. Para continuar, si $k\geq 3$ entonces tenemos $n+1 =7 (k-3)+11(t+2)$ . Si $t\geq 5$ entonces tenemos $n+1 =7(k+8)+11(t-5)$ .

Answer 5

2x11 - 3x7 = 1 y 8x7 -5x11=1

Así que si puedes obtener n, puedes obtener n+1 sumando 2 11s y quitando 3 7s. Esto supone que tienes al menos 3 7s. Si no lo tienes, puedes añadir 8 7s y quitar 5 11s (y entonces tendrás más de 3) lo que supone que tienes al menos 5 11s. Si nunca tienes menos de 3 11s puedes alternar con estas técnicas.

Para n=60 podemos hacer 7 7s y 1 11. Luego sumamos 2 11s y restamos 3 7s para obtener 61. Hazlo de nuevo para obtener 62. Tendremos 5 11s y 1 7s. Entonces tenemos que cambiar de método pero entonces al menos 63 si llegamos a tener 3 11s tendremos al menos 4 7s por lo que podemos sumar dos 11s y restar 3 para obtener el siguiente.