Fudge Likes Meatballs
Here is an interesting puzzle by Ivan Mitrofanov.
Puzzle. In front of my dog, Fudge, lies an infinite number of meatballs with a fly sitting on each of them. At each move, Fudge makes two consecutive operations described below.
- Eats a meatball and all the flies sitting on it at that time.
- Transfers one fly from one meatball to another (there can be as many flies as you want on a meatball).
Fudge wants to eat no more than a million flies. Assuming that flies sit still, prove that Fudge doesn’t have a strategy where each meatball is eaten at some point.
Share:
Lazar Ilic:
Perhaps my noodle noddle noodling noodles are up to no good… proof by contradiction. Suppose there existed such a strategy and the meatballs are numbered 1, 2, … without loss of generality we may permute the labels so that Fudge eats them in order. Then the following theorem becomes clear: if some prefix of length L of the remaining meatballs has >= L flies in total on the meatballs prefix then Fudge will eat >= 1 fly during their consumption of that prefix. Indeed, Fudge has L eat operations with only L-1 move operations between them on the prefix. OK. Intuition here is that a stronger strategy in the finite case would be to eat 1 then move from 2 to rear then eat 2 then move from 3 to rear then … then lose on the last move of eating from rear. Proof in the infinite case follows. Each phase we will ensure Fudge eats >= 1 more fly by tracking the maximal index we have shifted a fly to thus far. Phase 1 ends when we eat the fly on meatball 1. Now if Fudge moves the fly from meatball 2 to meatball M the new “prefix” from 2 to M works as it contains precisely M-1 flies. Once Fudge eats meatball 2 through the meatball M there is a new analysis. If fudge ate F >= 1 flies during phase 2 and moved M-1-F >= 0 with the maximal meatball MM being moved to then there exist MM-F-1 flies on the meatballs M+1 through MM is a new new prefix of length MM-M <= MM-F-1 flies on it and thus the theorem applies again and can be written up in to a formal strong induction proof that after 1000000 such phases the process will terminate.
I ought to have cited Sperner's Theorem in my previous comment on identifying a murderer with the "convenient" [8 choose 4] = 70 sized antichain bound.
15 March 2024, 7:14 pmDillan Agrawal:
I believe if there are an infinite number of meatballs with a fly sitting on each, there are an infinite number of flies on the meatballs. If the flies don’t move and can only be transferred to other meatballs, by eating all the meatballs, Fudge would have to eat all of the infinite number of flies, thus contradicting him eating no more than a million flies.
13 May 2024, 7:15 pmJBL:
Dillan, that solution is wrong. Aside from the Zeno-like confusion (“every meatball gets eaten at some point” is not the same as “eating all the meatballs”), it would apply equally well to the situation where the dog can move a finite number of flies (not just 1) at each step. But in this case the dog can do the required task: at step 1 he eats meatball 1 (along with its fly) and moves fly 2 to meatball 3. At step 2 he eats meatball 2 (with no flies) and moves flies 2 and 3 to meatball 4. At step 3 he eats meatball 3 (with no flies) and moves flies 2, 3, 4 to meatball 5. Etc. In this process each meatball eventually gets eaten, and no fly gets eaten aside from fly 1.
7 June 2024, 1:43 pm