# A riddle of marbles, buckets, and bottles

My roommate challenged me with the following riddle, claiming he had a solution to the problem. After two weeks of being puzzled, I asked for a hint, and later for his solution. Unfortunately, I was able to point out a flaw in his inductive reasoning, and now neither of us have a solution. Presented is the (mathematically informal) riddle.

There are 15 buckets and 20 bottles. Each of the 15 buckets contains between 1 and 20 marbles (inclusive). Each of the 20 bottles contains between 1 and 15 marbles (inclusive). Prove (or counterexample), that no matter what the distribution of marbles happens to be, you can always select a non-empty subset of buckets and non-empty subset of bottles such that the sum of marbles in both of these subsets is equal.

Feel free to substitute (15,20) with the arbitrary positive integers (A,B). I have proven up to (5,N), but am searching for a more elegant proof in one exists.

• Did you consider induction on A+B ? Gerhard "Sometimes Induction Makes It Easy" Paseman, 2015.06.01 Jun 2 '15 at 0:50
• This is essentially Problem A-4 from the 1993 William Lowell Putnam Mathematical Competition (and a hard Putnam problem at that - only 5 of the top 200 solved it). You can find a solution by Kiran Kedlaya posted here written shortly after he took that test. Jun 2 '15 at 1:19
• Seen before on math.SE math.stackexchange.com/questions/307517 Jun 2 '15 at 1:29