We have an integer n. We have n boxes where each box contains a non-negative amount of balls. Find all the permutations which satisfy some criteria

Question

Let $n$ be a positive integer. We have $n$ boxes where each box contains a non-negative number of pebbles. In each move we are allowed to take two pebbles from a box we choose, throwaway one of the pebbles and put the other pebble in another box we choose. An initial configuration of pebbles is called solvable if it is possible to reach a configuration with no empty box, in a finite(possibly zero) number of moves. Determine all initial configurations of pebbles which are not solvable, but become solvable when an additional pebble is added to a box, no matter which box is chosen.
I state that for a permutation $(m_1, m_2, dots, m_n)$, $S=leftlceil{frac{m_1}{2}}rightrceil+dots+leftlceil{frac{m_n}{2}}rightrceil$
After a lot of trial and error I have worked out that it is not solvable if and only if $Sle n-1$ however I can't prove it. This obviously leads to the solution of the question, if it were proved. Could you please explain to me how to solve the question, using my method or any other method you find best suited?

Mike Earnest · Answer

You can prove that the quantity $lceil m_1/2rceil + dots + lceil m_n/2rceil$ does not increase as you make valid moves (prove this). Furthermore, once all the boxes are nonempty, the quantity is at least $n$. Therefore, is a configuration is solvable, the value of the quantity must initially be at least $n$. Conversely, if the quantity is at least $n$, then a simple greedy algorithm works to fill all the boxes: simply always take balls from a box with at least $3$ balls, and put the result into an empty box.

Answered by Mike Earnest on January 25, 2021

We have an integer n. We have n boxes where each box contains a non-negative amount of balls. Find all the permutations which satisfy some criteria

One Answer

Add your own answers!

Ask a Question