Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online problems:

Solution to the problem of the (previous) week


Problem:

#./interaufg864_en.tex#How many possibilities do exist to arrange the digits $ 1, 2, 3, 4$ in a 4x4 grid if

a)
each digit appears 4 times, e.g.


1 1 1 1
2 2 3 3
4 2 2 3
4 4 4 3


b)
in addition, all digits appear in each row, e.g.


1 2 3 4
1 3 4 2
3 2 4 1
3 4 2 1


c)
moreover, no digit appears more than once in each column, e.g.


1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1


Fill in a grid where in addition to the constraints of a) - c) no identical digits are placed along the main diagonals.


Answer:

a)      
b)      
c)      


Solution:

a) Without restriction, the positions of the four ones can be chosen from 16 possibilities, i.e., there are

$\displaystyle \left( \begin{array}{c} 16 \\ 4 \end{array} \right)
= \dfrac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = 1820 \ $   possibilities$\displaystyle .
$

Analogously, there exist

$\displaystyle \left( \begin{array}{c} 12 \\ 4 \end{array} \right) = 495 \ $   possibilities

to place four twos in the remaining 12 positions, and

$\displaystyle \left( \begin{array}{c} 8 \\ 4 \end{array} \right) = 70 \ $   possibilities

to place four threes. Then, the positions of the fours are fixed.
Hence, there is a total of
$ 1820 \cdot 495 \cdot 70 = 63,063,000 $ possibilities.


b) Each row can contain a random permutation of the four digits. This means that in each row there are

4! = 24 possibilities,
totalling to $ 24^4 = 331,776$ possibilities.


c) After permutation of rows and columns of the grid ( $ 4! \cdot 3! = 144$ possibilities), we can presume that the digits in the first row and first column are placed in ascending order:

1 2 3 4
2      
3      
4      


Starting by a placement of the digit 4 in the second row, we obtain the following four possibilities:

1 2 3 4
2 \vbox{\kern3pt\textcircled{{4}}} 1 3
3 1 4 2
4 3 2 1
1 2 3 4
2 3 \vbox{\kern3pt\textcircled{{4}}} 1
3 4 1 2
4 1 2 3
1 2 3 4
2 1 \vbox{\kern3pt\textcircled{{4}}} 3
3 4 1 2
4 3 2 1
1 2 3 4
2 1 \vbox{\kern3pt\textcircled{{4}}} 3
3 4 2 1
4 3 1 2


There is a total of

$ 144 \cdot 4 = 576$ possibilities.


Below, you can see one of the possible arrangements without repetition along the main diagonals.

1 3 4 2
4 2 1 3
2 4 3 1
3 1 2 4


[problem of the week]