Maths Olympiad Prep

Library / /367 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

Let mm be a positive integer. Consider a 4m×4m4 m \times 4 m array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The required minimum is 6 m and is achieved by a diagonal string of m4×4m 4 \times 4 blocks of the form below (bullets mark centres of blue cells):

In particular, this configuration shows that the required minimum does not exceed 6 m.

We now show that any configuration of blue cells satisfying the condition in the statement has cardinality at least 6 m.

Fix such a configuration and let m1rm_{1}^{r} be the number of blue cells in rows containing exactly one such, let m2rm_{2}^{r} be the number of blue cells in rows containing exactly two such, and let m3rm_{3}^{r} be the number of blue cells in rows containing at least three such; the numbers m1c,m2cm_{1}^{c}, m_{2}^{c} and m3cm_{3}^{c} are defined similarly.

Begin by noticing that m3cm1rm_{3}^{c} \geq m_{1}^{r} and, similarly, m3rm1cm_{3}^{r} \geq m_{1}^{c}. Indeed, if a blue cell is alone in its row, respectively column, then there are at least two other blue cells in its column, respectively row, and the claim follows.

Suppose now, if possible, the total number of blue cells is less than 6 m. We will show that m1r>m3rm_{1}^{r}>m_{3}^{r} and m1c>m3cm_{1}^{c}>m_{3}^{c}, and reach a contradiction by the preceding: m1r>m3rm1c>m3cm1rm_{1}^{r}>m_{3}^{r} \geq m_{1}^{c}>m_{3}^{c} \geq m_{1}^{r}.

We prove the first inequality; the other one is dealt with similarly. To this end, notice that there are no empty rows - otherwise, each column would contain at least two blue cells, whence a total of at least 8m>6m8 m>6 m blue cells, which is a contradiction. Next, count rows to get m1r+m2r/2+m3r/34mm_{1}^{r}+m_{2}^{r} / 2+m_{3}^{r} / 3 \geq 4 m,
and count blue cells to get m1r+m2r+m3rm2r/20m_{1}^{r}+m_{2}^{r}+m_{3}^{r}m_{2}^{r} / 2 \geq 0, and the conclusion follows.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.