4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Did you consider induction on A+B ? Gerhard "Sometimes Induction Makes It Easy" Paseman, 2015.06.01 $\endgroup$ Jun 2 '15 at 0:50
  • 6
    $\begingroup$ 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. $\endgroup$ Jun 2 '15 at 1:19
  • 3
    $\begingroup$ Seen before on math.SE math.stackexchange.com/questions/307517 $\endgroup$ Jun 2 '15 at 1:29
5
$\begingroup$

While I won't repeat the proof here, this question has been answered sufficiently. It was 1993 Putnam problem A-4, answered by 5 of the top 207 participants. I no longer feel bad about having spent more than 6 hours and a 30-minute lunch break working on this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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