Number of ways a board can be found within a game

by saisanjeev   Last Updated August 10, 2018 10:20 AM

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.



Answers 1


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.

joriki
joriki
August 10, 2018 10:03 AM

Related Questions


recurrence solution of placing tiles

Updated March 06, 2016 01:08 AM

Combinatorics | Recurrence relations | Problem

Updated May 09, 2017 17:20 PM

Counting words with letter counts of specific parity

Updated August 24, 2017 21:20 PM

Nonhomogeneous Recurrence Relations

Updated March 26, 2015 07:28 AM