Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 18:57
    
Yes, we are allowed to pick a row. –  Erel Segal Halevi Jan 4 at 20:07
add comment

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
    
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 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 at 20:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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