Maths Olympiad Prep

Library / China Team Selection Test /28 of 92

China Team Selection Test

Algebra Difficulty 7.7 National Olympiad, round 2 Find the answer

Let n(≥2) n(\ge2) be a positive integer. Find the minimum m m , so that there exists xij(1≤i,j≤n)x_{ij}(1\le i ,j\le n) satisfying:
(1)For every 1≤i,j≤n,xij=max{xi1,xi2,...,xij}1\le i ,j\le n, x_{ij}=max\{x_{i1},x_{i2},...,x_{ij}\} or xij=max{x1j,x2j,...,xij}. x_{ij}=max\{x_{1j},x_{2j},...,x_{ij}\}.
(2)For every 1≤i≤n1\le i \le n, there are at most mm indices kk with xik=max{xi1,xi2,...,xik}.x_{ik}=max\{x_{i1},x_{i2},...,x_{ik}\}.
(3)For every 1≤j≤n1\le j \le n, there are at most mm indices kk with xkj=max{x1j,x2j,...,xkj}.x_{kj}=max\{x_{1j},x_{2j},...,x_{kj}\}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n(≥2) n (\geq 2) be a positive integer. We aim to find the minimum m m such that there exists xij x_{ij} (for 1≤i,j≤n 1 \leq i, j \leq n ) satisfying the following conditions:
1. For every 1≤i,j≤n 1 \leq i, j \leq n , xij=max⁡{xi1,xi2,…,xij} x_{ij} = \max \{ x_{i1}, x_{i2}, \ldots, x_{ij} \} or xij=max⁡{x1j,x2j,…,xij} x_{ij} = \max \{ x_{1j}, x_{2j}, \ldots, x_{ij} \} .
2. For every 1≤i≤n 1 \leq i \leq n , there are at most m m indices k k such that xik=max⁡{xi1,xi2,…,xik} x_{ik} = \max \{ x_{i1}, x_{i2}, \ldots, x_{ik} \} .
3. For every 1≤j≤n 1 \leq j \leq n , there are at most m m indices k k such that xkj=max⁡{x1j,x2j,…,xkj} x_{kj} = \max \{ x_{1j}, x_{2j}, \ldots, x_{kj} \} .

To solve this, we need to consider the structure and constraints given by the problem. The solution involves ensuring that the maximum number of indices k k for which xik x_{ik} or xkj x_{kj} is the maximum is minimized.

By analyzing the constraints and constructing examples, it can be shown that the minimum m m satisfying the conditions is:
m=1+⌈n2⌉. m = 1 + \left\lceil \frac{n}{2} \right\rceil.

Thus, the minimum value of m m is:
1+⌈n2⌉. \boxed{1 + \left\lceil \frac{n}{2} \right\rceil}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.