Maths Olympiad Prep

Library / /101 of 106

Combinatorics Difficulty 9.0 IMO level Find the answer

Find all integers nn for which each cell of n×nn \times n table can be filled with one of the letters I,MI,M and OO in such a way that:
[LIST]
[*] in each row and each column, one third of the entries are II, one third are MM and one third are OO; and?[/*]
[*]in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are II, one third are MM and one third are OO.[/*]
[/LIST]
[b]Note.[/b] The rows and columns of an n×nn \times n table are each labelled 11 to nn in a natural order. Thus each cell corresponds to a pair of positive integer (i,j)(i,j) with 1i,jn1 \le i,j \le n. For n>1n>1, the table has 4n24n-2 diagonals of two types. A diagonal of first type consists all cells (i,j)(i,j) for which i+ji+j is a constant, and the diagonal of this second type consists all cells (i,j)(i,j) for which iji-j is constant.

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

Solution

To solve the problem, we need to find all integers n n such that an n×n n \times n table can be filled with the letters I,M,O I, M, O while satisfying the given conditions:

1. Each row and each column contains exactly one-third of I I 's, M M 's, and O O 's.
2. For any diagonal whose length is a multiple of three, one-third of its entries must be I I 's, one-third M M 's, and one-third O O 's.

### Analysis

1. Row and Column Condition:
- Each row and column must have each letter exactly one-third of the time.
- Therefore, n n must be divisible by 3, since each character should appear n3\frac{n}{3} times.

2. Diagonal Condition:
- We have two types of diagonals:
- Type 1: All cells (i,j)(i, j) for which i+ji + j is constant.
- Type 2: All cells (i,j)(i, j) for which iji - j is constant.
- For diagonals whose length is a multiple of 3, each letter must appear one-third of the time.

### Solution

To satisfy the diagonal condition for both types, each diagonal must be able to be evenly divided into three parts. The longest diagonals occur when i+j=ni + j = n and ij=1ni - j = 1 - n or vice versa. Each of these diagonals has length nn.

- Therefore, nn must also be divisible by 3 for the diagonal condition.

From both conditions, nn must be divisible by 3.

### Verification

If n=3k n = 3k , where k k is a positive integer:
- Rows and columns can be filled with each of I,M,O I, M, O repeated k k times.
- Both types of diagonals of lengths that are multiples of 3 will have their contents divided equally among I,M,O I, M, O .

Thus, n n should be a multiple of 9, as diagonals require full sections of characteristic grouping.

Conclusion: The requirement is satisfied for n=9k n = 9k with k k being a positive integer.

Therefore, the integers n n for which the condition holds are:

9k for any positive integer k. \boxed{9k} \text{ for any positive integer } k.

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.