MathDB
numbers always being local maximum in n*n matrix

Source: 2021ChinaTST test4 day1 P1

April 13, 2021
combinatoricsmatrix

Problem Statement

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}\}.