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 pm