¿Cómo resolverías [matemáticas] 2 ^ n + n = m! [/ Matemáticas] sobre enteros positivos?

Answer 1

Como otros han señalado, parece que [math] (n, m) = (2,3) [/ math] es la única solución.

Para demostrar que realmente es así, vamos a seguir los siguientes pasos:

1. Probar un lema útil
2. Muestre cómo podemos encontrar la solución [matemáticas] (n, m) = (2,3) [/ matemáticas] sin adivinar;
3. Demuestre que, siendo [matemática] 2 ^ k \ cdot {t} = n [/ matemática], con [matemática] t [/ matemática] impar, [matemática] m! [/ Matemática] puede tener un límite inferior.
4. Deduzca que [matemática] k = 0 [/ matemática] o [matemática] k = 1 [/ matemática], y concluya que no hay soluciones distintas a [matemática] (2,3 [/ matemática]).

---

Paso 1

Lema Para todos [math] \ leq {2} [/ math] la desigualdad [math] \ displaystyle 2 ^ {2 ^ k + 2k + 3} \ leq {2 ^ {2 ^ {k + 1}} + 2 ^ {k + 1}} [/ math] se mantiene.

Esta afirmación, que resultará útil más adelante, puede demostrarse mostrando primero por inducción que para todos [math] k \ geq {3} [/ math] tenemos [math] \ displaystyle 2k + 3 <2 ^ {k + 1} [/ matemáticas]

Caso base : para [matemáticas] k = 4 [/ matemáticas] obtenemos

[matemáticas] \ begin {align} \ displaystyle 11 <16 \ end {align} \ tag * {} [/ math]

Paso inductivo : debemos mostrar que si [matemáticas] \ displaystyle 2k + 3 <2 ^ {k} [/ matemáticas] entonces [matemáticas] \ displaystyle 2 (k + 1) +3 <2 ^ {k + 1} \ Rightarrow {2k + 5 <2 ^ {k + 1}} [/ matemáticas].

Esto se puede hacer considerando la relación de los lados correspondientes, es decir, mostrando que

[matemáticas] \ begin {align} \ displaystyle \ frac {2k + 5} {2k + 3} <\ frac {2 ^ {k + 1}} {2 ^ {k}} = 2 \ end {align} \ tag {1} [/ matemáticas]

lo cual es una especie de prueba de que el lado izquierdo (LHS) crece más lentamente que el lado derecho (RHS)

Algunos álgebra elemental muestran que [math] (1) [/ math] se cumple para todos [math] \ displaystyle k \ leq {- \ frac {1} {2}} [/ math], y por lo tanto para todos los enteros positivos [math] ] \ blacksquare [/ math]

Ahora se puede probar el lema notando que [math] k = 2 [/ math] y [math] k = 3 [/ math] lo satisfacen y que para [math] k \ geq {4} [/ math] tenemos

[matemáticas] \ begin {align} \ displaystyle 2k + 3 <2 ^ {k} \ Rightarrow {2 ^ k + 2k + 3 <2 ^ {k + 1}} \ Rightarrow {2 ^ {2 ^ k + 2k + 3} <2 ^ {2 ^ {k + 1}} <2 ^ {2 ^ {k + 1}} + 2 ^ {k + 1}} \ blacksquare \ end {align} \ tag * {} [/ math ]

Por lo tanto, el lema es válido para todos los enteros [math] \ geq {2} [/ math].

---

Paso 2

Después de señalar que [math] m = 1 [/ math] produce [math] n = 0 [/ math], considere el caso [math] m \ geq {2} [/ math].

Si [math] m \ geq {2} [/ math] entonces [math] m! [/ Math] [math] \ equiv_ {2} {0} [/ math] y por lo tanto [math] n \ equiv_ {2} {0} [/ matemáticas]. Reescribe [math] \ displaystyle n = [/ math] [math] 2 ^ {k} \ cdot {t} [/ math], donde [math] t [/ math] es un entero impar.

Para [matemáticas] k = 1 [/ matemáticas] obtenemos

[matemáticas] \ begin {align} \ displaystyle 2 ^ {2t} + 2t = m! \ Rightarrow {2 || m!} \ Rightarrow {m \ leq {3}} \ end {align} \ tag * {} [ /matemáticas]

lo que da [matemáticas] (n, m) = (2,3) [/ matemáticas] como la única solución.

---

Paso 3

Aquí está la parte verdaderamente complicada: queremos mostrar que no hay más soluciones para [math] k [/ math] [math] \ geq {2} [/ math].

Comience notando que, si hubiera tal solución, podríamos escribir

[matemáticas] \ begin {align} \ displaystyle m! = 2 ^ {2 ^ k \ cdot {t}} + 2 ^ k \ cdot {t} \ Rightarrow {2 ^ k || m!} \ end {align} \ tag * {(**)} [/ math]

