Maths Olympiad Prep

Library / /445 of 462

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Ireland

A Colombian Square is a 6×66 \times 6 square which is subdivided into 3636 unit squares, each of which is coloured either Yellow, Blue or Red according to the following rules:

a. No row or column may contain more than two unit squares of the same colour.

b. In any set of four unit squares obtained by intersecting two rows with two columns, no colour is to occur exactly three times.

How many different Colombian Squares are there?

Solutions — 2

Solution 1

Condition (a) requires that each of RR, YY, BB is to occur exactly twice in each row and column.

We apply (b) as follows: Take any unit square of a given colour, say RR. As explained above, its row and column must each contain another RR. The three RR's are the vertices of a rectangle and the fourth vertex must also be RR by condition (b).

If (a) and (b) hold for a given matrix, then they will also hold after any permutation of the rows and columns of the matrix.

Let NN denote the number of Colombian Squares for which the 1st row and column in the table are both coloured in the pattern RYBRYBRYBRYB. There are (62)(42)(22)=90\binom{6}{2} \binom{4}{2} \binom{2}{2} = 90 ways to colour the first row, and for each of these choices there are (52)(32)=30\binom{5}{2} \binom{3}{2} = 30 ways to colour the remainder of the first column, so the total number of matrices will be 9030N=2700N90 \cdot 30 \cdot N = 2700N.

To find NN, we examine those Colombian Squares which partially look like
Figure 1

When we attempt to fill in the 4th row and column with YY, BB, with the help of (b) we quickly dismiss all but the following four patterns:

(i)
Figure 2

(ii)
Figure 3

(iii)
Figure 4

(iv)
Figure 5

Note that (iv) is obtained from (iii) by swapping rows with columns.

In each of the cases above, once we fill in the first empty 2×22 \times 2 table, the other entries are determined by (a) and (b), applied to the YY's and BB's.

In case (i), in columns 2 and 5 the B can only be in rows 2 and 5, because of (a). Similarly, the Y in columns 3 and 6 can only be in rows 3 and 6. The unfilled unit squares are then to be filled with R, using (a) again. Therefore, the only possibility in this case is this:

(i)
Figure 6

In case (ii), by using (b), we see that the distribution of Ys and Bs surrounding the top left empty 2×22 \times 2 cell forces all its four entries to be R. In turn, this implies that all the entries in the top right empty 2×22 \times 2 cell are Y or B. But, because of condition (a), this is impossible as there are already a Y and a B entry in these columns. Therefore, case (ii) is impossible.

In case (iii), proceeding as before, we are left with four possible Colombian Squares:

(iii)
Figure 7
Figure 8
Figure 9
Figure 10

In case (iv) the four possibilities are obtained from those in case (iii) by swapping rows with columns. Hence, we get N=1+4+4=9N = 1 + 4 + 4 = 9 possibilities.

Therefore, there are 9×2700=243009 \times 2700 = 24300 Colombian Squares.

Solution 2

Instead of fixing a row and a column, we first focus on one colour. Let us see in how many ways we can arrange the yellow squares in the table such that there are exactly two yellow squares in each row/column (this is condition a). By condition (b), the 12 yellow squares in the table form the vertices of 3 different rectangles.

There are (62)=15\binom{6}{2} = 15 ways to choose two yellow squares in column 1. There are 5 ways to choose another column, so that the yellow squares in the 1st column and the newly chosen column form the vertices of a rectangle. There are thus 75 ways to choose the first rectangle with yellow vertices.

For the second rectangle, we choose the next available column (either the 2nd or if taken, the 3rd). There are (42)=6\binom{4}{2} = 6 ways to choose yellow squares in it, so that they are not in the same rows as the yellow unit squares of the first rectangle. Then, there are 3 ways to choose a new column and thus complete the second rectangle with yellow vertices. This gives 18 possibilities for the 2nd rectangle. The third rectangle will then be uniquely determined by condition (a). Thus in total, there are 75×18=135075 \times 18 = 1350 ways of arranging the yellow squares.

Let us first determine how we can fill in the remaining squares in the first column, and then, for each case, how many Colombian tables we get.

The first 2 squares in the 3rd row could be RR, BB, RB or BR. This gives four cases to consider.

(i)
Figure 11

(ii)
Figure 12

(iii)
Figure 13

(iv)
Figure 14

In the first case, there are 3 options for completing this RR to a rectangle, and then all the colours in the table are determined by condition (a). Similarly in case (ii), we have 3 options for filling in the other BB in the first two columns, then everything else is determined.

In case (iii) columns 1 and 2 cannot be RR or BB in any row, because of condition (b). Therefore, and because of condition (a), there is another row starting with RB and there are 3 possibilities to choose it. For each such choice, there are two ways to complete the two rows starting with RBRB. Indeed, the two free squares left in these rows can be filled in with RBRB, or alternatively with BRBR. The colours of other squares in the table are then completely determined by condition (a). This leads to 6 ways of completing the table to a Colombian square in case (iii). Exchanging RR and BB switches from case (iii) to case (iv), hence there are 6 Colombian squares in case (iv) as well.

In total, cases (i)–(iv) yield 3+3+6+6=183+3+6+6 = 18 possibilities. Hence, the number of Colombian squares is equal to 1350×18=24,3001350 \times 18 = 24,300.

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.