# 999 coins in 3-by-3 piles

999 coins are organized in a 9 piles in a $3\times 3$ grid. There number of coins in each column is the same (333).

We are allowed to take the 3 piles in a single row, but only if we manage to arrange the 6 remaining piles in two rows (without splitting the piles), such that each row contains at least 333 coins.

Is this always possible?

Some simple cases:

** CASE A **
22  22  22
111 111 111
200 200 200


: Here we can just take the top row. The two remaining rows already contain at least 333 coins each.

** CASE B **
100 100 100
100 100 100
133 133 133


: Here we can take the top row and arrange the remaining piles as follows:

100 100 133
100 133 133


:

** CASE C **
11 100 211
22 200 100
300  33  22


: Here we can take the top row and arrange the remaining piles as follows:

33 200 100
300 22  22


I tried many cases and it seems to be always possible, but I could not come up with a proof. Is this always possible?

-
Is your question whether there is a (at least one) row we can take? Because if we take a row with more than $333$ coins, we will never succeed. – Ragnar Jan 4 '14 at 18:57
Yes, we are allowed to pick a row. – Erel Segal-Halevi Jan 4 '14 at 20:07

Mathematica helped me finding a counterexample using

s=a+b+c+d+e+f
FindInstance[{
a + b + c < 333,
d + e + f > 333,
2 (a + b + c) + d + e + f == 999,
2 a + d == 2 b + e == 2 c + f == 333,
k = a + b + d; k < 333 || s - k < 333,
k = a + b + e; k < 333 || s - k < 333,
k = a + b + f; k < 333 || s - k < 333,
k = a + c + d; k < 333 || s - k < 333,
k = a + c + e; k < 333 || s - k < 333,
k = a + c + f; k < 333 || s - k < 333,
k = a + d + e; k < 333 || s - k < 333,
k = a + d + f; k < 333 || s - k < 333,
k = a + e + f; k < 333 || s - k < 333
}, {a, b, c, d, e, f}, Integers]

The resulting square is

116|103|111
116|103|111
101|127|111

You must take one of the first two rows (say, wlg, the first one), because otherwise the total remaining would be less than $666$. Now, the sum of the remaining elements is $669$, so both sums should be at most $336$ and at least $333$. We can subtract $100$ of all elements, so the sum should be at least $33$ and at most $36$.

16|03|11
01|27|11

The row with the $27$ contains two other elements with sum at least $6$ and at most $9$. That is not possible, because the only two elements less than $9$ are $1$ and $3$, and they have sum $4$.

-
Thanks a lot! You not only helped me solved the problem, but also showed me how to solve similar problems in the future. – Erel Segal-Halevi Jan 4 '14 at 20:13
@ErelSegalHalevi You're welcome. I was hoping to find an easy counterexample myself, but when I couldn't find it, I had to use the (ugly, sorry for that) Mathematica code. – Ragnar Jan 4 '14 at 20:17