octpuzzle 2880x1620 lede

El mes pasado, presentamos tres rompecabezas que parecían lo suficientemente ordinarios pero contenían un giro numérico. Escondido debajo de la superficie estaba el misterioso número trascendental e. Más familiar como base de logaritmos naturales, el número e de Euler es una constante universal con una expansión decimal infinita que comienza con 2.7 1828 1828 45 90 45... (espacios añadidos para resaltar el cuasi-patrón en los primeros 15 dígitos después del punto decimal). Pero, ¿por qué, en nuestros rompecabezas, aparentemente aparece de la nada?

Antes de intentar responder a esta pregunta, necesitamos aprender un poco más sobre las propiedades y alias de e. Al igual que su primo trascendental πe se puede representar de innumerables maneras, como la suma de series infinitas, un producto infinito, un límite de secuencias infinitas, una fracción continua increíblemente regular, y así sucesivamente.

Todavía recuerdo mi primera introducción a e. Estábamos estudiando logaritmos comunes en la escuela, y me maravillé de su capacidad para convertir problemas de multiplicación complicados en simple suma simple simplemente representando todos los números como potencias fraccionarias de 10. ¿Cómo, me preguntaba, se calculaban los poderes fraccionarios e irracionales? Es, por supuesto, fácil calcular potencias enteras como 102 y 103, y en un apuro incluso podrías calcular 102.5 encontrando la raíz cuadrada de 105. Pero, ¿cómo descubrieron, como afirmaba la tabla de registro, que 20 era 10?1.30103? ¿Cómo podría construirse una tabla completa de logaritmos de todos los números desde cero? Simplemente no podía imaginar cómo se podría hacer eso.

Más tarde aprendí sobre la fórmula mágica que permite esta hazaña. Da una pista de dónde vino lo "natural" en "logaritmos naturales":

ex = 1 + x1!+x22!+x33!+x44!+x55!+.

Para los poderes negativos, los términos alternativos son negativos como se esperaba:

e-x = 1 – x1!+x22!x33!+x44!x55!+.

Estas poderosas fórmulas permiten el cálculo de cualquier potencia de la misteriosa e para cualquier número real, entero o fracción de infinito negativo a infinito, con cualquier precisión deseada. Permiten la construcción de una tabla completa de logaritmos naturales y, a partir de eso, logaritmos comunes, desde cero.

El caso especial de esta fórmula para x = 1 da esta famosa representación de e:

= 1 + 11!+12!+13!+14!+15!+.

Además, e tiene muchas propiedades sorprendentes, algunas de las cuales descubriremos en las soluciones a nuestros problemas. Pero la única propiedad que va a la esencia de e y la hace tan natural para logaritmos y situaciones de crecimiento exponencial y decadencia es esta:

ddxeex.

Esto dice que la tasa de cambio de ex es igual a su valor en todos los puntos. Cuando x representa el tiempo, significa una tasa de crecimiento (o decaimiento, para xnegativo) que es igual al tamaño o cantidad que se ha acumulado hasta ahora. Hay innumerables fenómenos en el mundo real que hacen exactamente esto durante períodos de tiempo, y los conocemos como ejemplos de crecimiento exponencial o decadencia. Pero, utilidad aparte, hay un elemento de perfección estética y naturalidad en esta propiedad de e que realmente puede inspirar asombro. Incluso lleva una lección moral; Me gusta pensar en ella como una función zen que, en su búsqueda de crecimiento, siempre está en perfecto equilibrio, nunca alcanzando más o menos de lo que ha ganado.

