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?

Answer 1

Como 7 y 11 son relativamente primos [math] 7x + 11y = \ pm 1 [/ math] tendrá infinitas soluciones en enteros. Podemos escalar por [matemáticas] N [/ matemáticas] o [matemáticas] -N [/ matemáticas] para obtener soluciones a nuestra ecuación. Si requerimos dos enteros positivos, necesitamos resolver desigualdades simultáneas.

Aquí está la solución de fracción continua:

[matemáticas] \ dfrac {11} {7} = 1 + \ dfrac {1} {\ frac 7 4} = 1 + \ dfrac {1} {1 + \ dfrac {1} {\ frac 4 3}} = 1 + \ dfrac {1} {1 + \ dfrac {1} {1 + \ dfrac 1 3}} [/ matemáticas]

El convergente mágico se obtiene al soltar el último cociente parcial:

[matemáticas] 1 + \ dfrac {1} {1 + \ dfrac {1} {1}} = \ dfrac 3 2 [/ matemáticas]

Esto nos dice

[matemáticas] 7 (-3) + 11 (2) = 1 [/ matemáticas]

Multiplicar por [matemáticas] N [/ matemáticas]

[matemáticas] 7 (-3N) + 11 (2N) = N [/ matemáticas]

Eso nos da una solución particular en enteros, no positiva.

[matemáticas] 7 (-3N) + 11 (2N) = N [/ matemáticas]

También sabemos

[matemáticas] 7 (11 t) + 11 (- 7 t) = 0 \ quad [/ matemáticas] para entero [matemáticas] t [/ matemáticas]

Agregando,

[matemáticas] 7 (11t -3N) + 11 (2N-7t) = N [/ matemáticas]

es decir, tenemos la solución entera general [matemáticas] (x, y) = (11t-3N, 2N-7t) [/ matemáticas]. Para soluciones positivas requerimos

[matemática] 11t -3N> 0 \ quad \ textrm {y} \ quad 2N-7t> 0 [/ matemática]

[matemáticas] t> (3/11) N [/ matemáticas]

[matemáticas] t <(2/7) N [/ matemáticas]

[matemáticas] (3/11) N <t <(2/7) N [/ matemáticas]

Esto será imposible cuando no haya un número entero entre [math] (3/11) N [/ math] y [math] (2/7) N. [/ Math] Claramente si cuando están separados por 1 unidad, ambos son enteros esa es la más alta imposible [matemática] N, [/ matemática] ya que cada superior tendrá necesariamente un número entero en el medio. Veamos si obtenemos enteros:

[matemáticas] (3/11) N + 1 = (2/7) N [/ matemáticas]

[matemáticas] N = \ dfrac {1} {(2/7) – (3/11)} = \ dfrac {1} {22/77 – 21/77} = 77 [/ matemáticas]

[matemáticas] (3/11) (77) = 21 <t <(2/7) (77) = 22 [/ matemáticas]

Tenemos dos enteros, entonces [matemáticas] N = 77 [/ matemáticas] es el máximo imposible [matemáticas] N. [/ matemáticas]

Answer 2

Para N = 7k, siempre está bien siempre que N sea positivo.

Para N = 7k + 1, debe tener 11 y = 1 mod 7, entonces y = 2 mod 7. El y más pequeño que puede obtener es 2, entonces N = 7 + 22 = 29 y más grandes son posibles, y el más grande imposible El número es 22.

Para N = 7k + 2, obtendrá de forma similar y = 4 mod 7, por lo que N = 7 + 44 = 51 y mayores son posibles, y 44 y menores no.

Para N = 7k + 3, obtienes y = 6 mod 7, por lo que 7 + 66 = 73 es posible. Sin embargo, 66 no lo es.

Es fácil ver que en otros casos los números máximos imposibles son 11, 33, 55.

Entonces 66 es la respuesta.

Editar: Darren O’Shaughnessy señaló un error. Para N = 7k, uno necesita tener y = 0 mod 7, por lo que y es al menos 11. Por lo tanto, 7 + 77 es el mínimo posible, y 77 no se puede lograr.

Answer 3

Acabo de escribir un programa para buscar valores de hasta 1000.

N = [0] * 1000
a = [7 * i para i en el rango (200)]
b = [11 * i para i en el rango (100)]
para x en a:
para y en b:
t = x + y
si (t <1000):
N [t] = 1

pr int max ([i para i en el rango (0, 1000) si N [i] == 0])

que imprime 77

La versión habitual de este problema es para x, y> = 0, pero este es el caso x, y> = 1

Answer 4

Primero, establecemos qué es la pregunta. Cuando, por ejemplo, [matemáticas] x = 5 [/ matemáticas] y [matemáticas] y = 3 [/ matemáticas], [matemáticas] N = 68 [/ matemáticas]. O al revés, ¿podemos encontrar valores para [matemática] x [/ matemática] y [matemática] y [/ matemática] para que [matemática] 7x + 11y = 68 [/ matemática]. Sí, podemos, [matemáticas] 5 [/ matemáticas] y [matemáticas] 3 [/ matemáticas]. ¿Podemos encontrar valores adecuados para [matemática] x [/ matemática] y [matemática] y [/ matemática] sin importar [matemática] N [/ matemática]. Bueno no. No hay un valor de [matemáticas] x [/ matemáticas] o [matemáticas] y [/ matemáticas] para producir [matemáticas] N = 9 [/ matemáticas]. Buscamos la mayor [matemática] N [/ matemática] para la cual no podemos encontrar y [matemática] x [/ matemática] y una [matemática] y [/ matemática] para hacer el truco.

