3
$\begingroup$

We say that a sequence $x_1, x_2,\ldots, x_n$ is increasing if $x_i ≤ x_{i+1}$ for all $1 ≤ i < n$. How many ways are there to fill an 8 x 8 table with numbers 1, 2, 3, and 4 such that:

• The numbers in each row are increasing from left to right

• The numbers in each column are increasing from top to bottom,

• and there is no pair of adjacent cells such that one is filled with 2 and the other one is filled with 3 (We say two distinct cells are adjacent if they share a side)

(I think you can build a system where you transform the problem into two seperate grids, such that they only contain 1s and 2s, but still follow the restrictions.

Then we compare the two grid numbers: 1 and 1 = 1, 1 and 2 = 2, 2 and 1 = 3 and 2 and 2 = 4, where the first number is taken from the first grid and the second from the second. Notice that here 2 and 3 can't be adjacent because that would mean that in one of the grids a 2 is followed by a 1.

Lastly, someone said the answer was $\binom{16}{8}^2$ while another person said $\binom{20}{10}^2$, both without reasoning.)

$\endgroup$
2

1 Answer 1

Reset to default
4
$\begingroup$

The answer is indeed ${16 \choose 8}^2$. The problem is equivalent to constructing two up-right paths (a red path and a blue path) from the bottom left corner to the top right corner of the $8 \times 8$ grid. The correspondence is as follows:

  • $1$ = Above the red path and blue path
  • $2$ = Above the red path but not the blue path
  • $3$ = Above the blue path but not the red path
  • $4$ = Above neither path

Since there are ${16 \choose 8}$ choices for each of the paths (can you see why?), this gives the required answer. The following example should make it clear.

enter image description here

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.