Una advertencia: en las soluciones de rompecabezas a continuación, entraremos en matemáticas que son un poco más avanzadas y de aspecto formidable de lo que es normal para esta columna de rompecabezas. No te preocupes si las ecuaciones hacen que tus ojos se deslumlumn; solo trata de seguir el argumento general y los conceptos. Mi esperanza es que cualquiera pueda salir con alguna idea, por confusa que sea, sobre cómo y por qué aparece en nuestros rompecabezas. En la serie de televisión de la BBC The Ascent of Man,Jacob Bronowski dijo sobre la escritura matemática de John von Neumann que es importante al leer matemáticas seguir la melodía del argumento conceptual: las ecuaciones son simplemente la "orquestación hacia abajo en el bajo".

Ahora intentemos rastrear cómo aparece e en nuestros rompecabezas.

Puzzle 1: Partición

Tomemos cualquier número, como 10. Divídelo en un número de piezas idénticas, como dos 5, y multiplícalos juntos: 5 × 5 = 25. Ahora, podríamos haber dividido 10 en tres, cuatro, cinco o seis piezas idénticas y hacer lo mismo. Esto es lo que le sucede a nuestro producto cuando lo hacemos:

2 piezas: 5 × 5
= 25 3 piezas: 3.33 × 3.33 × 3.33 = 37.04 4
piezas: 2.5 × 2.5 × 2.5 × 2.5 = 39.06
5 piezas: 2 × 2 × 2 × 2 × 2 = 32
6 piezas: 1.67 × 1.67 × 1.67 × 1.67 × 1.67 × 1.67 = 21.43

Puedes ver que el producto aumenta, alcanza lo que parece ser un máximo y luego comienza a disminuir. Intente hacer lo mismo con algunos otros números como 20 y 30. Notarás que lo mismo sucede en todos los casos. Esto no tiene nada que ver con los números en sí, sino que es causado por una propiedad única del número e.

Vea si puede averiguar cuándo el producto alcanza un máximo para un número determinado y qué tiene que ver esto con e.

Como mencioné en la sugerencia para 1a, el producto alcanza un máximo cuando el valor de cada pieza es más cercano a e. Para ser más precisos, los dos productos más altos se obtendrán cuando los valores de las piezas se encuentren a cada lado de e. Para los números pequeños de tamaño cotidiano que estamos considerando aquí, el valor más alto se obtiene para la pieza cuya diferencia de es la más pequeña.

b. Para el número 10, el producto más grande (39.06) es aproximadamente un 5.5% más grande que el siguiente más grande (37.04). Sin calcular la diferencia real, ¿puede adivinar qué número menor que 100 tiene la diferencia porcentual más pequeña entre el producto más grande y el siguiente más grande? ¿Por qué debería ser esto?

Desde arriba, es fácil ver que dos productos estarán más juntos cuando los valores de las dos piezas adyacentes son casi equidistantes de e,uno más bajo que e y el otro más alto. (Esto es estrictamente cierto solo si la función es simétrica alrededor de e, que no lo es, pero en este rango está lo suficientemente cerca, como explicó excelentemente Michel Nizette). Si el número original es N, esto tenderá a suceder cuando la parte fraccionaria de la relación Ne está cerca de 0,5, es decir, cuando Ne se encuentra cerca del punto medio entre dos enteros. Así que si construyes una tabla de Ne para N hasta 100 y busque la parte fraccionaria más cercana a 0.5, obtendrá el entero requerido: 53. Dividiendo 53 por e da 19.4976 y una diferencia de solo 0.0013% para los productos producidos por 19 y 20 piezas.

c. ¿Puede explicar por qué surge e en este problema aparentemente simple?

Como explicaron los lectores Lazar Ilic, Ashok Khatri, Alan Olson, Kurt Godel, TG, Atul Kumar y Michel Nizette,la respuesta implica algunos cálculos elementales, específicamente, debe encontrar el máximo de una función estableciendo su derivada en cero. Nuestra función es (nx)x, y el valor de cada pieza es nx. El logaritmo de la función es x(ln nx), y podemos maximizar eso en su lugar, lo cual es algo más fácil. Si puedes resolver esto manualmente, ¡felicitaciones para ti! Pero si hacer cálculo no es su taza de té, puede simplemente escribir"d/dx(x ln n/x) = 0" en Wolfram Alpha. La derivada se evalúa como ln(nx) = 1, y sale la solución xne para n y x positivos. Por lo tanto, el valor de la pieza óptima es nx = e.¡Voila! Así es como surge e y da el máximo producto.

