Maths Olympiad Prep

Library / /327 of 377

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

In how many ways can we enter numbers from the set {1,2,3,4}\{1,2,3,4\} into a 4×44 \times 4 array so that all of the following conditions hold?

(a) Each row contains all four numbers.

(b) Each column contains all four numbers.

(c) Each "quadrant" contains all four numbers. (The quadrants are the four corner 2×22 \times 2 squares.)

Solution

Solution:

Call a filled 4×44 \times 4 array satisfying the given conditions cool. There are 4!4! possibilities for the first row; WLOG, let it be 12341234. Since each quadrant has to contain all four numbers, we have exactly four possibilities for the second row, namely:
(i) 34123412
(ii) 34213421
(iii) 43124312
(iv) 43214321

I claim that the number of cool arrays with (i) is equal to those with (iv), and that the number of cool arrays with (ii) is equal to those with (iii). Let's first consider (i) and (iv). Now, (i) is
1234
3412
while (iv) is
4321
In (iv), switch 33 and 44 (relabeling doesn't affect the coolness of the array); then, it becomes
3421
Now, interchange the last two columns, which also does not affect the coolness. This gives us (i). Hence, the cool arrays with (i) and the cool arrays with (iv) have a 1:11:1 correspondence. Using the exact same argument, we can show that the number of cool arrays with (ii) equals those with (iii).

So we only need consider cases (i) and (ii). It is easy to verify that there are four cool arrays with (i), determined precisely by, say, the first two entries of the third row; and two with (ii), determined precisely by, say the first entry of the third row. Hence, the answer is 4!×(4+2)×2=2884! \times (4+2) \times 2 = 288.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.