Question

You are given two identical balls made of a tough alloy. The hardness test fails if a ball dropped from a floor of a 120-storey building is dented upon impact. A ball can be reused in fresh drops only if it has not been dented in a previous drop. Using only these two identical balls, what is the smallest number of ball drops that will determine the highest floor from which the ball can be dropped without being damaged?

Answer 1

Answer:

15

Step-by-step explanation:

first iteration

drop from 15th floor

if dented

use another ball from 1 to 14

total 15 drops

second iteration

if not dented from 15th floor

drop from 29 if dented

again use another ball from 16 to 28 floor

total 15 drops

next iteration s

from 42 th , 54 , 65 , 75 , 84 , 92 , 99 , 105 , 110 , 114 , 117 , 119, 120

in this way always 15 drops are sufficient

Answer 2

Answer:

Minmax problem.

Step-by-step explanation:

Let's consider a $k$-partition ($k\in\mathbb{N}$ obviously) of the building. That is, $n_1+n_2+\dots+n_k=120$. Each $n_i$ corresponds to the $f_i=\displaystle\sum_{j=1}^in_j$ floor. We start dropping one ball from $n_1$ (floor $f_1$).

Two options here:

1. It breaks. Then you need to use the other ball to check from the floor $1$ to the floor  $f_1-1$. Considering the worst scenario, you have dropped a ball $n_1$ times.
2. The ball survives. You go up and then drop the ball from $n_2$ (floor $f_2$). Two options here again: (a) It breaks. Using the other ball you need to check from the floor   $f_1+1$ to the floor  $f_2-1$ under the worst scenario. These are $n_2$ droppings. Plus the previous drop at $n_1$ you have dropped a ball $n_2+1$ times. (b) The ball survives. You go up and then drop the ball from $n_3$ (floor $f_3$). Two options here again: (i) It breaks. Using the other ball you need to check from the floor $f_2+1$ to the floor $f_3-1$ under the worst scenario. These are $n_3$ droppings. Plus the two previous drops at $n_1$ and $n_2$ you have dropped a ball $n_3+2$ times. (ii) The ball survives. You go up and then drop the ball from $n_4$ (floor $f_4$). And so on...

In this way, the worst case is                                        

                                    $\displaystyle\max_{r\in\{1,2,\dots,k\}}\{n_r+(r-1)\}$.

So, what we need is

                         $L(k)=\displaystyle\min_{n_1+n_2+\dots+n_k=120}\displaystyle\max_{r\in\{1,2,\dots,k\}}\{n_r+(r-1)\}$.

Considering that

             $\displaystyle\min_{x_1+x_2+\dots+x_k=c}\max\{x_1,x_2,\dots,x_k\}=\max\left\{\dfrac{c}{k},\dfrac{c}{k}\dots,\dfrac{c}{k}\right\}=\dfrac{c}{k}$

we proceed as follows

$L(k)=\displaystyle\min_{\sum_{s=1}^kn_s+(s-1)=120+\frac{k(k-1)}{2} }\displaystyle\max_{r\in\{1,2,\dots,k\}}\{n_r+(r-1)\}$

       $=\frac{120+\frac{k(k-1)}{2}}{k}$

       $=\frac{120}{k} +\frac{k-1}{2}$.

Now, what natural number divides $120$ and is odd? Well, $120=2^3\times5\times 3$. The options are $3,5,$ and $15$. We have that

                        $L(3)=41,\quad L(5)=26, \quad L(15)=15.$

Clearly $k=15$ is the best choice.  This gives us

$n_s+(s-1)=15, \forall s\in\{1,2,\dots,k\}$.  So

$n_1=15,$

$n_2=14,$

$n_3=13,$

     $\vdots$

$n_{15}=1.$