Esto nos enseña que e tiene una propiedad de optimalidad. Puede aparecer en situaciones que impliquen encontrar un máximo o mínimo, como veremos en el puzzle 2. La versión más básica de esta propiedad de e se ve si se calcula el valor de la función x1/x para todos los números reales positivos (esto se conoce como problema de Steiner). De todos los números reales infinitos, la x que produce el valor más alto para esta función es e. Maximizando x1/x es equivalente a maximizar (lnx)x, cuya derivada (1lnx)x2 es cero en ln x = 1, cuando x = e.

Puzzle 2: Unión

Como señalaron los lectores, esta fue una reafirmación del conocido problema de la secretaria. A continuación se resumen los puntos esenciales.

Un heredero tiene que elegir el mejor de los 10 cónyuges candidatos potenciales bajo las siguientes reglas. Los candidatos son entrevistados uno tras otro, y aceptados (si se sospecha que son los mejores) o rechazados antes de que se considere al siguiente candidato. Un candidato rechazado no puede ser retirado, y una vez que un candidato es aceptado, el proceso se detiene. El último candidato debe ser aceptado por defecto si el proceso no ha terminado para entonces.

 ¿Cómo puede el heredero maximizar sus posibilidades de elegir al mejor candidato, suponiendo que no haya vínculos?

Esta situación requiere que el heredero rechace incondicionalmente un número específico de candidatos (la fase de "rechazo") seguida de una "fase de selección" en la que selecciona al primero entre los candidatos restantes que ocupa un lugar más alto que todos los rechazados anteriormente. Las posibilidades de elegir al mejor candidato se maximizan cuando la fase de rechazo es una duración específica. La probabilidad disminuye si la fase de rechazo es más larga (el mejor candidato puede ser más propenso a ser rechazado) o más corta (no tiene suficiente experiencia para clasificar a los candidatos adecuadamente, lo que resulta en la aceptación de candidatos de menor rango).

Esto se conoce como un problema de "parada óptima", y e aparece en su solución debido a su propiedad de optimalidad. Para un gran número de candidatos n, el número óptimo de candidatos rechazados inicialmente debe ser igual a n dividido por e.

Aquí están los cálculos de probabilidad para n = 10 si la fase de rechazo (r) = 3. Primero, tenga en cuenta que el mejor candidato podría aparecer en cualquier momento de la serie de 10 entrevistas, con una probabilidad de 1 en 10 (1n) de estar en cualquier posición particular. Para la posición de cada entrevistado (i), multiplicamos esta 110 por la probabilidad de que el mejor candidato sea seleccionado en ese puesto. Luego sumamos las probabilidades para todas las posiciones y construimos nuestra expresión general.

  • Si el mejor candidato está en las posiciones 1 a 3, será rechazado automáticamente. Probabilidad (p) de seleccionar el mejor candidato = 110 × 0 = 0.
  • Si el mejor candidato está en la posición 4, siempre será seleccionado. Probabilidad p de este resultado = 110 × 1 = 110 = 1n.
  • En la posición 5, el candidato será seleccionado si el candidato anterior de mayor rango está en las posiciones 1 a 3, pero no 4. Así que p = 110 × 34 = 1n × r(i1) = rn × 1(i1).
  • En la posición 6, el candidato se selecciona si el candidato anterior de mayor rango está en las posiciones 1 a 3, pero no 4 o 5. Así que p = 110 × 35 = 1n ×  r(i1) = rn × 1(i1).
  • ...
  • En la posición 10, p = 110  ×  39 =  1n  × r(i1) = rn × 1(i1).

