Mathematics-Online problems: Solution to the problem of the (previous) week

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	Mathematics-Online problems:
	Solution to the problem of the (previous) week

Problem:

#./interaufg864_en.tex#How many possibilities do exist to arrange the digits

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

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]