La pregunta está motivada por una pregunta sobre una lata de número de fideos.
Cada elemento es un dígito entre el$0$$9$. Claramente, si se forma una cadena y considerar la posibilidad de que represente una base $10$ número entero, entonces obtendrá el mayor número si usted comienza con los dígitos de $999...$ y terminar con los ceros $...1111000000000$.
En este vídeo de youtube, el nombre de usuario numberphile (que hace entusiastas de la teoría de números videos para el profano) presenta los digis de su lado y se abre la siguiente generalizada pregunta:
Dado un conjunto de dígitos de mi fideos puede, ¿cuál es el mayor número que puede hacer con sólo
(a) la adición,
(b) la multiplicación
y
(c) exponenciación?
Así que aquí mis pensamientos:
En general, me dan un conjunto múltiple de dígitos y puedo usar cualquiera de estos dos números de formularios mayor que $9$. Y cada una de las tres operaciones es binario, es decir,
$(a,b)\mapsto a+b,\ \ \ \ \ \ $
$(a,b)\mapsto a\cdot b,\ \ \ \ \ \ $
$(a,b)\mapsto a^b,$
y sólo el último no es conmutativa y asociativa. La pregunta parece implicar que podemos usar bracketing, como nos gusta, asi que no te preocupes de estos.
Puedo decidir las dos primeras tareas, simplemente comprobando si la concatenación de los dígitos es mejor que la operación binaria para accieving los grandes números: Dado $n+1$ dígitos $(d_0,d_1,d_2,...,d_n)$, su concatenación
$\text{con}:(d_n,d_{n-1},d_{n-2},\dots,d_1,d_0) \mapsto \sum_{k=0}^n d_k 10^k$
nos da sumandos participación de la mayor y los poderes superiores de $10$.
Ya para $d_{n}\ne 0$ hemos
$\sum_{k=0}^{n} d_k 10^k < 10^{n+1},$
nos encontramos
$d_{n+1}\cdot\text{con}(d_n,\dots) =d_{n+1}\sum_{k=0}^{n} d_k 10^k < d_{n+1}10^{n+1} < \sum_{k=0}^{n+1} d_k 10^k = \text{con}(d_{n+1},d_n,\dots).$
es decir, $\text{con}$ es más fuerte que la multiplicación de los dígitos.
Sin embargo, la comprobación de algunos de los pares de dígitos para la tercera operación
$$2^3<3^2<23<32,$$
$$34<43<4^3<3^4$$
o
$$5^2=25<2^5<52$$
Puedo ver que no obvia el patrón! El algoritmo para construir el mayor número dependerá de los valores de los símbolos. Así que mi primera pregunta es esta (la pregunta en el vídeo):
(c) el Uso de la concatenación y la exponenciación, ¿cuál es el número más grande que puede hacer? ¿Cómo se puede demostrar que es realmente es el máximo?
Supongo que la prueba se debe hacer en general, pero aquí están los específicos dígitos del problema:
Voy a asumir que no se dispone de equipo será capaz de calcular esa absurda poder, pero estaría interesado en algunas de sus características, sin embargo.
Más ideas:
Ahora bien, si hay $N$ dígitos en total, los cuales son de uso gratuito en la concatenación, puede utilizar el número de conjuntos de hasta el tamaño de $N$ binario para la explotación. E. g. Si sólo había tres dígitos $\{0,3,7\}$, el número de conjuntos de tamaño $N=2$$\{\{0,37\}, \{0,73\},\{3,70\},\{7,30\}\}$. Nota: es evidente que Existe una regla adicional con respecto a cero, es decir, que usted no puede tener cadenas de partida con $0$.
Para cada número de $N$, hay un número fijo de posibles bracketings, como por ejemplo,$(a,((b,c),d))$, lo que determina el resultado, $a^{(b^c)^d}$ aquí. Supongo que el horquillado es un simple (hacia abajo) gráfico del árbol donde cada nodo, sean o ninguno de los dos (hacia abajo) offspings. Uno debe ser capaz de contar con estas.
La cantidad de números diferentes para la operación binaria (exponenciación es de principal interés aquí) uno puede generar es limitado por la cantidad de conjuntos de números se puede construir mediante la concatenación de los dígitos y el número de braketings para cada tamaño del conjunto. Cuántos diferentes lleno de soporte de las estructuras se puede tener?
Observe que para el no conmutativa exponenciación, los dos conjuntos de números $\{a,b\}$ tienen que ser reemplaza por pares $\{(a,b),(b,a)\}$ porque $a^b\ne b^a$.
Y mucho más difícil:
Teniendo en cuenta que las diferentes estructuras que puede terminar en el mismo número: ¿Cuál es la cantidad de resultados diferentes que usted puede tener? Hay un método funcional de trabajo fuera del "núcleo" de esta construcción?
Por último (menor prioridad):
Como tratamos con un alto número de dígitos que aquí, la mayoría de los resultados son relativamente bajos de la complejidad de Kolmogorov. Dada una cierta operación (por ejemplo, la exponenciación), el mayor número que podemos generar y el número de resultados que podemos tener, podemos concluir un patrón con respecto a el tamaño de la brecha entre los diferentes números más grandes, como una función del número de dígitos que se utiliza como entrada?