Como puede ver, obtenemos la misma expresión para cada posición en la fase de selección: rn × 1(i1). (La expresión para la posición 4 se puede escribir como 110 × 33 = rn × 1(i1) para ajustarse al patrón).

Toma rn a partir del signo de suma, esta suma, la probabilidad de encontrar al mejor candidato, se puede escribir:

 
 

La probabilidad correspondiente de encontrar el mejor candidato para r = 4 candidatos iniciales rechazados es del 39,8%. Estos son los dos valores más altos, y la probabilidad de mayores o menos rechazos iniciales disminuye. ¿Te recuerda esto al rompecabezas de la partición? Eso no es casualidad, como veremos a continuación.

b. ¿Cómo cambian las posibilidades del heredero si hay un 10% de posibilidades de empate por el primer lugar?

Dado que el heredero ahora tiene dos candidatos igualmente clasificados el 10% del tiempo, las posibilidades de encontrar el mejor candidato aumentan.

c. Este problema es un problema clásico cuya solución tiene algo que ver con e. ¿Puede explicar cómo entra en escena?

¡Resulta que e entra en escena dos veces en este problema! A medida que el número n se hace grande, el número de Euler aparece tanto en la probabilidad de encontrar la mejor opción como en la proporción de casos iniciales a rechazar.

La expresión de probabilidad que derivamos anteriormente puede ser representada, a medida que n crece hasta el infinito, por una integral sustituyendo por el límite de rn (la fracción de rechazo), p para (i1)n (la probabilidad incremental en cada n) y dp para 1n (la tasa de cambio de un entero al siguiente) . Esto da el límite de la probabilidad como:

x1x1pdp=xlnx.

Una vez más, la expresión en el lado derecho es similar a las que vimos en el problema de partición. Estableciendo la derivada en cero, encontramos que tanto la fracción óptima de candidatos que deben ser rechazados como la probabilidad de hacer la mejor elección son , o alrededor del 36,8%.1e

d. ¿Cómo puede el heredero alcanzar el rango esperado más alto de su candidato elegido en este escenario de elección más práctico?

En el escenario clásico anterior, el heredero adopta una estrategia de todo o nada rechazando a los primeros candidatos y luego seleccionando el primero que mejore a todos los rechazados. Si bien esto maximiza la probabilidad de encontrar al mejor candidato, también puede resultar en que se quede atrapado con un candidato de bajo rango si el mejor candidato estaba entre los rechazos iniciales. Para evitar esto, su mejor estrategia práctica es ser muy exigente para comenzar y buscar a los mejores candidatos, y luego reducir la quisquillosidad conformándose con candidatos simplemente buenos a medida que se agota el número de candidatos.

Esta estrategia se puede precisar comenzando hacia atrás desde que solo queda el último candidato. Esta persona podría ubicarse en cualquier lugar del ranking con la misma probabilidad. Así que la expectativa es que su rango final sea promedio (5.5 en este caso). Por lo tanto, debe aceptar al penúltimo candidato si estuviera entre sus cinco primeros hasta este punto, aunque puede que no sea el mejor absoluto. Cuando quedan dos candidatos, la expectativa para el mejor clasificado de los dos será de aproximadamente 3.67, por lo que para el tercer al último candidato debe estar satisfecho con un candidato que esté entre los tres primeros. Al calcular exactamente qué tan exigente debe ser en cada etapa, tiene una mejor oportunidad de obtener un muy buen candidato que mediante el uso del algoritmo clásico.

Rompecabezas 3: Unión

Un gran auditorio está organizando un espectáculo que solo admite parejas. Cuando una pareja entra en el auditorio, eligen al azar un par de asientos uno al lado del otro. Cada nueva pareja hace lo mismo, y en muchos casos esto resulta en asientos individuales vacíos entre parejas. Los asientos continúan hasta que solo quedan asientos individuales. Luego se declara el auditorio lleno y comienza el espectáculo.

