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.