15
$\begingroup$

I'm teaching an intro programming course and came up with a recursion problem for my students to solve that's inspired by the game Chomp. Here's the problem statement:

You have a chocolate bar that’s subdivided into individual squares. You decide to eat the bar according to the following rule: if you choose to eat one of the chocolate squares, you have to also eat every square below and/or to the right of that square.

For example, here’s one of the many ways you could eat a 3 × 5 chocolate bar while obeying the rule. The star at each step indicates the square chosen out of the chocolate bar, and the gray squares indicate which squares must also be eaten in order to comply with the above rule.

enter image description here

The particular choice of the starred square at each step was completely arbitrary, but once a starred square is picked the choice of grayed-out squares is forced. You have to eat the starred square, plus each square that’s to the right of that square, below that square, or both. The above route is only one way to eat the chocolate bar. Here’s another:

enter image description here

As before, there’s no particular pattern to how the starred squares were chosen, but once we know which square is starred the choice of gray squares is forced.

Now, given an $m \times n$ candy bar, determine the number of different ways you can eat the candy bar while obeying the above rule.

When I gave this to my students, I asked them to solve it by writing a recursive function that explores all the different routes by which the chocolate bar could be eaten. But as I was writing this problem, I started wondering - is there a closed-form solution?

I used my own solution to this problem to compute the number of different sequences that exist for different values of $m$ and $n$, and here's what I found:

$$\left(\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 2 & 4 & 8 & 16 & 32\\ 1 & 2 & 10 & 58 & 370 & 2514 & 17850\\ 1 & 4 & 58 & 1232 & 33096 & 1036972 & 36191226\\ 1 & 8 & 370 & 33096 & 4418360 & 768194656 & 161014977260\\ 1 & 16 & 2514 & 1036972 & 768194656 & 840254670736 & 1213757769879808\\ 1 & 32 & 17850 & 36191226 & 161014977260 & 1213757769879808 & 13367266491668337972 \end{matrix}\right)$$

Some of these rows show nice patterns. The second row looks like it's all the powers of two, and that makes sense because if you have a $1 \times n$ chocolate bar then any subsequence of the squares that includes the first square, taken in sorted order, is a way to eat the candy bar. The third row shows up as A086871 on the OEIS, but none of the rows after that appear to be known sequences. The diagonal sequence also isn't on the OEIS,

I believe that this problem is equivalent to a different one:

Consider the partial order defined as the Cartesian product of the less-than relation over the sets $[m] = \{0, 1, 2, ..., m - 1\}$ and $[n]$. How many distinct sequences of elements of this partial order exist so that no term in the sequence is dominated by any previous element and the final element is the maximum element of the order?

I'm completely at a loss for how to determine the answer to that question.

Is there a nice closed-form solution to this problem?

$\endgroup$
  • 2
    $\begingroup$ Not an answer, but a comment: there is no standard order over $\mathbb Z/m\mathbb Z$. Instead, I would pick a set with less structure, i.e., $[n]=\{1,2,\ldots,n\}$, and impose the subset order from the integers. $\endgroup$ – Don Thousand Feb 13 at 2:24
  • 2
    $\begingroup$ If you type "chomp" into oeis, 48 sequences come up. Maybe one of them will lead you to an answer. $\endgroup$ – Gerry Myerson Feb 13 at 3:41
  • 1
    $\begingroup$ Here's the third row from OEIS: oeis.org/A086871 Don't see why this is the case immediately though... Also the fourth row simply does not appear $\endgroup$ – Isaac Browne Feb 13 at 4:58
  • 1
    $\begingroup$ I don't know the answer, but the diagrams strongly remind me of Young tableaux, and there are a lot of combinatorial formulas associated to them, so it might also help to reformulate your problem in that language. $\endgroup$ – pregunton Feb 13 at 9:49
  • 1
    $\begingroup$ @GerryMyerson My apologies - it’s been a crazy week at work and I haven’t had the opportunity to follow up in depth. I did a cursory read over the sequences and while it’s possible that I missed something it looks like most of what’s there relates to the two-player game and counts of winning positions expressed as partitions of numbers. Perhaps there’s some prerequisite I’m missing? $\endgroup$ – templatetypedef yesterday

Your Answer

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

Browse other questions tagged or ask your own question.