7
$\begingroup$

You have $3$ boxes $A, B$ and $C$. Boxes $A$ and $B$ are empty to start with and box $C$ has $27$ balls. In "$i$-th" move you make, you must transfer exactly "$i$" balls from one box to another (any transfer to two different boxes are two distinct steps). You CANNOT transfer balls between boxes $A$ and $B$.

Your task is to get to equal number of balls in each box. Can this be done? If yes, how many minimum steps will it take?

Improve this question
$\endgroup$
9
$\begingroup$

A solution is

possible in 7 steps. 

   A B C
   0 0 27
1: 1 0 26
2: 3 0 24
3: 3 3 21
4: 7 3 17
5: 2 3 22
6: 2 9 16
7: 9 9 9

Proof:

Proof of minimality: At the end each box has 9 balls. Clearly the last move is at most 9, so it has to be done in 9 moves or fewer. Every move adds or removes from box C. Since C must be reduced by 18, an even number, the total number of balls transferred must also be even. The total number of balls transferred by $n$ moves is $T_n=\frac{n(n+1)}2$, so this must be even and at least $18$. This leaves only $n=7$ and $n=8$ as possibilities. I don't think there is an $8$ move solution.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes. As the sum of numbers from 1 to 5 is 15 (< 18), it is clear that the boundary is between 6 and 9. As you rightly mentioned, from odd even of sum of transferred numbers, it is also clear that it has to be 7 or 8. I also do not think there is a solution for 8 but even if there was, it is not the minimum. For i = 7, there are 2 solutions. One that you have mentioned where you first get to 7 in a box, then to 2 and then to 9. The other way is to first put 2 in a box and then put 7 in that box later. (0,0,27),(0,1,26),(2,1,24),(2,4,21),(2,8,17),(2,3,22),(2,9,16),(9,9,9). $\endgroup$
    – Math Lover
    Aug 7 '20 at 13:22
  • $\begingroup$ @MathLover: Yes, the second solution simply puts the back-and-forth transfers of +1+4-5 in the other box. $\endgroup$
    – Jaap Scherphuis
    Aug 7 '20 at 13:25
  • 1
    $\begingroup$ I confirm that there is no solution for 8. There are 168 solutions for 7. $\endgroup$
    – RobPratt
    Aug 7 '20 at 14:21
  • $\begingroup$ @RobPratt That can't be right. What are some of those solutions you found? $\endgroup$
    – Jaap Scherphuis
    Aug 7 '20 at 14:45
  • 2
    $\begingroup$ Sorry, I had not properly constrained C=27 initially. There are actually only 6 solutions: (0,0,27),(0,1,26),(2,1,24),(2,4,21),(2,8,17),(2,3,22),(2,9,16),(9,9,9); (0,0,27),(0,1,26),(0,3,24),(3,3,21),(7,3,17),(2,3,22),(2,9,16),(9,9,9); (0,0,27),(0,1,26),(0,3,24),(3,3,21),(3,7,17),(3,2,22),(9,2,16),(9,9,9); (0,0,27),(1,0,26),(3,0,24),(3,3,21),(7,3,17),(2,3,22),(2,9,16),(9,9,9); (0,0,27),(1,0,26),(3,0,24),(3,3,21),(3,7,17),(3,2,22),(9,2,16),(9,9,9); (0,0,27),(1,0,26),(1,2,24),(4,2,21),(8,2,17),(3,2,22),(9,2,16),(9,9,9) $\endgroup$
    – RobPratt
    Aug 7 '20 at 15:07

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.