Demostrando que *no* se puede hacer $2011$ de $1,2,3,4$ : bonito giro a lo habitual

Question

Un estudiante me hablaba de un rompecabezas que había encontrado: la idea era hacer $2011$ fuera de los números $1, 2, 3, 4, \ldots, n$ con las siguientes reglas/restricciones: los números deben permanecer en orden, y sólo se puede utilizar $+$ , $-$ , $\times$ , $/$ , ^ y $!$ . En palabras, "sumar menos dividir, exponer y factorizar". El juego consistía en construir $2011$ con $n$ lo más pequeño posible.

Para mi asombro, había conseguido hacer $n=5$ : de hecho

$$((1+2)!)!+(3!)^4-5=2011.$$

Ahora quería resolver el rompecabezas por completo demostrando que $n=1,2,3,4$ son imposibles.

Ahí es donde se pone interesante. Mi primer pensamiento fue "búsqueda por ordenador hecho". Pero no es tan fácil, porque el factorial es sólo un operador unario. Por ejemplo hay que descartar posibles cancelaciones sorprendentes entre números muy grandes, por ejemplo hay que comprobar

$$(1+2)!!!!!!!!!!!!!-3^{(4!!!!!!!!!!!)} \neq 2011.$$

Este en particular no es difícil de descartar, porque, por ejemplo, el lado izquierdo es un múltiplo de $3$ y la derecha no. En general, este enfoque tal vez pueda utilizarse para acotar el número de factoriales que pueden darse en cualquier presentación de $2011$ utilizando $1, 2, 3, 4$ sólo -- pero hacer esto riguroso parecía un poco delicado y me preguntaba si me estaba perdiendo algo. ¿Alguien tiene alguna idea?

EDIT: El heroico intento de Ron Maimon de tratar el problema por la fuerza bruta le ha llevado al interesante caso de $2011=(1+2)!!!...!!!/(3!!!...!!!/4!!!!...!!!)$ que parece ser más difícil de descartar que los otros: el juego aquí es demostrar que $2011$ no puede escribirse como $3!!!...!!!*4!!!!...!!!/3!!!!...!!!$ para cualquier elección de números de factoriales.

EDIT: Parece que las consideraciones de tamaño tienen que ver con el caso anterior. En definitiva, parece que la pregunta que hice puede responderse con un procedimiento bastante largo, pero finito(!). Gracias Ron por tus esfuerzos.

Answer 1

Esto es bastante sencillo de hacer a mano, aunque hay muchos casos. En primer lugar, hay que descartar el caso n=1, ya que 1 es un punto fijo para los factoriales. El caso n=2, es igualmente trivial, ya que 2 es también un punto fijo para los factoriales y 2011 no es un factorial.

Volveré a hablar de n=3 más adelante, primero trataré el problema de n=4.

Las operaciones binarias forman un árbol de análisis sintáctico, de modo que las operaciones binarias que se realizan dan un esqueleto sobre el que se pueden añadir factoriales. Hay exactamente cinco árboles binarios en 4 nodos, que enumero a continuación:

