How many ways to fill the board $ 4\times 4$ by nonnegative integers, such that sum of the numbers of each row and each column is 3?
Problem
Source: Mongolian TST 2008 day4 problem1
Tags: counting, derangement, pigeonhole principle, combinatorics proposed, combinatorics
11.06.2008 12:05
The answer is 2008
11.06.2008 15:52
Litlle 1000t wrote: The answer is 2008 wow Please post the proof.
12.06.2008 21:15
12.06.2008 23:34
set A={0,0,0 3} set B={0,0,1,2} set C={0,1,1,1} There are some cases for the four rows in some order: AAAA, AABB,ABBB,ABBC, ABCC, ACCC BBBB, BBBC,BBCC,BCCC CCCC AAAA=CCCC total 24 possibilities each
13.06.2008 07:44
I seem to be getting $ 2152$. How do you come up with $ 2008$? Edit: Scratch that, double counted one class of solutions; 2008 seems right. Would love to see a clean proof of it.
13.06.2008 15:30
implex wrote: set 1 {0,0,0 3} then we can arrange it to form 4.3.2.1=24 arrays set 2{0,0,1,2} set 3{ 0,1,1,1} then we can again arrange it 2.3.4=24 ways I think nothing can be done like this. For one row it is known(quite common) that number of nonnegetive integer sum solution is $ \binom{s + n - 1}{n - 1}$ where $ s$ is the sum and $ n$ is number of numbers. I proved it with a nice solution with partitions. But its $ 2d$. And thats the problem. I too would love to see a clean solution.
20.01.2012 17:22
Can anybody solve this?
27.01.2013 06:23
Here are the details; they are not very interesting. If four non-negative integers are to sum to $3$, they are either $\pi(3, 0, 0, 0)$, $\pi(2, 1, 0, 0)$, or $\pi(1, 1, 1, 0)$. Let $a, b, c$ denote the number of rows that are of each of the three forms, respectively. We can now do casework on the value of $a$. (We use the term makeshift row/column; this refers, in an arrangement with at least one $3$, to the entries of a row that are not in the column containing a $3$, or similarly to the entries of a column that are not in the row containing a $3$.) Case 1 : $a = 4$ - then there are clearly $4! = 24$ arrangements. Case 2 : $a = 3$ - clearly any row or column with a $3$ in it cannot have any other entries. Then any additional entries cannot lie in either of the three rows or columns containing one of the three $3$s. This leaves but a single square, which must be filled with a $3$, so $a = 4$ contradiction. Thus no valid arrangements here. Case 3 : $a = 2$ - there are $\binom{4}{2} = 6$ ways to choose the two rows containing the $3$s and $4 \times 3 = 12$ ways to choose the columns. Again, no entries can lie in either of the two rows and two columns containing one of the $3$s. Then we are left to fill a makeshift $2$x$2$ square so that each row and column sums to $3$, but no row or column is $\pi(3, 0)$. The only possibility is $\pi(2, 1)$ which we can permute in $2$ ways. This case then gives $6 \times 12 \times 2 = 144$ arrangements. Case 4 : $a = 1$ - there are first $4$ ways to choose the row to contain the $3$ and $4$ choices for the column it is in. This leaves us to fill a makeshift $3$x$3$ square with rows either $\pi(2, 1, 0)$ (corresponding to $b$) and $(1, 1, 1)$ (corresponding to $c$; all other entries in the row and column containing the $3$ must be $0$). We can now do casework on the value of $b$. Subcase 4.1 : $b = 3$ - we can pick the permutation of the first makeshift row in $3! = 6$ ways. We easily get $2$ possible permutations for the second makeshift row. Finally, the last makeshift row is fixed. In all, this is $12$ sub-arrangements. Subcase 4.2 : $b = 2$ - then $c = 1$. We have $3$ choices for which makeshift row is $(1, 1, 1)$. The next makeshift row can be any of the $3! = 6$ permutations of $(2, 1, 0)$. Finally, the third makeshift row is fixed. Here we have $18$ sub-arrangements. Subcase 4.3 : $b = 1$ - this is impossible; we would need some makeshift column to sum to $2 + 1 + 1 = 4 > 3$. Subcase 4.4 : $b = 0$ - all entries in the sub-square are $1$s, so we have just a single possibility here. In total, this case gives $16 \times (18 + 12 + 1) = 496$. Case 5 : $a = 0$ Subcase 5.1 : $b = 4$ - that is, each row is a permutation of $(2, 1, 0, 0)$. There are $24$ ways to position the $2$ in each row, since no two $2$s can lie in the same column. It only remains to position the ones; this is easily just $D_4 = 9$, the number of derangements of $4$ objects. Thus we have $24 \times 9 = 216$ arrangements here. Subcase 5.2 : $b = 3$ - we have two fundamentally different arrangements here. In one, every $(2, 1, 0, 0)$ row has its $1$ in the same column and the $1$s in the $(1, 1, 1, 0)$ row line up with the $2$s. There are $4$ choices for the $(1, 1, 1, 0)$ row and $4$ choices for how we permute it. The $2$s in the three $b$-rows can be permuted in $6$ ways. This gives $4 \times 4 \times 6 = 96$ arrangements. The other is a little more complicated. Again, we have $4$ choices for the $(1, 1, 1, 0)$ row and $4$ choices for its ordering. This time, there is at least one $2$ in the column containing the $0$ of the $(1, 1, 1, 0)$ row; we have three choices for which row it comes from and $3$ choices for which column to put the $1$ from that row in. We can now choose the position of the other two $2$s in $2$ ways and the positions of the other two $1$s in $2$ ways. This contributes another $4 \times 4 \times 3 \times 3 \times 2 \times 2 = 576$ arrangements. Subcase 5.3 : $b = 2$ - our two $(1, 1, 1, 0)$ rows cannot line up, since otherwise by pigeonhole either we have a column summing to at least $2 + 2 = 4 > 3$ or $1 + 1 + 2 = 4 > 3$. Then they are not ordered the same way, so there are $\binom{4}{2} = 6$ ways to choose their positions and $4 \times 3 = 12$ ways to order them. Here, we can choose the position of the two $2$s in $2$ ways and the position of the two $1$s in $2$ ways, for a total of $6 \times 12 \times 4 = 288$ arrangements here. Subcase 5.4 : $b = 1$ - we have $4$ choices for the $(2, 1, 0, 0)$ row and $12$ ways to permute it. The columns with the $0$s from this row must contain $1$s in the next three columns, so there are $\binom{3}{1} = 3$ ways to finish. Here we get $4 \times 12 \times 3= 144$ arrangements. Subcase 5.5 : $b = 0$ - clearly there are $4! = 24$ arrangements here. Adding these up, we get \[24 + 144 + 496 + 216 + 96 + 576 + 288 + 144 + 24 = \boxed{2008}\]