Tiene dos idénticos huevos. De pie en frente de un 100 piso edificio, se pregunta cuál es el número máximo de plantas a partir de la cual el huevo se puede quitar sin que se rompa. ¿Cuál es el mínimo número de intentos necesarios para encontrar la solución?
Respuestas
¿Demasiados anuncios?
Ahora que tienes la respuesta por ti mismo, me permito publicar lo que me estaba pasando, así. (Una lenta la prueba formal de que $14$ es el mínimo, y la respuesta general de los $N$ en lugar de $100$.)
Para ser claros, el supuesto en que el problema es que todas las respuestas son posibles, de $0$ $100$incluido: es posible que el huevo se rompe cuando se deja caer desde el primer piso de la misma, es posible que el óvulo puede sobrevivir a una caída de la $100$th floor, y todo lo demás. (También, el resultado de una caída, es que el huevo se rompe, y no puede ser utilizado, o que no se rompe y el otoño no tiene ningún efecto en absoluto.)
Primero vamos a resolver el problema que tienen sólo un huevo. Entonces debe quedar claro que la única solución es dejar caer desde el primer piso, a continuación, si no se rompe caer desde el segundo piso, y así sucesivamente hasta el $100$ pisos. [Prueba: Supongamos que quitar primero el huevo desde una altura $h_1$, entonces si no se rompe de caída desde una altura $h_2$, y así sucesivamente. A continuación,
- $h_1$ debe $1$. Porque si $h_1 > 1$, y en el que se rompe al caer desde la altura de la $h_1$, entonces usted tiene el huevo no más, y no tenemos ninguna manera de distinguir entre las posibles respuestas $0, \dots, h_1-1$.
- $h_2$ debe $h_1 + 1$, y, en general,$h_{n+1} = h_n + 1$, por una razón similar: si el huevo se rompe cuando se te cae de $h_{n+1} > h_{n} + 1$, entonces usted no tiene ninguna manera de distinguir entre las posibles respuestas $h_{n}, \dots, h_{n+1}-1$. Por lo $h_1, h_2, h_3, \dots$ $1, 2, 3, \dots$ respectivamente. $\Box$]
Así que ahora, con dos huevos, supongamos que usted deje caer desde una altura de $h_1$, entonces si no se rompe de caída desde una altura $h_2$, y así sucesivamente. (Obviamente, para ser óptima, este será un aumento de la secuencia, ya que si el huevo no se rompe cuando se deja caer desde una cierta altura, no es necesario caer desde una pequeña altura, como ya se sabe el resultado.) Para su comodidad, denotan $h_0 = 0$. Si en alguna gota $h_{n+1}$ el huevo se rompe ($n \ge 0$), entonces se quedan con la tarea de distinguir entre las posibles respuestas $h_n, \dots, h_{n+1}-1$ con un solo huevo, que por el razonamiento de la primera parte de arriba, toma (a) $h_{n+1} - h_{n} - 1$ gotas (básicamente colocar el huevo de $h_{n} + 1$, luego de $h_{n} + 2$, y así sucesivamente hasta el $h_{n+1} -1$). Por lo que el número total de gotas necesarias en este escenario es $n+1$ (para las gotas $h_1$$h_{n+1}$), seguido por $h_{n+1} - h_{n} - 1$ gotas, para un total de $ n + 1 + h_{n+1} - h_{n} - 1$, es decir, $n + h_{n+1} - h_{n}$ gotas (donde $n\ge 0$). En el peor de los casos, vamos a incurrir en el coste máximo de esta sobre todas las $n$, y eso es lo que queremos minimizar: queremos minimizar $$\begin{align}\max( &0 + h_1,\\ &1 + h_2 - h_1, \\ &2 + h_3 - h_2, \\ &\dots,\\ &n + h_{n+1} - h_{n})\end{align}$$ donde $n$ ahora es tal que $h_{n+1} = 100$ (si el huevo nunca se rompe, se va a mantener con el primer huevo hasta que cae de las $100$th floor, por lo que podemos wlog asumir que el $h_i$s forman una secuencia finita terminando con $100$). Tenga en cuenta que la suma de todas estas cantidades telescopios, y es $\frac{n(n+1)}{2} + 100$. Así, desde la suma de $n+1$ números es que mucho, el mayor de ellos es, al menos, $\frac{1}{n+1}$th, es decir $$\frac{1}{n+1}\left(\frac{n(n+1)}{2} + 100\right) = \frac{n}{2} + \frac{100}{n+1} \ge 10\sqrt{2} - \frac12 \approx 13.6,$$ so we need at least $14$ las gotas.
Y el método para lograr la $14$ gotas en sí mismo sugiere: hacer el máximo de igualdad cuando la suma es fijo, la forma general es hacer que todos ellos tan iguales como sea posible, lo que sugiere que podemos tomar $h_1 = 14$, $h_2 - h_1 = 13$ (por lo $h_2 = 14 + 13 = 27$),$h_3 = 14 + 13 + 12$, y así sucesivamente hasta el $h_{11} = 14 + 13 + \dots + 4 = 99$, y, a continuación,$h_{12} = 100$.
(Hay muchas otras soluciones, por ejemplo,$h_1 = 7$, luego $h_2 = 7 + 13$, $h_3 = 7 + 13 + 12$ y así sucesivamente hasta el $h_{14} = 7 + (13 + 12 + \dots + 2 + 1) = 100$, pero el hecho sobresaliente es que $13 + 12 + \dots + 2 + 1 = 91 < 100$, mientras que $14 + 13 + \dots + 2 + 1 = 105 > 100$. Si en lugar de $100$ nos daban $105$, la respuesta sería aún se $14$, y que el método será único.)
Por supuesto, no hemos de aquí el uso de cualquier propiedad especial de $100$, y repitiendo el argumento anterior para general $N$ muestra que el número de pasos que necesita es: $$ \left\lceil \sqrt{2N} - \frac{1}{2} \right\rceil$$
Una alternativa más simple manera de decir esto es: $$\text{the smallest number $n$ such that $\frac{n(n+1)}{2} \ge N$.}$$
Ehtesh Choudhury
Puntos
158
He encontrado la solución. Aquí está:
La forma más sencilla de hacerlo sería para comenzar en el primer piso y colocar el huevo. Si no se rompe, pasar a la siguiente planta. Si se rompe, entonces sabemos que el máximo de la planta, el huevo va a sobrevivir es 0. Si continuamos este proceso, vamos a encontrar fácilmente la máxima plantas, el huevo va a sobrevivir con un solo huevo. Por lo que el número máximo de intentos es 100 que es cuando el óvulo sobrevive incluso al 100 piso.
Podemos hacer mejor? Por supuesto que podemos. Vamos a empezar en el segundo piso. Si el huevo se rompe, entonces podemos usar el segundo huevo para volver a la primera planta y vuelve a intentarlo. Si no se rompe, entonces podemos seguir adelante y tratar en el 4to piso (en múltiplos de 2). Si alguna vez se rompe, dicen en el suelo, x, entonces sabemos que sobrevivió piso x-2. Eso nos deja con solo piso x-1 a probar con el segundo huevo. Entonces, ¿cuál es el número máximo de intentos posible? Se produce cuando el óvulo sobrevive 98 o 99 plantas. Tomará 50 intenta alcanzar el piso de 100 y uno de los más huevo para tratar sobre el 99 piso, por lo que el total es de 51 intenta. Wow, que es casi la mitad de lo que había pasado el tiempo.
Podemos hacerlo aún mejor? Sí, se puede. Lo que si tratamos a intervalos de 3? Aplicando la misma lógica, como el caso anterior, tenemos un máximo de 35 intenta averiguar la información (33 intenta llegar a 99 piso y 2 más en 97º y 98º piso).
Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 – 20
15 – 20
16 – 21
Para escoger cualquiera de los intervalos con 19 número máximo de intentos estaría bien.
En lugar de tomar intervalos iguales, podemos aumentar el número de plantas por uno menos que el anterior incremento. Por ejemplo, vamos a probar primero en el piso 14. Si se rompe, entonces tenemos 13 intentos más para encontrar la solución. Si no se rompe, entonces debemos tratar de piso 27 (14 + 13). Si se rompe, tenemos 12 intentos más para encontrar la solución. Así, la inicial de 2 intentos más el adicional de 12 intenta todavía sería intenta 14 en total. Si no se rompe, podemos intentar 39 (27 + 12) y así sucesivamente. Mediante 14 como el primer piso, se puede llegar hasta el piso 105 (14 + 13 + 12 + ... + 1) antes de que necesitamos más de 14 intentos. Ya que sólo necesita para cubrir el 100 pisos, 14 intenta es suficiente para encontrar la solución.
Por lo tanto, el 14 es el menor número de intentos para encontrar la solución.
CodingBytes
Puntos
102
La crítica de la tira de los huevos es el intervalo de $C:=[k,k+1]$ de manera tal que, cuando un huevo que se deja caer desde una altura de $\leq k$ sobrevive, y cuando se deja caer desde una altura de $\geq k+1$ frenos.
Los números $$h_r(n)\qquad(r\geq0,\ n\geq0)$$ ("longitud permitida para $r$ de los huevos y $n$ "pruebas") se definen como sigue: Si sabemos que $C$ se encuentra en un cierto intervalo de longitud de $\ell\leq h_r(n)$ podemos localizar $C$ $r$ de los huevos en $n$ ensayos, pero si sabemos sólo que $C$ se encuentra en un cierto intervalo de longitud de $\ell>h_r(n)$ entonces no hay ningún algoritmo determinista que permite localizar $C$ $r$ de los huevos en $n$ ensayos seguro. Obviamente $$h_0(n)=1\quad(n\geq0)\ ,\qquad h_r(0)=1\quad(r\geq0)\ .$$ Los números de $h_r(n)$ satisfacer la recursividad $$h_r(n)=h_{r-1}(n-1)+h_r(n-1)\qquad(r\geq1,\ n\geq1)\ .\qquad(*)$$ Prueba. Suponga $C$ se encuentra en un cierto intervalo de $I$ de la longitud de la $\ell:=h_{r-1}(n-1)+h_r(n-1)$. Podemos muy bien suponer que el extremo inferior de $I$ está en el nivel cero. Colocar el primer huevo en la altura de la $h_{r-1}(n-1)$. Si los frenos, a continuación, $C$ está contenida en el intervalo de $[0,h_{r-1}(n-1)]$, y puede ser localizado con el resto de las $r-1$ de los huevos en $n-1$ ensayos. Si sobrevive, a continuación, $C$ está contenida en el intervalo de $[h_{r-1}(n-1),\ell]$ de la longitud de la $h_r(n-1)$, y puede ser localizado con la $r$ de los huevos en $n-1$ ensayos. Esto demuestra $h_r(n)\geq\ell$.
Por el contrario, asumir que sólo sabemos que $C$ se encuentra en un cierto intervalo de longitud de $\ell'>\ell$ y que existe un algoritmo que localiza $C$ $r$ de los huevos en $n$ ensayos. Este algoritmo nos diría la altura de la $k$ a la que debemos colocar el primer huevo. Si $k>h_{r-1}(n-1)$ y el huevo frenos o si $k\leq h_{r-1}(n-1)$ y el óvulo sobrevive sería imposible terminar la tarea, como el resto de intervalo que contiene a $C$ es mayor que el permitido para el resto de los recursos. De ello se desprende que $h_r(n)\leq\ell$.
De $(*)$ obtenemos $$h_1(n)=n+1\ ,\quad h_2(n)={1\over2}(n^2+n+2),\quad h_3(n)={1\over6}(n^3+5n+6)\qquad(n\geq0)\ .$$ Como $h_2(13)<100<h_2(14)$ necesitamos al menos $14$ ensayos para localizar $C$ (o eliminar las $C\subset[0,100]$) en el programa de instalación original.