• emparejamiento: ((12)(34))
• adelante: (((12)3)4)
• hacia atrás: (1(2(34))
• centro-izquierda: ((1(23))4)
• centro-derecha: (1((23)4))

Estas cinco parentizaciones definen las cinco formas de aplicar operaciones binarias a las hojas 1,2,3,4. Los factoriales pueden venir en la hoja tres, produciendo 6,720,etc, en la hoja cuatro, produciendo 24, etc, o en una de las tres cantidades intermedias entre paréntesis.

No se puede aplicar un factorial al nodo superior, ya que 2011 no es un factorial. Para cada caso, hay exactamente cuatro nodos en cada árbol en los que se puede aplicar el factorial: en el 3, en el 4 y en los dos nodos intermedios.

Tres cantidades no pueden hacerlo

Para tratar n=4, hay que tratar metódicamente n=3. En este caso, sólo hay 2 parentizaciones diferentes

• izquierda: (1(23))
• derecho: ((12)3)

El factorial sólo se permite en 3, y en el valor del paréntesis interior. La cantidad exterior no puede obtener un factorial, ya que 2011 no es un factorial.

Ahora fíjate: la operación que implica el 1 es +,-,*,/,^. La última operación produce 1, reduciendo el tamaño del problema a binario, la operación de división produce un sinsentido, y el operador * simplemente elimina el nodo 1. Así que la única posibilidad es +/- (EDIT: si expandes el dominio a números racionales, de manera que puedas hacer 1/(¡¡¡2*3!!!) en etapas intermedias, hay muchos casos nuevos)

Esto significa que, la respuesta 2011 se produce desde la izquierda, en cuyo caso 2010 se escribe con (23), o desde la derecha, en cuyo caso 2011 se escribe con (33). Ambos son binarios y trivialmente imposibles.

De esta forma se dispone de n=3

Cuatro cantidades se reducen en su mayoría a tres

De nuevo, cuatro cantidades se reducen a 3 cuando se considera la operación binaria que implica el 1. Si esta operación no es + o -, debe matar el nodo (EDIT: excluyendo las operaciones con números racionales), reduciendo así el árbol a 3,2 o 1 objetos.

La posibilidad restante es que 1 se sume a una cantidad. Esto produce los siguientes problemas de tres cantidades:

• ((3 3) 4) hacer 2011
• (3(3 4)) hacer 2011
• (2(3 4)) hacer 2010 o 2011
• ((2 3) 4) hacer 2010 o 2011

y exactamente un problema verdadero de cuatro cantidades * ((1 + (23)) 4)

El verdadero problema de cuatro cantidades tiene 15 posibles combinaciones de operaciones y 4 lugares para poner los factoriales. Primero prescindiré de los casos de tres cantidades.

2 3 4 o 3 3 4 no hacen 2011

El nodo superior que hace el 2011 no puede ser ^, porque el 2011 no es una potencia. No puede ser * porque 2011 es primo. Esto deja +,-,/. Llamaré A_n a la iteración factorial n veces:

• (3_n + 3_m)_k + 4_l

• (3_m - 3_n)_k + 4_l

• (3_m * 3_n)_k + 4_l

• (3_m / 3_n)_k + 4_l

• (3_m ^ 3_n)_k + 4_l

• (3_n + 3_m)_k - 4_l

• (3_m - 3_n)_k - 4_l

• (3_m * 3_n)_k - 4_l

• (3_m / 3_n)_k - 4_l

• (3_m ^ 3_n)_k - 4_l

Para k>0, estos no pueden ser 2011 por razones de paridad. Para k=0, los productos/cocientes se excluyen por razones de paridad (ya que 3_m y 3_n nunca son diferentes en 1, su cociente es siempre par o igual a 1--- 1 se excluye porque 2010 no es un factorial iterado de 4, el caso de la exponenciación se excluye por la divisibilidad por 3 para l>0 y por el hecho de que 2015 y 2007 no son potencias para l=0). Esto deja

• 3_n + 3_m - 4_l
• 3_n - 3_m + 4_l
• 3_n - 3_m - 4_l

(el caso all plus está excluido por los límites de tamaño y una búsqueda finita). Es imposible que ambos n,m sean mayores que 1, o bien la suma es par. Así que exactamente uno de n o m es 1. Entonces la reducción en módulo 6 da 3 para l>1 n>1 y 2011 es 1 en módulo 6.

El caso en el que el primer 3 se sustituye por 2 se trata exactamente igual.

• (3_n + 3_m)_k / 4_l
• (3_m - 3_n)_k / 4_l
• (3_m * 3_n)_k / 4_l
• (3_m / 3_n)_k / 4_l
• (3_m ^ 3_n)_k / 4_l

Esto no puede ser 2011 para k>0 por razones de primacía (2011 no es el cociente de dos factoriales que no sean 2011!/2010! y (33) no hace 8044). Esto deja los casos k=0:

EDIT: Yo también me he saltado estos casos no triviales.

• (3_n + 3_m) = 2011 4_l
• (3_m - 3_n) = 2011 4_l
• (3_m * 3_n) = 2011 4_l : SIN RESOLVER
• 3_m = 2011 4_l 3_l
• (3_m ^ 3_n) = 2011 4_l

El caso A!= 2011 B! C! se resuelve en la siguiente sección, y esto se encarga de 3_m = 2011 4_l 3_l. El caso 3_m^3^n se resuelve observando que el factorial del lado derecho debe ser suficientemente mayor que el factorial del lado izquierdo para incluir un nuevo primo. ¡A! + B! = 2011 C! requiere que A>C y B>C y WLOG A>B, de modo que, dividiendo, se obtiene C(C+1)...(C+(A-C)) + C(C+1)..(C+(B-C)) = 2011, lo que requiere por primacía C=B o C=B-1 pero 3_k y 4_m nunca pueden ser exactamente iguales por primacía del factorial, y no pueden diferir en 1, excepto en m=0 k=0, porque siempre son ambos pares.

El caso 3_m * 3_n = 2011 4_l no está resuelto, y es similar al otro caso no resuelto de abajo.

Luego está (3(34)). En este caso, el nodo superior tampoco puede ser * o ^ porque 2011 no es una potencia ni un producto.

EDITAR: MÁS (3(34))

Así que hay otros 15 casos (antes, los anoté, pero no los resolví).

• 3_l + (3_m + 4_n)_p :

El interior del parén es al menos 7, ¡7! es 5040, demasiado grande, así que p=0. Las cantidades 3_l+3_m son pares a menos que exactamente una de l o m sea cero, así que tienes 3 +3_m + 4_n , que es una búsqueda finita para pasar por 2011.

• 3_l + (3_m - 4_n)_p

El interior del parén no puede ser negativo, y si es positivo, m debe ser al menos 1, para que el segundo término sea par. Esto significa que el primer término debe ser impar, por lo que l=0. Esto hace que 3 + (3_m - 4_n)_p = 2011, y 2008 no es un factorial, por lo que p=0. Así que quieres que la diferencia de 3_m y 4_n sea 2008, lo que es imposible si n>0 porque 2008 no es 0 mod 3. Así que 2004 debe ser 3_m, lo cual es imposible.

• 3_l + (3_m * 4_n)_p

2011 es 1 mod 3, y esto es cero mod 3.

• 3_l + (3_m / 4_n)_p

Aquí se plantea la cuestión de cómo interpretar los cocientes yo lo interpretaré como la parte entera. Así que el argumento interior del parén puede ser 0 o 1 (3/4 y 6/4), haciendo que 3_l 2010 o 2011, sea imposible. Así que la parte interna del parén no es 0 ni 1. El cociente de dos factoriales que es mayor que 2 es en sí mismo un número entero, por lo que se obtiene la suma de dos factoriales, que es par a menos que l=0 o p=0.

Si l=0, tienes un factorial que da 2008, que, como 2008 no es factorial, da p=0, y 2008 es un cociente de factoriales que es imposible, porque no es factor en el producto de números consecutivos.

Esto deja p=0, l distinto de cero. (3_l - 2011) * 4_n + 3_m = 0, que por los signos requiere que 3_l<2011, por lo que l es 1,2,3. y esto es los dos casos:

• (6 - 2011) * 4_n + 3_m = 0
• (720 - 2011) * 4_n + 3_m = 0

Ambas ecuaciones son imposibles porque los coeficientes no triviales, 2005 y 291, no pueden ser el cociente de dos factoriales, ya que ninguno es un producto de números consecutivos.

• 3_l + (3_m ^ 4_n)_p

Esto es cero mod 3, y 2011 no lo es.

• 3_l - (3_m + 4_n)_p

Esto es cero mod 3 a menos que n=0 y p=0. 3_l - 3_m + 4 = 2011, lo que significa que la diferencia de 2 factoriales iterados de 3 tiene que ser 2007, que es impar, así que esto es imposible.

• 3_l - (3_m - 4_n)_p

Esto es cero mod 3 a menos que n=0 y p=0, 3_l - 3_m - 4 = 2011 por lo que la diferencia de 2 factoriales iterados de 3 tiene que ser 2015, que no es cero mod 3, así que hecho.

• 3_l - (3_m * 4_n)_p

Esta cantidad es cero mod 3, a diferencia de 2011.

• 3_l - (3_m / 4_n)_p

Estas dos cantidades serán ambas pares a menos que p=0, l=0, o la cantidad entre los paréntesis sea 1. l=0 se excluye ya que el resultado es menor que 3, y si la cantidad entre los paréntesis es 1, entonces 3_l debe ser 2010, no es posible. Así que esto requiere p=0, y esto se convierte en las ecuaciones diofánticas

• 3_m = (3_l- 2011)4_n

En este caso, 3_l debe ser mayor que 2011, por lo que l>2. 3_m/4_n es un cociente de dos factoriales, por lo que se convierte en

(¡A!/(B!(A-B)!))*(A-B)! = (3_l - 2011)

El lado izquierdo es par en cualquier caso no trivial, y el lado derecho es impar, descartando esto por paridad.

• 3_l - (3_m ^ 4^n)_p

Esto es cero mod 3, así que no es 2011.

• 3_l / (3_m + 4_n)_p
• 3_l / (3_m - 4_n)_p
• 3_l / (3_m * 4_n)_p
• 3_l / (3_m / 4_n)_p
• 3_l / (3_m ^ 4_n)_p

El cociente de dos factoriales no triviales es siempre un producto de números consecutivos, por lo que no puede ser 2011 a menos que el superior sea 2011! y el inferior 2010! 3_l nunca es 2011. Se puede concluir que o bien l=0 o bien p=0. l=0 es imposible, ya que el resultado sería menor que 3, así que p=0 para todo lo anterior. Esto da las siguientes 4 ecuaciones diofánticas

• 3_l = 2011*(3_m + 4_n)
• 3_l = 2011*(3_m - 4_n)
• 3_l = 2011*(3_m * 4_n)
• 3_l = 2011*(3_m ^ 4_n)
• 3_l = 2011*(3_m / 4_n)

Para los cuatro primeros casos, l debe ser mayor que 3 porque 3!!!=720! que no tiene un factor de 2011. Así que todos estos son grandes factoriales no triviales.

Consideremos una forma más general de la ecuación de la suma, la ecuación del primer caso anterior:

• A! = 2011 (B!+C!)

Sin pérdida de generalidad A>B>C, así que dividiendo por C! se obtiene A!/C! = 2011(B!/C!+1) donde las cantidades A!/C! y B!/C! son productos de enteros consecutivos, al menos uno de los cuales es par, porque A no es igual a B, y ambos son pares a menos que B=C+1. Así que B=C+1, y se obtiene ¡A!/C! = 2011(C+1), o ¡A!=2011(C+1)! que es imposible porque 2011 no es un producto de enteros consecutivos. Lo mismo descarta el caso del signo menos.

• A! = 2011 B! ¡C!

De nuevo, WLOG, B>C, esto se puede reescribir:

• (¡A!/B!(A-B)!) ((A-B)!/C!(A-B-C)!) ¡(A-B-C)! = 2011

donde todo se expresa en términos de los coeficientes binomiales multiplicativos más fundamentales. Esto requiere que cada factor sea o bien 1 o bien 2011, lo que requiere o bien A=B+C o bien A=B+C+1, ya que el último factor no puede ser igual a 2011 en ningún caso. ¡En ambos casos, los dos coeficientes combinatorios se convierten en uno, y el resultado es que C=1 o 0 y B=2010 mientras que A=2011, dando las dos soluciones triviales 2011! ¡= 2011 * 2010! 1! y 2011! ¡= 2011 2010! 0!, y ninguna otra (estas soluciones triviales no funcionan, no tienen C>4 por ejemplo). Ya está hecho.

• A! = 2011 B!^C!

Donde C>4. Como C>4, y para B mayor que 2, (B!)^4> (2B)! (fácil de demostrar usando la fórmula de Stirling), se puede concluir que A>2B, de modo que hay un nuevo primo entre B y 2B que está contenido en A! que no está contenido en el lado derecho, hecho. Esto también funciona cuando C es 3, por lo que resuelve el caso paralelo de (33)4 anterior.

El último caso a considerar es el cociente del cociente, que se reordena en

• 3_l * 4_n = 2011 * 3_m

aquí, o bien l es mayor que 3, o bien n es mayor que 2, para que uno de los dos objetos de la izquierda tenga un factor de 2011, por lo que se trata de nuevo de grandes factoriales. La forma general

• ¡A! B! = 2011 C!

para los grandes A, B y C, WLOG A

• 2011 ((A+B)!/A!B!) = (A+B)(A+B-1)..(A+B-y+1)

En esta fórmula, A y C son ambos iterados factoriales de 3, mientras que B es un iterado factorial de 4. Esto significa que C es o bien igual a A (lo que no funciona) o bien enormemente mayor que A, ¡siendo al menos A! Para que el tamaño del lado derecho y el izquierdo sean iguales, B debe ser aproximadamente del mismo tamaño que C.

El LHS es B^A/A!, mientras que el lado derecho es B^y, por lo que para coincidir, A e y tienen que ser del mismo orden.

Ahora el lado derecho es divisible por y!, mientras que el lado izquierdo no puede ser divisible por algo tan grande como A! Esta es una propiedad del triángulo de Pascal, que ((A+B)!/A!B!) no es divisible de nuevo por A!. La razón es un simple conteo de primos:

El número de potencias de 2 en N! es N/2 + N/4 + N/8 + N/16... + N/(2^(log_2(N)) donde la división significa la división por el suelo. Esto es asintótico a N, y esto significa que el número de potencias de 2 simplemente se cancela entre el numerador y el denominador cuando A+B=C. Si quieres que y! sea un factor en el elemento resultante del triángulo de Pascal, necesitas potencias de 2 adicionales en C!, una cantidad aproximadamente igual a 2A+B. No debería haber tantas potencias de 2 en (C!). Lo mismo ocurre con las potencias de 3, o de cualquier otro primo menor que A.

Así que debería ser imposible satisfacer la ecuación basándose sólo en el recuento de potencias primarias, pero este argumento no lo demuestra, porque B es tan enorme comparado con A, que el error en la estimación de la potencia de dos para ((A+B)!) es ingenuamente mayor que A. Pero hay entradas Impares en el triángulo de Pascal arbitrariamente alejadas, especialmente cerca del borde izquierdo, así que debe haber mejores límites en las potencias primarias que ocurren en el triángulo de Pascal que los que he dado. Estoy seguro de que ¡y! no puede entrar en la entrada del triángulo de Pascal para y grandes, pero no puedo dar un argumento sólido. Así que lo dejaré como no resuelto por ahora.

Me sorprende que este caso sea mucho más difícil que los otros, porque es relativamente obvio que lo puramente multiplicativo no puede funcionar, que se necesita lo aditivo.

de todos modos: SIN RESOLVER. Pero el boceto anterior podría resolverlo si se precisa.

EDIT (2 (3 4)) no hace 2011 (para completar)

Me olvidé de calcular los 2(34) casos para hacer el 2011. El nodo superior no puede ser * o ^, ya que 2011 no es primo ni potencia, y no puede ser - o /, porque 2011 es mayor que 2.

• 2 + (3_m + 4_n)_p
• 2 + (3_m - 4_n)_p
• 2 + (3_m * 4_n)_p
• 2 + (3_m / 4_n)_p
• 2 + (3_m ^ 4_n)_p

Se excluye p>0 porque 2009 no es un factorial. 3_m + 4_n, 3_m - 4_n no funciona para m>0 debido a la paridad, así que m=0, y así se hace. El caso de la potencia 3_m^4_n se excluye porque 2009 no es una potencia. (3_m *4_n) es cero mod 3, y 2009 no lo es, así que el único caso es 3_m=2009 4_m, que es de la forma

• A! = 2009 B!

o (¡A!/B!(A-B)!)(A-B)! ¡= 2009, que se excluye por paridad a menos que A=B+1, cuando se obtiene la solución trivial 2009! = 2009*2008!, que no coincide con los factoriales iterados de 3 y 4.

Para permitir las fracciones, consideraré el único proceso de división razonable

• 2/(3_m/4_m) = 2*4_m/3_m = 2011

se trata de un número entero par cuando el numerador es mayor que el denominador, es decir, 2( ¡A!/(¡B!(A-B)!)(A-B)!, por lo que se excluye.

2 3 4 no hace 2010

Ahora 2010 = 2 * 3 * 5 * 67. La descomposición en ((23)4) sólo puede obtener factoriales sobre 3 y 4.

• (2+3_m)_n +4_p

• (2-3_m)_n +4_p

• (2*3_m)_n +4_p

• (2/3_m)_n +4_p

• (2^3_m)_n +4_p

• (2+3_m)_n -4_p

• (2-3_m)_n -4_p

• (2*3_m)_n -4_p

• (2/3_m)_n -4_p

• (2^3_m)_n -4_p

Para estos casos, basta con observar que 2010 no es divisible por 4, por lo que n=0 o n=1, o el argumento del factorial es 1, y una tediosa enumeración los agota.

• (2+3_m)_n *4_p
• (2-3_m)_n *4_p
• (2*3_m)_n *4_p
• (2/3_m)_n *4_p
• (2^3_m)_n *4_p

El año 2010 no es divisible por 4, por lo que quedan descartados.

• (2+3_m)_n /4_p
• (2-3_m)_n /4_p
• (2*3_m)_n /4_p
• (2/3_m)_n /4_p
• (2^3_m)_n /4_p

Estos dan la relación 2010 4^p = (2*3_n)_m. Mirando en módulo 7 y 67 prohíbe que esta ecuación se mantenga para cualquier m,n.

• (2+3_m)_n ^4_p
• (2-3_m)_n ^4_p
• (2*3_m)_n ^4_p
• (2/3_m)_n ^4_p
• (2^3_m)_n ^4_p

2010 no es una potencia.

((1+(23))4) no hace 2011

Hay 15 casos, ya que el nodo superior no puede ser * por primacía, y no puede ser ^ ya que 2011 no es una potencia:

• (1+(2+3_l)_m)_n + 4_p

• (1+(2-3_l)_m)_n + 4_p

• (1+(2*3_l)_m)_n + 4_p

• (1+(2/3_l)_m)_n + 4_p

• (1+(2^3_l)_m)_n + 4_p

• (1+(2+3_l)_m)_n - 4_p

• (1+(2-3_l)_m)_n - 4_p

• (1+(2*3_l)_m)_n - 4_p

• (1+(2/3_l)_m)_n - 4_p

• (1+(2^3_l)_m)_n - 4_p

n=0 por paridad. Esto reduce el problema por asociatividad en 2,3,4 haciendo 2010.

• (1+(2+3_l)_m)_n / 4_p
• (1+(2-3_l)_m)_n / 4_p
• (1+(2*3_l)_m)_n / 4_p
• (1+(2/3_l)_m)_n / 4_p
• (1+(2^3_l)_m)_n / 4_p

Estos son los únicos casos realmente nuevos. En este caso, se obtiene 2011*4_p = (1 + (algo))_n, lo que está prohibido al mirar el módulo 2011.

Es muy probable que tu amigo haya hecho una búsqueda de este tipo para el caso n=5 para encontrar la solución especial.

Answer 2

Si se permiten las raíces cuadradas y los porcentajes (y el menos unario), entonces hay una serie de soluciones, la más sencilla probablemente sea

$$2011 = (-1 + (2 + 3!)!\%) \div \sqrt{4\%}$$

Hace muchos años, escribí un sencillo programa para Windows llamado $200$ Arriba (enlace a la carpeta de Dropbox) para resolver problemas como estos:

$\hspace{1.75in}$

El dominio de cálculo es $\mathbb{Z}/d$ para un denominador determinado $d\in\mathbb{N}$ (y con límites en la magnitud del numerador).

Observe que, en la imagen anterior, la solución para 2018 es

$$ \large 2018 \;\;=\;\; \big( \sqrt[\sqrt{\cdot \dot{1}}]{\Large 2} \; + \; 3!!\%\% \big) \; \div \; \cdot 4\%. $$