también

[matemáticas] \ begin {align} \ displaystyle m! = 2 ^ {2 ^ k \ cdot {t}} + 2 ^ k \ cdot {t} \ geq {2 ^ {2 ^ k} + 2 ^ k} \ end {align} \ tag * {} [/ math]

Ahora, la parte realmente difícil: ¡demuestre por inducción que para todos [matemáticas] k \ geq {2} [/ matemáticas] tenemos [matemáticas] \ displaystyle 2 ^ {2 ^ k} + 2 ^ k> (2k-1)! [/matemáticas]

Caso base: para [matemáticas] k = 2 [/ matemáticas] obtenemos la verdadera desigualdad [matemáticas] 20> 6 [/ matemáticas]

Paso inductivo: debemos mostrar que si [matemáticas] \ displaystyle 2 ^ {2 ^ k} + 2 ^ k> (2k-1)! [/ Matemáticas] entonces [matemáticas] \ displaystyle 2 ^ {2 ^ {k + 1 }} + 2 ^ {k + 1}> (2k + 1)! [/ Math].

Al igual que lo hicimos para el primer lema, podemos mostrar que el RHS crece más rápido que el LHS, es decir

[matemáticas] \ begin {align} \ displaystyle \ frac {2 ^ {2 ^ {k + 1}} + 2 ^ {k + 1}} {2 ^ {2 ^ k} + 2 ^ k}> \ frac { (2k + 1)!} {(2k-1)!} \ Leftrightarrow {2 ^ {2 ^ {k + 1}} + 2 ^ {k + 1}> \ left (2 ^ {2 ^ k} +2 ^ k \ right)} \ end {align} \ tag {2} [/ math].

Ahora

[matemáticas] \ begin {align} \ displaystyle 2 ^ {2 ^ k} + 2 ^ k <2 \ cdot {2 ^ {2 ^ k}} \ end {align} \ tag {3} [/ math]

y, dado que [math] \ displaystyle k <2 ^ k-1 [/ math],

[matemáticas] \ begin {align} \ displaystyle 2k <2 ^ {k + 1} \ end {align} \ tag {4} [/ math]

y

[matemáticas] \ begin {align} \ displaystyle 2k + 1 <2 ^ {k + 1} \ end {align} \ tag {5} [/ math]

Ahora multiplique los lados correspondientes de [matemáticas] (3) [/ matemáticas], [matemáticas] (4) [/ matemáticas], [matemáticas] (5) [/ matemáticas]

[matemáticas] \ begin {align} \ displaystyle \ left (2 ^ {2 ^ k} + 2 ^ k \ right) (2k + 1) \ cdot {2k} <2 ^ {2 ^ k + 1} \ cdot { 2 ^ {k + 1}} \ cdot {2 ^ {k + 1}} = 2 ^ {2 ^ k + 2k + 1} <2 ^ {2 ^ {k + 1}} + 2 ^ {k + 1 } \ end {align} \ tag * {} [/ math]

donde el último paso se basa en nuestro primer lema. Desde [matemáticas] \ displaystyle \ left (2 ^ {2 ^ k} + 2 ^ k \ right) (2k + 1) <\ left (2 ^ {2 ^ k} + 2 ^ k \ right) (2k + 1 ) \ cdot {2k} [/ math], la tesis sigue [math] \ blacksquare [/ math].

---

Paso 4

Acabamos de demostrar que si [math] k \ geq {2} [/ math] entonces [math] \ displaystyle m! \ Geq {2 ^ {2 ^ {k + 1}} + 2 ^ k}> (2k-1 )! [/ math] y, por lo tanto, [math] \ displaystyle m \ geq {2k} \ Rightarrow {m \ geq {4}} [/ math].

Entonces [math] m! [/ Math] es el producto de más de [math] k [/ math] números pares, al menos uno de los cuales es divisible por [math] 4 [/ math]. Entonces [math] \ displaystyle 2 ^ {k + 1} | m! [/ Math], pero encontramos [math] (**) [/ math] que [math] \ displaystyle 2 ^ k || m! [/ matemáticas], lo cual es una contradicción con la hipótesis [matemáticas] k \ geq {2} [/ matemáticas]

---

Esto muestra que [matemáticas] (n, m) = (2,3) [/ matemáticas] es la única solución.

Answer 2

Tropecé un poco, pero creo que probé que (2, 3) es la única solución.

Una observación:

[math] \ forall a, b, c \ in \ mathbb {N}: c \ mid a \ land c \ nmid b \ implica c \ nmid (a + b) [/ math]

Por lo tanto, [math] n [/ math] no puede tener un máximo factor común con [math] m! [/ Math] que no sea [math] 2 ^ k, k \ in \ mathbb {N} [/ math]; de lo contrario, [matemáticas] 2 ^ n + n [/ matemáticas] no sería divisible por esos factores, lo que implica que no puede ser igual a [matemáticas] m! [/ matemáticas].

