Problema de cumpleaños sin ayudas electrónicas en un invierno nuclear

Question

El Problema del Cumpleaños es bien conocido, con muchas preguntas y respuestas relacionadas con en este sitio.

La mayoría de las soluciones en algún lugar de hacer uso de una instrucción equivalente a: $\frac{365!}{342!365^{23}} < \frac 1 2$. La exactitud de esta declaración es generalmente demostrado por la afirmación (por el uso de una calculadora, otros medios electrónicos, de registro o tablas) que el lado izquierdo es de aproximadamente 0.492703.

Mi pregunta es: "¿Cuál sería la forma más eficaz de demostrar la verdad de la afirmación anterior usando sólo lápiz y papel?" Supone que todos los equipos y de las tablas de logaritmos han sido destruida en un holocausto nuclear.

Claramente sería posible (aunque dolorosa) para hacer esto después de la división en el largo de la mano: $$\frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365\cdot 365 \cdot 365 \cdot \dots \cdot 365}$$ pero debe haber mejores maneras.

Mi primer pensamiento fue para demostrar algo más sencillo de lo que el resultado sigue. Por ejemplo, se puede demostrar fácilmente con la pluma y el papel que $$\frac{365!}{342!365^{23}} = \prod_{k=0}^{22}\left(1-\frac k {365}\right)<\prod_{k=0}^{22} e^{-\frac k {365}}= \exp\left({-\frac {253}{365}}\right).$$ It would therefore be sufficient to demonstrate that $\exp\left({-\frac {253}{365}}\right) < \frac 1 2$ (which is a true statement since $\exp\left({-\frac {253}{365}}\right) \aprox 0.4999982478$). Equivalently it would be sufficient to show that $\frac{253}{365}>\ln 2$. Pero estos pueden no ser las mejores maneras de proceder, y no he conseguido traer a un satisfactorio de lápiz-y-papel conclusión.

Answer 1

Este no es muy grande pero debería ser posible con la mano.

Desde

$$\ln(x)= \sum_{n=1}^\infty \frac{1}{n}\left(\frac{x-1}{x}\right)^n$$

tenemos

$$\ln(2) = \sum_{n=1}^\infty \frac{1}{n \cdot 2^n} = \sum_{n=1}^{15}\frac{1}{n \cdot 2^n} + \sum_{n=16}^\infty \frac{1}{n \cdot 2^n}$$

Para los quince primeros plazo, usted puede hacer algunos tedioso aritmética para obtener

$$\sum_{n=1}^{15} \frac{1}{n \cdot 2^n} = \frac{31972079}{46126080} = 0.6931453745\overline{906870}$$

Para la cola, se puede aproximar de la siguiente manera:

$$\sum_{n=16}^\infty \frac{1}{n \cdot 2^n} < \frac{1}{16}\sum_{n=16}^\infty \frac{1}{2^n} = \frac{1}{524288} = 0.0000019073486328125$$

Añadir estos juntos obtendrá

$$\ln(2) < 0.6931472819393199031\overline{870906} < 0.6\overline{93150684} = \frac{235}{365}$$

---

Bueno, eso sigue siendo bastante malo, pero ya he escrito, así que bien podría post.

Answer 2

Creo que tengo una mucho mejor/más simple, más directo de enfoque para responder a esta pregunta. No tiene nada que ver con mi anterior $\ln 2$ relacionados con la respuesta (ver en otros lugares en este hilo), así que estoy publicando por separado.

