Browse · MathNet
PrintTeam selection tests
Vietnam counting and probability
Problem
In a garden, which is organized as a board, we plant three types of flowers: roses, daisies, and orchids. We want to plant flowers such that the following conditions are satisfied:
(i) Each cell is planted with at most one type of flower. Some cells can be left blank and not planted.
(ii) For each planted cell , there exist exactly other planted cells in the same column or row such that those cells are planted with flowers of different types from 's.
(iii) Each flower is planted in at least cell.
What is the maximal number of the cells that can be planted with flowers?
(i) Each cell is planted with at most one type of flower. Some cells can be left blank and not planted.
(ii) For each planted cell , there exist exactly other planted cells in the same column or row such that those cells are planted with flowers of different types from 's.
(iii) Each flower is planted in at least cell.
What is the maximal number of the cells that can be planted with flowers?
Solution
Let be the number of planted cells. The estimation of will be based on the following two simple lemmas.
Lemma 1. If a row (or column) contains at least two types of flowers then it has at most planted cells.
Proof. Suppose to the contrary that a row contains at least planted cells of at least two types of flowers. We choose one type of flowers which is planted in this row with the least (positive) number of cells, WLOG, suppose that it is Roses. Then there are at least other cells which are planted with Daisies or Orchids. This leads to a contradiction, since the cell planted with Roses is in the same row as at least cells planted with Daisies or Orchids. ■
Lemma 2. If a row and a column contains at most one type of flowers then the cell which is the intersection of them is not planted with flower.
Proof. Suppose that the intersection cell of the row and the column is planted with flowers, WLOG, suppose that it is Roses. Then both the row and column are planted with Roses only. This contradicts condition (ii) in the problem. ■
We assume that there are exactly rows and columns which contain at least two types of flowers. We will give a bound for in the following two cases.
Case 1: or . WLOG, suppose that . It is obvious that each remaining rows contains at most planted cells. So by Lemma 1
Case 2: . WLOG, suppose that the first rows and the first columns contain at least two types of flowers. We illustrate the situation as in Fig. 1. By Lemma 1, the first columns (the lime colored part) has at most planted cells. Again, by Lemma 1, the first rows of the remaining columns (the red part) has at most planted cells. By Lemma 2, the remaining cells (the white part) has no planted cell. Therefore we have
So in both cases . It is not hard to see that this maximum value can be attained by planting flowers as in Fig. 2. In the first columns, we plant Roses and Orchids in the last rows. In the first rows, we plant Roses and Orchids in the last columns. So the maximal number of the cells that can be planted with flowers is .
Fig. 1
Fig. 2
Lemma 1. If a row (or column) contains at least two types of flowers then it has at most planted cells.
Proof. Suppose to the contrary that a row contains at least planted cells of at least two types of flowers. We choose one type of flowers which is planted in this row with the least (positive) number of cells, WLOG, suppose that it is Roses. Then there are at least other cells which are planted with Daisies or Orchids. This leads to a contradiction, since the cell planted with Roses is in the same row as at least cells planted with Daisies or Orchids. ■
Lemma 2. If a row and a column contains at most one type of flowers then the cell which is the intersection of them is not planted with flower.
Proof. Suppose that the intersection cell of the row and the column is planted with flowers, WLOG, suppose that it is Roses. Then both the row and column are planted with Roses only. This contradicts condition (ii) in the problem. ■
We assume that there are exactly rows and columns which contain at least two types of flowers. We will give a bound for in the following two cases.
Case 1: or . WLOG, suppose that . It is obvious that each remaining rows contains at most planted cells. So by Lemma 1
Case 2: . WLOG, suppose that the first rows and the first columns contain at least two types of flowers. We illustrate the situation as in Fig. 1. By Lemma 1, the first columns (the lime colored part) has at most planted cells. Again, by Lemma 1, the first rows of the remaining columns (the red part) has at most planted cells. By Lemma 2, the remaining cells (the white part) has no planted cell. Therefore we have
So in both cases . It is not hard to see that this maximum value can be attained by planting flowers as in Fig. 2. In the first columns, we plant Roses and Orchids in the last rows. In the first rows, we plant Roses and Orchids in the last columns. So the maximal number of the cells that can be planted with flowers is .
Fig. 1
Fig. 2
Final answer
24216
Techniques
Coloring schemes, extremal argumentsPigeonhole principle