In a game of Chomp, two players alternately take bites from a 5-by-7 grid of unit squares. To take a bite, a player chooses one of the remaining squares, then removes ("eats") all squares in the quadrant defined by the left edge (extended upward) and the lower edge (extended rightward) of the chosen square. For example, the bite determined by the shaded square in the diagram would remove the shaded square and the four squares marked by $\times.$ (The squares with two or more dotted edges have been removed form the original board in previous moves.)

The object of the game is to make one's opponent take the last bite. The diagram shows one of the many subsets of the set of 35 unit squares that can occur during the game of Chomp. How many different subsets are there in all including the empty and the filled up one?

one of the arrangements that can be found

I analysed the first few squares on the corner and started counting them but my analysis started becoming too extensive once I started reaching the middle of the board? Can anyone please help me with finding a nice proof for this. I feel recurrence relations would help but am not able to develop a nice one for this.

up vote 3 down vote accepted

Since each admissible position is uniquely described by the lengths of the five rows, the admissible positions are in bijection with the weakly increasing $5$-tuples of integers in $[0,7]$. These can be counted by counting the ways to insert $7$ increases anywhere before, between or after the $5$ rows. Thus there are $\binom{7+5}7=792$ different admissible positions. Note that the answer has the required symmetry in that we could interchange rows and columns in the derivation and get the same result.

  • 1
    +1 This solution can also be visualised by means of the popular "stars and bars". – Servaes Aug 10 at 10:07
  • Pardon my ignorance, but what do you mean by "weakly increasing"? – saisanjeev Aug 12 at 5:24
  • @saisanjeev: Weakly increasing, as opposed to strictly increasing, means that equality is allowed. A weakly increasing sequence has $a_{n+1}\ge a_n$; a strictly increasing sequence has $a_{n+1}\gt a_n$. Another way to put it would be that "weakly increasing" means "not decreasing". The row lengths can stay the same or increase, but they can't decrease as you go from top to bottom. – joriki Aug 12 at 5:28
  • So you are basically tracing a path from the top left to bottom right? – saisanjeev Aug 12 at 6:37
  • @saisanjeev: Yes, that's a good way of putting it. MathWorld calls it a staircase walk. – joriki Aug 12 at 6:39

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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