Segunda observación:

Si [math] p_i [/ ​​math] es el i ésimo primo, [math] \ forall a, i, j \ in \ mathbb {N}, i \ neq j: p_i \ mid a \ implica p_i \ nmid (a + p_j) [/ matemáticas]

Por lo tanto, [math] n [/ math] tampoco puede tener factores primos diferentes de los factores primos en [math] m! [/ Math]. Eso significa que [math] n [/ math] solo puede tomar la forma de [math] 2 ^ k, k \ in \ mathbb {N} [/ math]. Lo que nos deja con:

[matemáticas] 2 ^ {(2 ^ k)} + 2 ^ k = m! [/ matemáticas]

Aquí está el bit ligeramente ondulado (pero solo porque no sé cómo expresarlo en matemáticas, no porque no sea cierto):

Si representamos el lado izquierdo y el lado derecho en la base 2, tenga en cuenta que el lado izquierdo solo tendrá exactamente dos dígitos iguales 1. Sin embargo, el lado derecho tendrá un número cada vez mayor de conjunto de bits (en la multiplicación, cualquier factor que no sea una potencia de 2 al menos duplicará la cantidad de bits).

La única vez que el lado derecho tendrá exactamente dos bits establecidos es cuando [math] m = 3 [/ math] o [math] m = 4 [/ math]. Podemos comprobar a mano que no hay una solución válida donde [math] m = 4 [/ math].

Por lo tanto, (2, 3) es la única solución.

Answer 3

Estás buscando pares ordenados [matemáticas] (n, m) [/ matemáticas]. Primero, está claro que no hay soluciones con [math] m \ leq 1 [/ math]. Si arreglas [math] m [/ math], puedes ver el exponente de [math] 2 [/ math] en la factorización de [math] m! [/ Math] Esto será:

[matemáticas] f (m) = \ lfloor \ frac {m} {2} \ rfloor + \ lfloor \ frac {m} {2 ^ 2} \ rfloor + \ dots [/ math]

Para valores muy grandes de [math] m [/ math], esto tiende hacia [math] m [/ math].

Puede observar que el lado izquierdo tiene un exponente de [math] 2 [/ math] en su factorización estrictamente menor que [math] n [/ math] (Sugerencia: mírelo en binario y observe que [math] n [/ math] es muy pequeño en comparación con [math] 2 ^ n [/ math], por lo que ocupará los bits más bajos). De hecho, el exponente será igual a la posición indexada a cero del bit más bajo de [math] n [/ math].

Para que ocurra la igualdad, necesita que los exponentes de [math] 2 [/ math] en ambos lados sean iguales. Por lo tanto, necesita [matemáticas] n = k2 ^ {f (m)} [/ matemáticas] donde [matemáticas] k [/ matemáticas] es impar. Ahora tienes eso:

[matemáticas] 2 ^ {k2 ^ {f (m)}} + k2 ^ {f (m)} = m! [/ matemáticas]

Ahora, debería ser fácil ver que nunca habrá soluciones en algún momento para valores mayores de [math] m [/ math]. Esto se debe a que el logaritmo del lado izquierdo se comporta como [matemática] 2 ^ m [/ matemática] mientras que el logaritmo del lado derecho se comporta como [matemática] m \ log m [/ matemática]. Puedes hacer este argumento más riguroso si quieres. Los “factores constantes” ocultos en este argumento no son realmente un problema.

Por lo tanto, hay muchas soluciones, y es una buena apuesta que no haya tantas. Para resolverlo, simplemente repita los valores pequeños de [math] m [/ math], y busque binariamente para encontrar su valor [math] n [/ math] asociado. Si terminas con un número entero positivo, estás listo para comenzar.

Answer 4

Por supuesto, n = 2, m = 3 es una solución, y el objetivo es mostrar que no hay otras.

Primero observamos que n = (m log_2 m), entonces 2 ^ n + n> (2 ^ (log_2 m)) ^ m = m ^ m> m!

El poder de 2 que divide m! es [m / 2] + [m / 4] +…> = m / 2 + m / 4 +… -log_2 m = m-log_2 m. Por otro lado, la potencia de 2 que divide el lado izquierdo es como máximo log_2 n.

Entonces obtienes (2 ^ m) / m

Aquí estaba un poco descuidado en los márgenes, por lo que tendrá que arreglarlo un poco, pero esa debería ser la idea principal.

Answer 5

Con MATLAB Ahora te puedo decir que 2 ^ 2 + 2 = 3 !, así que he encontrado la prueba más fácil de que no es imposible con números enteros positivos, pero no hay una buena manera simple de simplificarlo (al menos eso puedo pensar de, me encantaría saber si alguien encuentra un patrón algebraico)