Let $ n(\ge2) $ be a positive integer. Find the minimum $ m $, so that there exists $x_{ij}(1\le i ,j\le n)$ satisfying: (1)For every $1\le i ,j\le n, x_{ij}=max\{x_{i1},x_{i2},...,x_{ij}\} $ or $ x_{ij}=max\{x_{1j},x_{2j},...,x_{ij}\}.$ (2)For every $1\le i \le n$, there are at most $m$ indices $k$ with $x_{ik}=max\{x_{i1},x_{i2},...,x_{ik}\}.$ (3)For every $1\le j \le n$, there are at most $m$ indices $k$ with $x_{kj}=max\{x_{1j},x_{2j},...,x_{kj}\}.$
Problem
Source: 2021ChinaTST test4 day1 P1
Tags: combinatorics, matrix
bumjoooon
20.04.2021 19:28
Is the translation correct? I'm afraid that $x_{i1}$ would not make sense if we restrict $i<j$.
mathematics2003
14.05.2021 03:48
bumjoooon wrote: Is the translation correct? I'm afraid that $x_{i1}$ would not make sense if we restrict $i<j$. Sorry for the same terrible typo as Day4P3 maybe I was sleeping while typing the question
CANBANKAN
17.03.2022 02:40
This problem is quite hard for its position. Also, I am sure the problem statement missed that $x_{i,j}$ are pairwise distinct. Put the numbers on a grid.
$1+\lceil \frac n2 \rceil$
Clearly it suffices to bound for $n$ odd.
Global + Equality: Call a square X if it is greater than all numbers to its left, and Y if it is greater than all numbers above it. Note the first column is all X and first row is all Y. This means that in the $(n-1)\cdot (n-1)$ subgrid not containing the first row and first column of the original grid. In this subgrid, each row contains at most $\frac{n-1}{2}$ X's and each column contains at most $\frac{n-1}{2}$ Y's. Summing, $(n-1)^2 \le \# X + \# Y \le \frac{n-1}{2} (n-1+n-1)=(n-1)^2$
This means equality holds, each column and row has exactly $\frac{n-1}{2}$ X's and Y's, and each square can only be one of X,Y.
Extremal (the hard part): We use the property that each square can be one of $X,Y$. Consider the grid with the largest value in this $(n-1) \cdot (n-1)$ subgrid, call $x_{k,j}$. If it is marked X, then consider its column. If there is a Y below it, it is not maximal. Otherwise, there is a Y above it (and between this X and the Y there are only X's), say at $x_{k,y}$. Then we can induct on $l$ to show for all $l>j, x_{k,l}<x_{k,j}$, or $x_{k,l}=max\{ x_{k,1}, \cdots, x_{k,l} \}$ contradicting $l$ being only $X$. Therefore, this grid cannot be the largest. Similarly, the largest number cannot have be marked Y, contradiction!
It clearly suffices to construct for $n$ even. Let $n=2k$. Divide the board into 4 $k\cdot k$ squares.
For $i,j\ge 2$: if $i=j>k$ then mark them with both X and Y.
If $i\le k$ and $j\le k$ or if $i>k$ and $j>k$ mark it with $X$
If $i>k$ and $j\le k$ or if $i\le k$ and $j>k$ or if $i=k+1$ and $j>k$ mark it with Y.
So construct as follows:
$x_{1,1}=10^{2k^2}.$ For $i\ge 2, x_{i,1}=i, x_{i,j}=i+jk^{-2}$. Set $x_{1,i}=k+i$ where $2\le i\le k$.
Set $x_{i,j}=k^{-2}+ik^{-6}+jk^{-4}$ for $j\in \{k+1,\cdots,2k\}, i\in \{1,\cdots,k\}$. They are only marked Y's because $x_{i,j}<x_{i,k}$.
Set $x_{j,1}=2^j$ for $j=k+1,\cdots, 2k$. Set $x_{j,t}=j+tk^{-2}$ for $t\in \{2,\cdots,k\}$ and $j\in \{k+1,\cdots,2k\}$.
Set $x_{k+1,t}=10^{(k+1)^t}$ for $t\in \{k+1,\cdots,2k\}$
Set $x_{l,t}=2^l+t\epsilon$ for $l\ge k+2, t\ge k+1$.