En esta etapa, la pregunta se realiza en gran medida mediante conjeturas inteligentes. Sin embargo, hay esperanza. Llamemos a encontrar [math] x [/ math] y [math] y [/ math], resolviendo un valor de N. Estas son las buenas noticias: si puede encontrar [matemática] 7 [/ matemática] valores consecutivos de [matemática] N [/ matemática] para los cuales puede resolver, puede resolver para cada valor de [matemática] N [/ matemática] más grande que eso. Aquí hay un pequeño ejemplo. Ciertamente, puede resolver [matemáticas] 154 [/ matemáticas] usando [matemáticas] x = 11 [/ matemáticas] y [matemáticas] y = 7 [/ matemáticas]. Supongamos que podemos resolver para [matemáticas] N = 155 [/ matemáticas], [matemáticas] 156, 157, 158, 159, 160. [/ Matemáticas] Entonces 1 [matemáticas] 61 = 7 \ veces12 + 11 \ veces7 [/ matemáticas] y [matemáticas] 162 = 7 \ 13 + 11 \ veces 7 [/ matemáticas] etc.

Sugiero dos tareas. Vea si puede resolver para [matemáticas] N = 84 a 90 [/ matemáticas]. Si puede, debe bajar a [matemáticas] 84 [/ matemáticas]. La siguiente [matemática] N [/ matemática] crucial es [matemática] 77 [/ matemática]. Cuando haya encontrado la [matemática] N [/ matemática] más grande para la cual no puede resolver, vea si puede expresar ese número en términos de [matemática] 7 [/ matemática] y [matemática] 11 [/ matemática].

Lamentablemente, no puede utilizar 0 como valor para x o y.

Answer 5

Más generalmente, para cualquier [matemática] a, b \ in \ mathbb N [/ matemática], [matemática] \ gcd (a, b) = 1 [/ matemática], [matemática] ab [/ matemática] es el entero más grande eso no puede ser representado por la forma [math] ax + por [/ math] con [math] x, y \ in \ mathbb N [/ math].

---

Prueba. Suponga que [math] ab = ar + bs [/ math] con [math] r, s \ in \ mathbb N [/ math]. Entonces [math] a \ mid bs [/ math] y [math] b \ mid ar [/ math], de modo que [math] a \ mid s [/ math] y [math] b \ mid r [/ math] desde [math] \ gcd (a, b) = 1 [/ math]. Pero luego [math] s \ ge a [/ math], [math] r \ ge b [/ math] y [math] ar + bs \ ge 2ab [/ math], contradiciendo nuestra suposición de que [math] ar + bs = ab [/ matemáticas]. Por lo tanto, [math] ab [/ math] no es representable por la forma [math] ax + por [/ math], [math] x, y \ in \ mathbb N [/ math].

Considere [math] n \ in \ mathbb N [/ math], [math] n> ab [/ math]. Dado que cada número entero puede ser representado por la forma [math] ax + por [/ math], existe [math] x, y \ in \ mathbb Z [/ math] tal que [math] n = ax + por [/ math ] Tenga en cuenta que [math] n = a (x + bt) + b (y-at) [/ math] para cada [math] t \ in \ mathbb Z [/ math]. Elija [math] t_0 \ in \ mathbb Z [/ math] tal que [math] 1 \ le x + bt_0 \ le b [/ math]. Si [matemática] x_0 = x + bt_0 [/ matemática], [matemática] y_0 = y-at_0 [/ matemática], entonces

[matemática] y_0 = \ dfrac {n-ax_0} {b}> \ dfrac {a (b-x_0)} {b} \ ge 0 [/ matemática].

Por lo tanto, [math] n = ax_0 + by_0 [/ math] con [math] x_0, y_0 \ in \ mathbb N [/ math].

Esto completa la prueba. [matemáticas] \ blacksquare [/ matemáticas]

---

Observación. Para un conjunto dado de enteros positivos [matemática] a_1, \ ldots, a_k [/ math], con [math] \ gcd (a_1, \ ldots, a_k) = 1 [/ math], el problema de determinar el entero más grande [ math] g (a_1, \ ldots, a_k) [/ math] no representable por la forma [math] a_1x_1 + \ cdots + a_kx_k [/ math], cada [math] x_i \ in \ mathbb N \ cup \ {0 \} [/ math], se conoce como el problema del intercambio de monedas y se remonta a Sylvester en [math] 1884 [/ math]. El número [matemáticas] g (a_1, \ ldots, a_k) [/ matemáticas] a veces se llama el número de Frobenius , en honor al matemático que jugó un papel importante en la popularización del problema. Para [matemáticas] k = 2 [/ matemáticas], [matemáticas] g (a_1, a_2) = a_1a_2-a_1-a_2 [/ matemáticas].

En el problema del intercambio de monedas , si restringimos los [math] x_i [/ ​​math] ‘para que sean enteros positivos [math] ([/ math], por lo tanto, no se permite [math] 0 [/ math]’ s [math]) [ / math], y llame al entero no representable más grande correspondiente como [math] f (a_1, \ ldots, a_k) [/ math], luego

[matemáticas] f (a_1, \ ldots, a_k) = g (a_1, \ ldots, a_k) + (a_1 + \ cdots + a_k) [/ math].