un. ¿Qué proporción de asientos se espera que se dejen sin llenar cuando se detengan los asientos?

La respuesta, a medida que aumenta el número de escaños, se acerca o alrededor del 13,5%.1e2

b. ¿Cómo entra en este teatro de unión?

Veamos qué sucede cuando hay un pequeño número de asientos etiquetados alfabéticamente. Llamemos A los números de asientos vacíos esperados E1, E2, E3, E4, y así sucesivamente, donde los subíndices son el número de sillas vacías seguidas.

  • Un solo asiento está vacío: una pareja no puede ocuparlo, por lo que E1 = 1.
  • Para dos asientos, no hay asiento vacío, por lo que E2 es 0.
  • Para tres asientos, la pareja puede ocupar AB o BC, dejando un asiento vacío en cada caso, por lo que E3 = 1.
  • Para cuatro asientos, una pareja puede ocupar BC, dejando dos asientos vacíos, o pueden ocupar AB o CD, sin dejar ninguno. Esto da tres configuraciones que producen un total de dos asientos vacíos, dando una expectativa promedio de E4 = .23

Al jugar con las relaciones entre estos y los siguientes números, Lazar Ilic y Michel Nizette pudieron derivar una relación de recurrencia que les permitió predecir los asientos no ocupados para el número actual de asientos (n) utilizando los resultados anteriores para – 1 y – 2 asientos. La fórmula para la relación de recurrencia es (para n ≥ 2):

(n − 1)En = 2nEn+ (n − 2)En-1.

La secuencia va: 1, 0, 1,23, 1,1615,119,142105 ...

Estos números divididos por el número de escaños dan la proporción de asientos sin cubrir, que Nizette calculó como 16.24% para 10 asientos, 13.804% para 100, 13.561% para 1,000 y 13.538% para 6,000. Puedes ver que los números se acercan a o 13.5335...%. Pero, ¿cómo podemos saber que es exactamente hacia donde se dirigen para grandes números para los cuales la relación tardará demasiado en calcularse?1e2

Una relación de recurrencia es buena, pero es como tratar de subir una escalera infinita un paso a la vez. Lo que realmente necesitamos es una expresión de forma cerrada que dependa solo de n. Una expresión de forma cerrada es como un ascensor. Presionas el botón para cualquier n, y whoosh!  el ascensor te lleva hasta allí, incluso a la derecha hasta la parte superior del edificio, donde la vista es infinita.

Obtener una fórmula cerrada a partir de una relación de recurrencia se denomina resolución de la recurrencia. No hay una solución mágica para esto, y aunque hay algunas técnicas que puedes probar, es algo así como un arte. Los programas de matemáticas como Mathematica tienen paquetes para esto. Para nuestro problema, Lazar Ilic produjo una expresión de forma cerrada para En que mostraba que el límite de era correcto.1e2

Así que e entra en el teatro, pero ¿cómo? Todavía no tenemos una idea de cómo llegó allí. ¿Cuál de sus numerosos superpoderes utilizó? A continuación, trato de dar una visión intuitiva de los aspectos más destacados principales mientras dejo de afuera los matorrales de álgebra enredada en el medio.

Primero, deduzvamos dos secuencias de diferencia comenzando con nuestra secuencia E. La secuencia de diferencia de primer orden D consiste en diferencias entre valores consecutivos de E, y la secuencia de diferencia de segundo orden DD consiste en diferencias entre valores consecutivos de D. Así D1 = E1 − E0, D2 = E2 − E1, D3 = E3 − E2, y así sucesivamente, y DD1 = D1 − D0DD2 = D2 − D1DD3 = D3 − D2, y así sucesivamente. (Ambas E0 y D0 son 0). Explicaré el punto de hacer todo esto en breve. Los valores iniciales de las tres secuencias se enumeran en la siguiente tabla.

