All the Winning Bites for a by b Chomp for a and b up to 14 and Two Computational Challenges By Shalosh B. Ekhad and Doron Zeilberger Posted: Aug. 11, 2018: Dedicated to Richard K. Guy (b. Sept. 30, 1916) in honor of his forthcoming 102th birthday Recall that the game of CHOMP starts out with an a by b chocolate bar where the top-left corner is poisoned and if you eat it you would die. Two players take turn picking any remaining square, and have to eat it along with all remaining squares that lie to its right and under it. You win if you don't die (and the other player dies, since it is forced to eat the poisoned square). David Gale (using John Nash's strategy stealing argument he used for Hex) famously proved that the first player HAS (at least one) winning move. Here is the argument. Consider the minimal move 1x1 (i.e. biting the bottom-right square, only removing this one square). By the Law of Excluded Middle, there are only TWO possibilities (it is obvious that in this game there are never ties). Case I: It is a Winning Move. Then of course, there Exists a Winning Move. Case II: It is a Losing Move. This mean that the second player has a WINNING COUNTER-MOVE. But it is obvious that any legal move from the current position is also a Winning Move from the initial position. So the first player can "steal" this move, and do it. Hence there Exists a Winning Move in this case. Since this is a finite game, there are no theological objections to this EXISTENCE proof using the notorious Law of Excluded Middle (e.g. that there exists irrational numbers a and b such that a^b is rational: consider sqrt(2)^(sqrt(2)): it is either rational (take a=sqrt(2), b=sqrt(2)) or irrational in which case take a=sqrt(2)^sqrt(2), b=sqrt(2) This "proof" is not even wrong it is gibberish). Going back to Chomp, what IS (or are) the winning move(s). One of us (DZ) is pledging a $500 donation to the OEIS in honor of the first person to solve First Computational Challenge: Find all the winning moves for a 1001 by 1003 chocolate bar. The classic book Winning Ways, vol. 2, by E. R. Berlekamp, J. H. Conway, and R. K. Guy (Academic Press, 1982), Chapter 16, bottom of Fig. 12 lists all the winning moves for small a and b <=6, and for a<=4 b<=16. Here we extend this table to ALL 1<=a,b<=14. [ [0 , {1x1} , {1x2} , {1x3} , {1x4} , {1x5} , {1x6} , {1x7} , {1x8} , {1x9} , {1x10} , {1x11} , {1x12} , {1x13}] [{1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1} , {1x1}] [{2x1} , {1x1} , {2x2} , {2x2} , {1x2} , {2x3} , {1x3} , {2x4} , {1x3} , {2x5} , {2x5} , {1x4} , {2x6} , {1x4}] [{3x1} , {1x1} , {2x2} , {3x3} , {2x3} , {3x4} , {2x4} , {3x5} , {1x2} , {2x5} , {3x7} , {3x7} , {2x7} , {2x7}] [{4x1} , {1x1} , {2x1} , {3x2} , {4x4} , {3x3} , {4x5} , {1x2} , {3x4} , {4x7} , {1x2} , {1x2} , {2x4} , {4x10}] [{5x1} , {1x1} , {3x2} , {4x3} , {3x3} , {5x5} , {2x3} , {4x5} , {5x7} , {4x6} , {1x1} , {5x9} , {2x5, 3x2} , {4x9}] [{6x1} , {1x1} , {3x1} , {4x2} , {5x4} , {3x2} , {6x6} , {5x6} , {5x6} , {6x8} , {3x5} , {5x7} , {2x3} , {2x11}] [{7x1} , {1x1} , {4x2} , {5x3} , {2x1} , {5x4} , {6x5} , {7x7} , {3x3} , {4x5, 5x2} , {5x6} , {7x10} , {2x8} , {2x4}] [{8x1} , {1x1} , {3x1} , {2x1} , {4x3} , {7x5} , {6x5} , {3x3} , {8x8} , {1x6, 3x3} , {5x8} , {3x4} , {8x11} , {6x10}] [{9x1} , {1x1} , {5x2} , {5x2} , {7x4} , {6x4} , {8x6} , {2x5, 5x4} , {3x3, 6x1} , {9x9} , {8x9} , {9x8} , {8x10} , {4x6, 6x2}] [{10x1} , {1x1} , {5x2} , {7x3} , {2x1} , {1x1} , {5x3} , {6x5} , {8x5} , {9x8} , {10x10} , {3x4} , {7x8} , {3x7}] [{11x1} , {1x1} , {4x1} , {7x3} , {2x1} , {9x5} , {7x5} , {10x7} , {4x3} , {8x9} , {4x3} , {11x11} , {2x5, 3x3} , {8x9}] [{12x1} , {1x1} , {6x2} , {7x2} , {4x2} , {2x3, 5x2} , {3x2} , {8x2} , {11x8} , {10x8} , {8x7} , {3x3, 5x2} , {12x12} , {11x12}] [{13x1} , {1x1} , {4x1} , {7x2} , {10x4} , {9x4} , {11x2} , {4x2} , {10x6} , {2x6, 6x4} , {7x3} , {9x8} , {12x11} , {13x13}]] : It is also mentioned in Winning Ways that Ken Thompson (of Unix fame) discovered that the smallest size for which there are TWO winning moves is an 8 by 10 chocolate bar. From the above table we found a few other cases, e.g. 6 by 13 bar, 10 by 14 bar, but none so far, with THREE winning moves. This brings us to the next computational challenge for which D.Z. is pledging a $100 donation to the OEIS in honor of the finder. Second Computational Challenge: Find a and b such that an a by b Chomp has (at least) THREE winning moves.