Aquí trato de mostrar directamente $$\frac{365!}{342!365^{23}} <\frac 1 2$$ using only a `difference of two squares' inequality: $a^2\ge a^2-b^2 = (a+b)(a-b)$.

Aquí va: $$\begin{align} \frac{365!}{342!365^{23}} &= \frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365^{23}} \\ &= \frac{(354+11)\cdot (354+10) \cdot \dots \cdot (354-10)\cdot(354-11) } {365^{23}} \\ &= \frac{\left[(354^2-11^2)\cdot (354^2-10^2) \cdot \dots \cdot (354^2-1^2)\right]\cdot(354-0) } {365^{23}} \\ &< \frac{\left[(354^2-0^2)\cdot (354^2-0^2) \cdot \dots \cdot (354^2-0^2)\right]\cdot(354-0) } {365^{23}} \\ &= \left(\frac{354}{365}\right)^{23}. \end{align}$$ A partir de aquí es relativamente fácil demostrar (sólo con lápiz y papel)$\left(\frac{354}{365}\right)^{23}\approx0.495<\frac 1 2$. Por ejemplo, abreviar el valor de $\frac{354}{365}$ por el símbolo $\rho$, podríamos repetidamente la plaza de $\rho$ no más de cuatro veces y, a continuación, evaluar $\rho^{23}$ del producto $\rho^{1+2+4+16}=\rho^1 \rho^2 (\rho^2)^2 (((\rho^2)^2)^2)^2$. Esto requiere un total de siete multiplicaciones (cuatro tomada mientras repetidas veces el cuadrado de $\rho$, y luego otros tres multiplicaciones para combinar los resultados obtenidos en la respuesta final).

Answer 3

[Declaración de interés: esta respuesta es publicado por (mí), el autor de la pregunta original. Por las razones expuestas a continuación, he llegado a la conclusión de que Alexis la respuesta es mejor, aunque, por lo que no será hasta de votar este post, pero publicarlo en caso de que no inspira a nadie.]

Mi línea de investigación relativos a los intentos de demostrar que $\frac {253}{365}>\ln 2$ fue de la siguiente manera: $$\begin{align}\ln 2 &= \ln \left(\frac {4} 3 \cdot \frac 3 2\right)\\ &=\ln\left(1+\frac 1 3\right) + \ln\left(1+\frac 1 2\right) \\ &= -\sum_{k=1}^{\infty} \frac {1} {(-3)^k k} -\sum_{k=1}^{\infty} \frac {1} {(-2)^k k}. \end{align}$$ Desde que la serie anterior han términos de alternancia de signo y magnitud decreciente, sabemos que el error de truncamiento obtenida sumando cada uno para un número finito de términos está limitada por la magnitud de la primera omitido plazo. Cómo muchos términos que necesitamos para calcular el $\ln2$ precisión suficiente para nuestros propósitos? El número que estamos tratando de establecer el signo de es $\frac {253} { 365} - \ln 2\approx 3.5\times 10^{-6}$, por lo que necesitamos una precisión mejor que eso. El $k=10$ término de la primera suma y el $k=16$ término de la segunda suma tienen magnitudes cuyo total es menos de $2.7\times 10^{-6}$. Con el fin de demostrar que el $\frac {253}{365} > \ln 2$ por lo tanto, es suficiente para establecer que la cantidad de $X$, definido a continuación, es positivo: $$X=\frac {253} { 365} +\sum_{k=1}^{9} \frac {1} {(-3)^k k} +\sum_{k=1}^{15} \frac {1} {(-2)^k k}.$$ Tedioso aritmética podría ser utilizado para deducir que $X=\frac{1649344091}{1060426770923520}$ lo cual es positivo. Por desgracia, este podría decirse que/tal vez no es una mejora sobre Alexis de la respuesta en términos de costo: mi respuesta a necesidades del cómputo de un plazo de quince suma que tiene el mismo costo que un cálculo similar como Alexis ... pero mi respuesta también se necesita un nueve término de la suma que se calcula, que su no.

He pensado en usar (10/7)(7/5) en lugar de (4/3)(3/2) para obtener una menor limitación factor de expansión (2/5 en lugar de 1/2) que podría reducir el número de términos que se necesitaba en la lenta convergencia de suma ... pero el costo de tener numeradores que no son de la unidad probablemente sería demasiado alto.

Yo tasa de Alexis respuesta, por tanto, como mejor que esta, en el momento de la publicación.

Sin embargo, me gustaría comentar que la razón de mi respuesta y Alexis son malos, es que tenemos tanto el objetivo de la $\ln 2$ en comparación con $\frac {253}{365}$, que es un cierre de ejecutar la desigualdad (sólo cierto), y por lo tanto necesita mucha precisión y por tanto de costes. Todavía me siento que un acercamiento inteligente que los ataques $\frac{365!}{342!365^{23}} < \frac 1 2$ directamente podría ser mucho más rápido, de mejor manera, puesto que hay muchos más "slop", en el que la desigualdad. Sólo se necesita orden "por ciento" de precisión en lugar de "por millones".

== Nota añadida más tarde ==

Me doy cuenta de que podía mejorar el anterior mediante el uso de $\ln 2 = \ln\left(1+\frac 1 8\right) + 2 \ln\left(1+\frac 1 3\right)$, lo que llevaría a que el análogo de la cantidad de $X$ en mi respuesta está en lugar de $Y$ se define como: $$Y=\frac {253} { 365} +\sum_{k=1}^{5} \frac {1} {(-8)^k k} +2 \sum_{k=1}^{10} \frac {1} {(-3)^k k}=\frac{55119469}{14831143649280}>0$$ ya que este se aproxima a $\frac {253}{365}-\ln 2$ con una precisión limitada por $\frac 1 {6\times 8^6}+2 \frac 1 {11\times 3^{11}}\approx 1.7\times10^{-6}$ que es suficiente para este problema.