n Asientos vacíos previstos E Valor 1ª Diferencia Seq. D Valor 2ª Diferencia Seq. DD Valor
0 E0 0 D0 0 DD0 0
1 E1 1 D1 =
E1 – E0
1 DD1 =
D1 – D0
1
2 E2 0 D2 =
E2 – E1
-1 DD2 =
D2 – D1
-2
3 E3 1 D3 =
E3 – E2
1 DD3 =
D3 – D2
2
4 E4 23 D4 =
E4 – E3
-13 DD4 =
D4 – D3
-43
5 E5 1 D5 =
E5 – E4
 13 DD5 =
D5 – D4
23
6 E6 1615 D6 =
E6 – E5
 115 DD6 =
D6 – D5
-415
7 E7 119 D7 =
E7 – E6
745 DD7 =
D7 – D6
445

Haciendo un poco de álgebra entrelazada en la relación de recurrencia original, podemos derivar una expresión de forma cerrada para DDn como sigue (n ≥ 1):

DDn = (2)n1(n1)!

Podemos comprobar que esta fórmula funciona comparándola con la tabla anterior:

DD1 = = 1
DD(2)00!2 = = -2
DD(2)11!3 = = 2
DD(2)22!4 = = - = -
DD(2)33!86435 = = =
DD(2)44!1624236 = = - = -
DD(2)55!321204157 = = = (2)66!64720445

Ahora aquí está el truco: Observe lo que sucede cuando suma todos los DD.

DD1 + DD2 + DD3 + ... + DDn1 + DDn =

D1 − D0 + D2 − D1 + D3 − D2 + ... + Dn1 − Dn2 + Dn − Dn1 = Dn − 0 = Dn.

Todos los demás términos se cancelan, dejando solo Dn. Esta técnica de resolver una recurrencia se llama acertadamente telescopía.

Ahora volvamos a conectar las expresiones de forma cerrada para cada uno de los DD.

Dn = 1 – .21!+222!233!+244!255!+

¿Te resulta familiar? Compare esto con la serie infinita para e-x encima. De hecho, para ngrande , esta es exactamente la fórmula para e-2 o .1e2

Así que el cuadrado de nuestra constante trascendental ha aparecido mágicamente en el denominador de la primera secuencia de diferencia derivada del número de asientos vacíos. Está ahí porque el proceso implica una suma de potencias sucesivas de −2 divididas por el factorial correspondiente, que es exactamente la estructura de las potencias de e.

Todavía tenemos algo de trabajo por hacer para volver de la secuencia D a la secuencia E mediante un proceso similar para obtener En. Este valor, dividido por n,nos dará la fracción de asientos que están vacíos. Para llegar a la línea de meta, necesitamos hacer un poco más de álgebra enredada. Baste decir que e2 permanece en la expresión final, que se ve así:

Enn=1e2+2e2(1n)+

En el límite de ngrande, solo queda el primer término, dando el resultado que ya encontramos: . Tenga en cuenta que para los números grandes pero finitos que Michel Nizette enumeró, solo la suma de los dos primeros términos se ajusta a los valores de la fracción no llena casi exactamente.1/e2

Espero que hayan disfrutado de la fuerte dosis de trascendencia de esta constante tan fascinante y fundamental. El premio Quanta Insights para este mes es para Michel Nizette, por la claridad de la exposición, y Lazar Ilic por el dominio matemático habitual. ¡Enhorabuena a ambos!

(Lazar Ilic, usted es claramente uno de los mejores matemáticos para adornar las secciones de comentarios de nuestros rompecabezas. Como esta es la tercera vez que gana este premio, según mi conteo, y queremos dar una oportunidad a otros también, este es el premio final que le otorgaremos. Por la presente, ha ingresado al Salón de la Fama de Insights. Espero que siga contribuyendo con sus comentarios profundamente perspicaces. Los esperamos con ansias).

Fuente

 

Suscríbete para recibir las últimas noticias y novedades

Por favor, habilite el javascript para enviar este formulario