Maths Olympiad Prep

Track / Stage 7 / 42 of 300 #1442 of 1964

Problem 1442

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.1 Find the answer

Let m>1 m > 1 be an integer, n n is an odd number satisfying 3n<2m, 3\le n < 2m, number ai,j(i,jN,1im,1jn) a_{i,j} (i,j\in N, 1\le i\le m, 1\le j\le n) satisfies (1) (1) for any 1jn,a1,j,a2,j,,am,j 1\le j\le n, a_{1,j},a_{2,j},\cdots,a_{m,j} is a permutation of 1,2,3,,m;(2) 1,2,3,\cdots,m; (2) for any 1<im,1jn\minus1,ai,j\minusai,j\plus11 1 < i\le m, 1\le j\le n \minus{} 1, |a_{i,j} \minus{} a_{i,{j \plus{} 1}}|\le 1 holds. Find the minimal value of M M, where M\equalmax1<i<mj\equal1nai,j. M \equal{} max_{1 < i < m}\sum_{j \equal{} 1}^n{a_{i,j}}.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

1. Understanding the Problem:
- We are given an integer m>1 m > 1 and an odd number n n such that 3n<2m 3 \le n < 2m .
- We have a matrix ai,j a_{i,j} with 1im 1 \le i \le m and 1jn 1 \le j \le n .
- The matrix satisfies two conditions:
1. For any 1jn 1 \le j \le n , the elements a1,j,a2,j,,am,j a_{1,j}, a_{2,j}, \ldots, a_{m,j} form a permutation of 1,2,,m 1, 2, \ldots, m .
2. For any 1<im 1 < i \le m and 1jn1 1 \le j \le n-1 , ai,jai,j+11 |a_{i,j} - a_{i,j+1}| \le 1 .
- We need to find the minimal value of M M , where M=max1<i<mj=1nai,j M = \max_{1 < i < m} \sum_{j=1}^n a_{i,j} .

2. Analyzing the Conditions:
- The first condition ensures that each column of the matrix is a permutation of 1,2,,m 1, 2, \ldots, m .
- The second condition ensures that the difference between consecutive elements in any row (except the first row) is at most 1.

3. Constructing the Matrix:
- To minimize M M , we need to construct the matrix such that the sum of the elements in each row (except the first row) is as small as possible.
- Let's consider the simplest case where m=3 m = 3 and n=3 n = 3 :
123212331 \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 2 \\ 3 & 3 & 1 \\ \end{array}
- Here, the sums of the rows are:
j=13a1,j=1+2+3=6 \sum_{j=1}^3 a_{1,j} = 1 + 2 + 3 = 6
j=13a2,j=2+1+2=5 \sum_{j=1}^3 a_{2,j} = 2 + 1 + 2 = 5
j=13a3,j=3+3+1=7 \sum_{j=1}^3 a_{3,j} = 3 + 3 + 1 = 7
- Therefore, M=max(5,7)=7 M = \max(5, 7) = 7 .

4. Generalizing the Construction:
- For a general m m and n n , we can construct the matrix in a similar manner.
- For example, for m=4 m = 4 and n=3 n = 3 :
123212331444 \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 2 \\ 3 & 3 & 1 \\ 4 & 4 & 4 \\ \end{array}
- Here, the sums of the rows are:
j=13a1,j=1+2+3=6 \sum_{j=1}^3 a_{1,j} = 1 + 2 + 3 = 6
j=13a2,j=2+1+2=5 \sum_{j=1}^3 a_{2,j} = 2 + 1 + 2 = 5
j=13a3,j=3+3+1=7 \sum_{j=1}^3 a_{3,j} = 3 + 3 + 1 = 7
j=13a4,j=4+4+4=12 \sum_{j=1}^3 a_{4,j} = 4 + 4 + 4 = 12
- Therefore, M=max(5,7,12)=12 M = \max(5, 7, 12) = 12 .

5. **Finding the Minimal Value of M M :**
- To minimize M M , we need to ensure that the sums of the rows (except the first row) are as balanced as possible.
- The minimal value of M M can be achieved by constructing the matrix such that the sums of the rows are as close to each other as possible.

The final answer is 7 \boxed{7} .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.