3
$\begingroup$

$28$ balls are placed in $28$ empty boxes, all in a row. Someone removes all the balls and then places them again either in the same box or to an adjacent of the initial box. In how many different ways can he do this if there is only one ball in each box?

Is it $2*3*3*3*2$? Probably not...

$\endgroup$
  • $\begingroup$ Is multiple occupancy allowed? If it is then for the left and right ball two options, and for every other ball 26 options. $\endgroup$ – Václav Mordvinov Nov 13 '17 at 9:19
  • $\begingroup$ Considering that If we divide them up into pairs of adjacent balls, we get 14 pairs (if we want disjoint). For each pair we have the independent choice of switching places. Thus we have AT LEAST $2^{14}$ choices, but certainly there are more. 2*3*3*3*2 is thus clearly unreasonable, but please explain how you got there... $\endgroup$ – Ove Ahlman Nov 13 '17 at 9:26
  • $\begingroup$ @OveAhlman presumably OP meant $2*3*3...*3*2$ as the number of options for each ball in turn, multiplied together. $\endgroup$ – Especially Lime Nov 13 '17 at 9:29
  • $\begingroup$ No, only 1 ball per box. $\endgroup$ – Alex.vollenga Nov 13 '17 at 9:32
  • $\begingroup$ @EspeciallyLime: yes! Thanks $\endgroup$ – Alex.vollenga Nov 13 '17 at 9:34
2
$\begingroup$

Let $a_n$ be the number of ways we can fill $n$ boxes.

Observe that $a_1 = 1$ since there is only one way to fill one box with the ball that was originally in it.

Also, $a_2 = 2$ since we must either place the balls in their original boxes or switch them.

Suppose $n > 2$.

We can extend any permissible arrangement of length $n - 1$ to one of length $n$ by placing the $n$th ball in the $n$th box. Conversely, given a permissible arrangement of length $n$ in which the $n$th box contains the $n$th ball, we can reduce it to a permissible arrangement of length $n - 1$ by removing the $n$th box. Hence, the number of permissible arrangements in which the $n$th box is filled with the $n$th ball is $a_{n - 1}$.

If the $n$th ball is not placed in the $n$th box, it must be placed in the $(n - 1)$st position, with the $(n - 1)$st ball placed in the $n$th box. Thus, any permissible arrangement in which the $n$th ball is not placed in the $n$th box can be reduced to a permissible arrangement of length $n - 2$ by removing the last two boxes. Conversely, any permissible arrangement of length $n - 2$ can be extended to a permissible arrangement of length $n$ by adding the last two boxes with the $n$th ball placed in the $(n - 1)$st box and the $(n - 1)$st ball placed in the $n$th box. Hence, the number of permissible arrangements in which the $n$th ball is not in the $n$th box is $a_{n - 2}$.

Therefore, we have the recurrence relation \begin{align*} a_1 & = 1\\ a_2 & = 2\\ a_n & = a_{n - 1} + a_{n - 2} \end{align*} Notice that $a_n = F_{n + 1}$, where $F_n$ is the $n$th Fibonacci number, so the number you seek is $F_{29}$.

$\endgroup$
  • $\begingroup$ So it is 317811?? $\endgroup$ – Alex.vollenga Nov 14 '17 at 10:12
  • $\begingroup$ According to my calculations, that is $F_{28}$. I obtain $F_{29} = 514229$. $\endgroup$ – N. F. Taussig Nov 14 '17 at 10:21
  • $\begingroup$ N.F.Taussig Thank you very much! You are brilliant! $\endgroup$ – Alex.vollenga Nov 15 '17 at 8:34
1
$\begingroup$

If you're allowed to have two or more balls in the same box then it is $2\times3\times3\times...\times3\times2=4\times 3^{26}$, as you say: the number of choices for each ball in turn is $2,3,3,...,3,2$ and all choices are independent.

If you're only allowed to have one ball in each box then the choices are not independent. Say there are $u_n$ ways to do this with $n$ boxes. You have to end up with exactly one ball in each box (because there's exactly the same number of balls as boxes). Some ball must go in the leftmost box: either the ball which was originally there stays there, or the first two balls swap. For each of these options, how many ways are there to arrange the remaining balls?

$\endgroup$
  • $\begingroup$ If the choices are not independent, is it 2x2x2...x2 = 2^14? Because, for the leftmost and rightmost balls there are 2 options; therefore for the remaining 26 balls again the same etc, so for each pair we have 2 options. Is this correct? $\endgroup$ – Alex.vollenga Nov 13 '17 at 9:58
  • $\begingroup$ No, it's not as simple as that. For the first ball there are two options, but if you move the first ball there's now only one option for the second (it has to go in the space left by the first). That's why you need to consider the two cases separately, and look for a recurrence relation for $u_n$. $\endgroup$ – Especially Lime Nov 13 '17 at 10:17
  • $\begingroup$ ...and then if we swap 1 and 2, we have 2 options for 3 and 4 and so on, right? $\endgroup$ – Alex.vollenga Nov 13 '17 at 10:26
  • $\begingroup$ Yes, so each time we either reduce the number of remaining boxes by $1$ or $2$... $\endgroup$ – Especially Lime Nov 13 '17 at 10:46
  • $\begingroup$ So: 1-2-... or 2-1- and 3-4-... or 4-3-...etc so why not 2^14? I don't get it :) Sorry for being silly! $\endgroup$ – Alex.vollenga Nov 13 '17 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.