Maths Olympiad Prep

Library / /32 of 97

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(1i,jn)x_{ij}(1\le i ,j\le n) satisfying:
(1)For every 1i,jn,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 1in1\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 1jn1\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. Spacing and $ signs are ignored.

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 1i,jn 1 \leq i, j \leq n ) satisfying the following conditions:
1. For every 1i,jn 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 1in 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 1jn 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,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.