Maths Olympiad Prep

Library / /109 of 144

Combinatorics Difficulty 8.6 Shortlist Find the answer

In a 999×999999 \times 999 square table some cells are white and the remaining ones are red. Let TT be the number of triples (C1,C2,C3)(C_1,C_2,C_3) of cells, the first two in the same row and the last two in the same column, with C1,C3C_1,C_3 white and C2C_2 red. Find the maximum value TT can attain.

[i]

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

Solution

Given a 999×999 999 \times 999 square table, our goal is to maximize the number of triples (C1,C2,C3)(C_1, C_2, C_3) such that:
- C1C_1 and C3C_3 are white cells,
- C2C_2 is a red cell,
- C1C_1 and C2C_2 are in the same row,
- C2C_2 and C3C_3 are in the same column.

Let w w represent the number of white cells and r r the number of red cells, where w+r=9992 w + r = 999^2 .

To form a valid triple (C1,C2,C3)(C_1, C_2, C_3), for each red cell C2 C_2 , we can choose C1 C_1 from the remaining white cells in its row and C3 C_3 from the remaining white cells in its column.

### Approach

1. Determine combinations for a fixed red cell:
- For each row, let there be wi w_i white cells and ri r_i red cells. Therefore, the number of ways to choose a pair (C1,C2)(C_1, C_2) in the same row is ri(wi1) r_i \cdot (w_i - 1) .
- Likewise, for each column with wj w_j white cells and rj r_j red cells, the number of ways to choose (C2,C3)(C_2, C_3) is rj(wj1) r_j \cdot (w_j - 1) .

2. **Determining the maximum count T T of triples**:
- Utilize symmetry and combinatorial reasoning under constraints for maximizing white cells—for a balanced distribution, when 13 \frac{1}{3} of the cells are red helps achieving maximal overlap.
- Assume the table is partitioned such that w=23×9992 w = \frac{2}{3} \times 999^2 white cells and r=13×9992 r = \frac{1}{3} \times 999^2 red cells. This ratio balances the need for high overlap without inaccessible segments.

3. Calculating the number of such triples:
- Each red cell (given it belongs to both computations for row and column overlap) can contribute an additional count due to the distributed symmetry:
T(139992)(23999)(23999). T \leq \left( \frac{1}{3} \cdot 999^2 \right) \left(\frac{2}{3} \cdot 999\right)\left(\frac{2}{3} \cdot 999\right).
- This expression represents the best overlapping distribution of white cells while minimizing wasteful triple counts, such as purely white rows or columns.

4. **Evaluating T T **:
- Simplifying this we find:
T=4279994 T = \frac{4}{27} \cdot 999^4

Hence, by balancing the proportions of red and white cells and efficiently placing them within the grid, the maximum value of T T is given by:
4279994 \boxed{\frac{4}{27} \cdot 999^4}

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