Another square grid :D

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#1 h Oct 30, 2021, 11:00 PM • 11 Y

Y by megarnie, HWenslawski, Mogmog8, centslordm, OlympusHero, Zyz1010, 554183, The_Turtle, Pluto1708, Tastymooncake2, ItsBesi

Let $n$ be a fixed positive integer and consider an $n\times n$ grid of real numbers. Determine the greatest possible number of cells $c$ in the grid such that the entry in $c$ is both strictly greater than the average of $c$ 's column and strictly less than the average of $c$ 's row.

Proposed by Holden Mui

This post has been edited 2 times. Last edited by MathLuis, Nov 4, 2021, 11:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VulcanForge

626 posts

VulcanForge

#2 h Oct 30, 2021, 11:02 PM • 7 Y

Y by HWenslawski, centslordm, megarnie, Pluto1708, metricpaper, Tastymooncake2, MS_asdfgzxcvb

Answer: $(n-1)^2$ .

Construction shown below is easily generalizable.
$\begin{bmatrix} 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ -1&-1&-1&0 \end{bmatrix}$
Let $A$ be the set of minimums in the columns, and $B$ be the set of maximums in the rows (if these min/maxes are not unique, then perturb them so they are unique). Notice $|A \cap B| \le 1$ , or else we get a contradiction. Hence we have at least $2n-1$ of the cells are bad, so at most $(n-1)^2$ of them are good.

This post has been edited 3 times. Last edited by VulcanForge, Oct 31, 2021, 4:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Knty2006

50 posts

Knty2006

#3 h Oct 30, 2021, 11:03 PM • 3 Y

Y by HWenslawski, centslordm, samrocksnature

My answer seems really bad, but here goes nothing.

A "fat" square is a square that is minimum in column and maximum in its row.
Call a number that is non-" $c$ ", "dumb"

$subclaim$ : If we have a fat square on the same column or row, it is as good as not having another fat square.
Proof:
Firstly, note that each row and column has a minimum and a maximum value, therefore there should be a unique dumb square that corresponds to each row and column as long as a fat square does not cover it.

Observe that the new fat square that shares a column or row with an existing fat square only corresponds to a new column/row but it does not cover a new row/column. Hence, observe that even if we replace the new fat square with a dumb square the number of dumb squares that are needed still decreases by the same amount.

Therefore, we do not need to consider fat squares that are in the same row/column.

$claim 1:$ If there are $\geq 2$ fat squares in a different column and row, the number of dumb squares is the same as having no fat squares at all.

$Proof:$
For the sake of contradiction, suppose that there are $\geq 2$ fat squares in a different column and row. Select one fat square and rearrange it such that the fat square is on the bottom left of the $n$ by $n$ grid.

Suppose that the value in the fat square is $x$ . Note that the numbers in the same column $\geq x$ , numbers in the same row $\leq x$

Rearrange the row and column such that it is from largest to smallest ( left to right) and smallest to largest (bottom to top)

Now, consider the second fat-square in a different column and row, suppose that it has a value of $j$

Note that $j\leq x$ if you consider the column while $j\geq x$ if you consider the row. This implies that $j=x$
This means that all the edges of the rectangle formed by the terms containing $j$ and $x$ as it's corner pieces must all have the value $x$ .

Now, notice that the edges of the rectangle are "dumb" since they are either the minimum in column or maximum in their row, since they share the same value as $x$ and $j$

Furthermore, note that every row and column has $\geq1$ unique dumb square that corresponds to it as long as it is not covered by a "fat" square.

However, since there are no more fat squares outside of this rectangle, there is a unique dumb square for the remaining rows and columns.

Suppose that the rectangle has dimensions $a$ and $b$ then the number of dumb squares $\geq 2n-1 +(a+b-3)$
Since $a\geq, b\geq 2$ , we get that no of dumb squares $\geq 2n$

$claim2$ : If there are no "fat squares", no of dumb squares $\geq 2n$
Furthermore, note that every row and column has $\geq1$ unique dumb square that corresponds to it as long as it is not covered by a "fat" square.
So, there is a unique dumb square for each column and row $=>$ no. of dumb squares $\geq n+n=2n$

$claim3$ If we have $1$ fat square, the number of dumb squares $\geq 2n-1$
Note that 1 fat square will be able to cover $1$ dumb square for $1$ row and $1$ column, however, the remaining $n-1$ columns and rows will require a unique dumb square to correspond to it .
Therefore the number of dumb square $\geq (n-1) + (n-1) +1 =2n-1$

$claim 4$ Number of $c$ 's $\leq (n-1)^2$
Proof:
no of $c= n^2$ -no. of dumb squares $\leq$ $n^2-(2n-1)=(n-1)^2$

Construction:
Fill the $(n-1)$ by $(n-1)$ at the bottom left of the grid with $1$ , the topmost row's first $n-1$ values with $0$ 's, the rightmost column's bottom most $n-1$ values with $2$ and the top right grid with $69420$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathJams

3229 posts

MathJams

#4 h Oct 30, 2021, 11:08 PM • 5 Y

Y by HWenslawski, YBSuburbanTea, centslordm, RP3.1415, LLL2019

This is what I submitted.

Attachments:

This post has been edited 1 time. Last edited by MathJams, Oct 30, 2021, 11:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7338 posts

DottedCaculator

#5 h Oct 30, 2021, 11:25 PM • 3 Y

Y by centslordm, megarnie, IMUKAT

solution attached

Attachments:

2021 USEMO Problem 1.pdf (259kb)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The_Turtle

254 posts

The_Turtle

#6 h Oct 30, 2021, 11:25 PM • 25 Y

Y by ike.chen, Knty2006, MathJams, MathLuis, MarkBcc168, HamstPan38825, centslordm, megarnie, HrishiP, math31415926535, Idio-logy, Aryan-23, tigerzhang, 554183, mathleticguyyy, pad, Radio2, Atpar, pog, rayfish, mira74, Mogmog8, Pluto1708, mijail, Yiyj1

My problem

Solution

This post has been edited 1 time. Last edited by The_Turtle, Oct 30, 2021, 11:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#7 h Oct 30, 2021, 11:31 PM • 2 Y

Y by centslordm, Pluto1708

We claim that the greatest value is $(n-1)^2.$ Call a cell "good" if it satisfies the conditions and "bad" if not. Assign coordinates to our cells with $(1,1)$ the bottom left corner and $(n,n)$ the top right.

Claim: $(n-1)^2$ good cells is possible.
Proof. Let the upper-right $n\times n$ square be all zeros, the left-most column excluding $(1,1)$ be $1,$ and the down-most row be $-1.$ We see that all the zeros are good as $0<\tfrac{1}{n}<\tfrac{0(n-1)+1}{n}$ and $0>-\tfrac{1}{n}=\tfrac{0(n-1)-1}{n}.$ Also note that all the ones and negative ones are bad. $\blacksquare$

Let the cells with $x$ or $y$ coordinate $k$ with $k\in[1,n]$ be called the $k$ th "shell." Note each row/column cannot be all good so each shell must have at least one bad cell.

Claim: Each $n\times n$ grid can have at most one shell with one bad cell.
Proof. FTSOC let the $p$ th and $k$ th shell have only one bad cell, $b_p$ and $b_k.$

Sub-Claim: All cells with $x$ coordinate $p$ will be greater than $b_p,$ and all cells with $y$ coordinates $p$ will be less than $b_p.$
Proof. We will prove the $x$ coordinate part and the $y$ coordinate part will follow analogously. Notice that the cells with $x$ coordinate $p$ is the $p$ th column. Let the average of the column be $a_p.$ FTSOC assume at least one cell in the $p$ th column be less than or equal to $b_p.$
Case 1: $a_p<b_p.$ Since all other cells in the column are good, they are greater than the average. But then all the cells are greater than the average, so a contradiction.
Case 2: $a_p=b_p.$ Then, at least one other cell is less than or equal to $a_p,$ so a contradiction since all other cells must be good.
Case 3: $a_p>b_p$ Then, at least one other cell is less than $a_p,$ a contradiction. $\blacksquare$

Consider cells $(p,q)$ and $(q,p).$ Since $(p,q)$ has $x$ coordinate $p,$ it is greater than $b_p.$ Since it has $y$ coordinate $q,$ it is less than $b_q.$ Thus, $b_p<b_q.$ Similarly, $b_q<b_p$ from $(q,p).$ We have our desired contradiction $\blacksquare$

There are $n$ shells, and since all but one cell needs at least $2$ bad cells, there are at least $2n-1$ bad cells. Hence, there are at most $n^2-2n+1=(n-1)^2$ good cells. $\square$

This post has been edited 3 times. Last edited by Mogmog8, Oct 31, 2021, 3:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AwesomeYRY

579 posts

AwesomeYRY

#8 h Oct 30, 2021, 11:42 PM • 2 Y

Y by centslordm, opIst_w

Sketch of my solution:

Answer: $(n-1)^2$ .
Construction. Top row are -1s, right column is 1s, everything else is 0.

We now show that this is optimal. Let $A$ be the set of cells consisting of the leftmost cell in each row that is $\geq$ the average of the row. Let $B$ be the set of cells consisting of the uppermost cell of each column that is $\leq$ the average of the column. Clearly, $|A|=|B|=n$ .

Claim: $|A\cap B| \leq 1$ .
Proof: If we take $X,Y\in A\cap B$ , and the two cells in the rectangle together with them are $M,N$ , then we'll have some sort of
$X>M>Y>N>X$ contradiction.

Then, $|A\cup B| \geq 2n-1$ , so at most $n^2-(2n-1) = (n-1)^2$ squares are good.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5589 posts

megarnie

#9 h Oct 31, 2021, 1:00 AM • 1 Y

Y by centslordm

We claim the answer is $\boxed{(n-1)^2}$ .

This is achievable by making the rightmost column all ones except for the topmost cell and making the top row all $-1$ except for the rightmost cell. We label all other cells $0$ . This works because all the zeroes except for the zero in the top right cell can be a value of $c$ , which gives $(n-1)^2$ total values.

Now we will prove the bound.

Consider the smallest cell in each column and the largest cell in each row (if there are two within the same row or column, choose any one of these). There are $2n$ of these cells minus the number of cells that are the smallest in its column and largest in its row. None of these can be a value of $c$ .

Claim: There can be only one cell that is the smallest cell in its column and largest in its row.
Proof: AFTSOC that there are two. Label them $a$ and $b$ . Now we consider the two other intersection points between the columns and rows of these $a$ and $b$ . One of them must be labeled greater than $a$ and less than $b$ , which implies $a<b$ . The other must be labeled greater than $b$ and less than $a$ , which implies $b<a$ , a contradiction.

So we discard at least $2n-1$ cells, giving a maximum of $n^2-2n+1=(n-1)^2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HrishiP

1346 posts

HrishiP

#10 h Oct 31, 2021, 2:12 AM • 4 Y

Y by BlackMax, centslordm, megarnie, pog

The answer is $\boxed{(n-1)^2}$ . For construction, consider the following example for $n=4$ which easily generalizes:
$[asy] unitsize(14); int n = 4; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i < n && j < n || i == n && j == n) { label("1", (i, j)); } else if (i == n) { label("$2$", (i, j)); } else { label("$0$", (i, j)); } } } [/asy]$
Now call a cell satisfying the desired condition cool. Every row and column must have at least one cell that is less than the average of that row or cell (all the numbers in a set cannot be greater than the average). Thus we can count $2n$ cells that cannot be cool. However, we claim at most one square is counted twice, that is, there is at most one square that is the smallest in its row and largest in its column. Assume that there exists two such cells, with numbers say $x$ and $y$ . Consider the intersection of the column of $x$ and the row of $y$ . This implies that $x>y$ . Similarly $y<x$ , contradiction. Thus the maximum number of cool cells is $n^2-(2n-1) = (n-1)^2$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

edfearay123

92 posts

edfearay123

#11 h Oct 31, 2021, 2:27 AM • 1 Y

Y by centslordm

Sketch of a hard solution:
We will say that a cell is special if fulfills the conditions on the problem. We will say that a set of $n$ cells is special if all of its cells are special.
Claim 1: Each line (column or row) cannot be special.
Claim 2: We will say that a set of n cells is happy if there are not cells on the same column or row, then there are not a happy special set.

We define the above sets with fantastic (happy or lines) and they need at least one non special cell.

Now, basically we have to solve the following problem: In $n \times n$ find the maximum number of cells that are painted such that each fantastic set has at least one cell choosed. (Of course the answer is $2n-1$ painted cells!)

(Now please try this problem, it took me much time and if you have a solution please put it on the thread)
Click to reveal hidden text

The example for $2n-1$ is on the other solutions.

This post has been edited 2 times. Last edited by edfearay123, Nov 1, 2021, 3:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheStrayCat

161 posts

TheStrayCat

#12 h Oct 31, 2021, 3:05 AM • 1 Y

Y by centslordm

My idea: call a cell marked if it satisfies the condition from the statement and unmarked otherwise. Assume there are fewer than $2n-1$ unmarked cells. Consider the bipartite graph whose $2n$ vertices are the $n$ rows and $n$ columns, and in which a row is connected to a column whenever the cell at their intersection is unmarked. This graph must be disconnected, hence, there is at least one partitioning of all rows into disjoint sets $A$ and $B$ , and at least one partitioning of all columns into disjoint sets $C$ and $D$ such that all cells in $A \times C$ and $B \times D$ are marked. This implies $avg(A \times C)<avg(A \times D)<avg(B \times D)<avg(B \times C)<avg(A \times C)$ , where $avg(X)$ is the average of all numbers in the set $X$ of cells. Contradiction.

Examples for $n^2-2n+1$ have already been constructed above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

LLL2019

834 posts

LLL2019

#13 h Oct 31, 2021, 3:29 AM • 1 Y

Y by centslordm

Solution from my mocking

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#14 h Oct 31, 2021, 3:30 AM • 2 Y

Y by Eyed, centslordm

Call a cell good if it's greater than the average of its column and less than the average of its row.

Call a cell row-bad if it is the maximum of its row (if there are multiple, define the cell to be the leftmost maximum), and
Call a cell column-bad if it the minimum of its column (choose lowest if multiple).

Note that there exists a (unique) row-bad square in each row and a (unique) column-bad square in each column. Let $R_i$ be the row-bad square of row $i$ for each $i$ , and similarly define $C_i$ .

Claim. $|\{R_1,\ldots,R_n\}\cap \{C_1,\ldots,C_n\}| \le 1$ .

Proof. Suppose square $(i',j)$ (value $a$ ) and $(i,j')$ (value $b$ ) are both row-bad and column-bad. (The ordering of these coordinates is irrelevant.) Call $c$ the value in $(i,j)$ and $d$ the value in $(i',j')$ .

https://media.discordapp.net/attachments/752979051370774612/904198258732195850/unknown.png

Since we assumed $a$ is the leftmost maximum, we know $d\not = a$ . We have
$\begin{align*} a&\ge d, \quad a\le c \\ b&\ge c, \quad b\le d, \end{align*}$ which means $a>d\ge b\ge c\ge a$ , contradiction. $\blacksquare$

Now, notice $R_i$ are all bad and $C_i$ are all bad, and so there are at least $\{R_1,\ldots,R_n\}\cup \{C_1,\ldots,C_n\} \ge n+n-1 = 2n-1$ bad cells, so there are at most $n^2-(2n-1)=(n-1)^2$ good cells. A construction is to take an $(n-1)\times (n-1)$ grid of $0$ 's, and add on a row of $1$ 's to the right and a column of $-1$ 's to the bottom.

Motivation: First, I noticed that in each row, at least one cell exists that is greater than average, so it is bad. Similarly for the columns. So each row has at least 1 bad square, and so does each column; however, this is too weak to conclude the $(n-1)^2$ bound. A counterexample that illustrates this is if the set of bad squares is the diagonal of the grid. Then the $n$ ``row-bad'' and $n$ ``column-bad'' squares ``match up'', so we don't get $\approx 2n$ distinct bad squares, as needed.

So this made me think about when the row-bad and column-bad squares match up -- we want to prove this happens at most once. I called a square doubly-bad if it was not good and all squares on its row and column were good. This was the crucial mistake, since it is not true that if a square is less than the average of its column and more than the average of its row, then it is doubly-bad; we also need everything to be good, which is not always going to happen.

Anyways, I let $C_1,\ldots,C_n$ and $R_1,\ldots,R_n$ be arbitrary squares in the columns and rows respectively, which are greater than the average of the row and less than the average of the column, respectively. The key in my above solution is to instead make these the maximum and minimum, removing the necessity of everything else in the row/column being good. With this old definition, I made an inequality chain similar to my solution above's, where instead of the maximum and minimum giving the inequalities, it was the fact that one is greater and one is less than the average in the row/column. Again, while the claim is technically true for this definition, it is useless, since $C_i=R_j$ does not imply $(i,j)$ is doubly bad.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math90

1476 posts

math90

#15 h Oct 31, 2021, 4:39 AM

Y by

I don't understand the problem statement. Is $c$ a number or a subset of cells?

This post has been edited 1 time. Last edited by math90, Oct 31, 2021, 4:40 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math31415926535

5617 posts

math31415926535

#16 h Oct 31, 2021, 4:51 AM

Y by

math90 wrote:

I don't understand the problem statement. Is $c$ a number or a subset of cells?

the former

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math90

1476 posts

math90

#17 h Oct 31, 2021, 5:04 AM

Y by

So what is "the entry in $c$ "?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blackbluecar

302 posts

blackbluecar

#18 h Oct 31, 2021, 5:11 AM • 1 Y

Y by centslordm

Let $S$ denote the set of squares with the desired property. Wlog slightly tweak the value on each cell so that they are all distinct. We let $A$ be the set of maximal numbers on each row and $B$ be the minimum value of each column. Notice that all elements in $A \cup B$ are not in $S$ .

Claim: $|A \cup B| \geq 2n-1$

Assume the contrary, this implies that there exists distinct $x$ and $y$ in both $A$ and $B$ . Let their rows and columns be $R_X$ , $C_X$ , $R_Y$ , and $C_Y$ . Notice that this implies that every number in $C_X$ is strictly greater than every value in $R_X$ and the same for $R_Y$ and $C_Y$ . But, if $R_X$ and $C_Y$ intersect at $s_1$ and $R_Y$ and $C_X$ intersect to $s_2$ , this implies $s_1>s_2$ and $s_1<s_2$ . Contradiction.

Thus $|S| \leq n^2-|A \cap B| \leq (n-1)^2$ . Indeed, we get the following construction.

$M$ $m$ $m$ $m$
$M$ $1 \text{ } \text{ } 1 \text{ } \text{ } 1$
$M$ $1 \text{ } \text{ } 1 \text{ } \text{ } 1$
$M$ $1 \text{ } \text{ } 1 \text{ } \text{ } 1$

Where $M$ super large and $m$ is super small

This post has been edited 3 times. Last edited by blackbluecar, Nov 2, 2021, 3:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6874 posts

v_Enhance

#19 h Oct 31, 2021, 2:17 PM • 4 Y

Y by megarnie, math90, centslordm, HamstPan38825

math90 wrote:

I don't understand the problem statement. Is $c$ a number or a subset of cells?

$c$ is a single cell

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#20 h Oct 31, 2021, 3:43 PM • 1 Y

Y by centslordm

use induction and take cases, we can show the maximum for each case is $n^2-2n+1$ and then provide construction

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aopsuser305

678 posts

aopsuser305

#21 h Oct 31, 2021, 3:51 PM

Y by

pad wrote:

Click to reveal hidden text

I also used this solution method, was nervous that I got it wrong because no one posted a similar sol (until you now did).

This post has been edited 2 times. Last edited by aopsuser305, Oct 31, 2021, 3:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gghx

1071 posts

gghx

#22 h Nov 1, 2021, 2:02 AM • 1 Y

Y by centslordm

Someone please tell me if this is wrong:

We colour a cell black if it satisfies the condition in the question statement.

Claim 1: no entire row/column is black (obvious).

Claim 2: for any $n$ cells which are all in distinct rows and columns, not all of them are black.
Proof: Suppose there exists such $n$ cells, and their total sum is $t$ .
Then, consider the sum of all the other cells, $s$ .
We have $s>(n-1)t$ when looking at rows, but $s<(n-1)t$ when looking at columns, contradiction.

We now ignore the numbers altogether.

We show that for any set of $n$ cells that satisfy the two claims, the number of black cells is $\le (n-1)^2$ .
Suppose that there is such a colouring with $(n-1)^2+2$ cells.

Let the number of black cells in row $i$ be $x_i$ . WLOG $x_i\ge x_{i-1}$ .

By claim 1, $x_1\ge 1$ .

If there is some $x_i<i$ , then we have $(n-1)^2+1=x_1+x_2+...+x_n\le (i-1)i+(n-1)(n-i)$ . This is equivalent to $(i-1)(i+1-n)\ge 1$ , which can only happen when $i=n$ .

This means $x_1\ge 1, x_2\ge 2, ..., x_{n-1}\ge n-1$ and $x_n\ge n-1$ .

If the $n-1$ and $n$ columns have the different sets of black cells, we can construct a set of $n$ cells that contradict claim 2 by picking one from column $1$ , one from column $2$ which is not part of the current set, one from column $3$ , ..., one from column $n-2$ and for the last two cells, one from column $n-1$ and column $n$ . This is a contradiction.

If the $n-1$ and $n$ columns have the same set of black cells, WLOG that they both do not have a black cell in the nth row. There must be some column $i$ that has a black cell in the nth row. Suppose that $i$ is the smallest such column. We can thus tweak our previous method a bit by taking the black cell in the nth row when it comes to picking a cell from the ith column.

Construction is the same as all the above (with 0,1,-1s).

I hope this made sense.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

edfearay123

92 posts

edfearay123

#23 h Nov 1, 2021, 3:38 AM

Y by

gghx wrote:

Someone please tell me if this is wrong:

We colour a cell black if it satisfies the condition in the question statement.

Claim 1: no entire row/column is black (obvious).

Claim 2: for any $n$ cells which are all in distinct rows and columns, not all of them are black.
Proof: Suppose there exists such $n$ cells, and their total sum is $t$ .
Then, consider the sum of all the other cells, $s$ .
We have $s>(n-1)t$ when looking at rows, but $s<(n-1)t$ when looking at columns, contradiction.

We now ignore the numbers altogether.

We show that for any set of $n$ cells that satisfy the two claims, the number of black cells is $\le (n-1)^2$ .
Suppose that there is such a colouring with $(n-1)^2+2$ cells.

Let the number of black cells in row $i$ be $x_i$ . WLOG $x_i\ge x_{i-1}$ .

By claim 1, $x_1\ge 1$ .

If there is some $x_i<i$ , then we have $(n-1)^2+1=x_1+x_2+...+x_n\le (i-1)i+(n-1)(n-i)$ . This is equivalent to $(i-1)(i+1-n)\ge 1$ , which can only happen when $i=n$ .

This means $x_1\ge 1, x_2\ge 2, ..., x_{n-1}\ge n-1$ and $x_n\ge n-1$ .

If the $n-1$ and $n$ columns have the different sets of black cells, we can construct a set of $n$ cells that contradict claim 2 by picking one from column $1$ , one from column $2$ which is not part of the current set, one from column $3$ , ..., one from column $n-2$ and for the last two cells, one from column $n-1$ and column $n$ . This is a contradiction.

If the $n-1$ and $n$ columns have the same set of black cells, WLOG that they both do not have a black cell in the nth row. There must be some column $i$ that has a black cell in the nth row. Suppose that $i$ is the smallest such column. We can thus tweak our previous method a bit by taking the black cell in the nth row when it comes to picking a cell from the ith column.

Construction is the same as all the above (with 0,1,-1s).

I hope this made sense.

I think that your solution is correct, I thought the same problem of the black squares, and I put a solution of that above (Is a bit harder than yours).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

554183

484 posts

554183

#24 h Nov 1, 2021, 7:16 AM • 1 Y

Y by centslordm

I hope this works. Anyway this is a really nice problem.
WLOG all entries are distinct. Let all cells satisfying the condition in the problem statement be called good and bad otherwise. I claim that there are a minimum of $2n-1$ bad cells. Notice that the cell with the maximum entry in each row and minimum entry in each column is always bad. But there might be cells which have the maximum entry in their row and minimum entry in their column. Now I claim that there can be at maximum of one such cell. FTSOC assume there are at least 2. Now in the figure attached, its easy to see that $a>c>b$ and $a<d<b$ , contradiction, so our claim is proven.
Therefore, it follows that there are at least $2n-1$ of bad cells and our result follows (construction has been provided above.)

Attachments:

This post has been edited 2 times. Last edited by 554183, Nov 1, 2021, 8:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

edfearay123

92 posts

edfearay123

#25 h Nov 4, 2021, 3:10 AM

Y by

pad wrote:

$\begin{align*} a&\ge d, \quad a\le c \\ b&\ge c, \quad b\le d, \end{align*}$ which means $a>d\ge b\ge c\ge a$ , contradiction. $\blacksquare$

I saw that various solutions use that the number on the cells are different, but the problem doesn't say it.

This post has been edited 1 time. Last edited by edfearay123, Nov 4, 2021, 1:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

edfearay123

92 posts

edfearay123

#26 h Nov 4, 2021, 1:18 PM

Y by

AwesomeYRY wrote:

Claim: $|A\cap B| \leq 1$ .
Proof: If we take $X,Y\in A\cap B$ , and the two cells in the rectangle together with them are $M,N$ , then we'll have some sort of
$X>M>Y>N>X$ contradiction.

HrishiP wrote:

Now call a cell satisfying the desired condition cool. Every row and column must have at least one cell that is less than the average of that row or cell (all the numbers in a set cannot be greater than the average). Thus we can count $2n$ cells that cannot be cool. However, we claim at most one square is counted twice, that is, there is at most one square that is the smallest in its row and largest in its column. Assume that there exists two such cells, with numbers say $x$ and $y$ . Consider the intersection of the column of $x$ and the row of $y$ . This implies that $x>y$ . Similarly $y<x$ , contradiction. Thus the maximum number of cool cells is $n^2-(2n-1) = (n-1)^2$ . $\blacksquare$

Prabh2005 wrote:

I hope this works. Anyway this is a really nice problem.
WLOG all entries are distinct. Let all cells satisfying the condition in the problem statement be called good and bad otherwise. I claim that there are a minimum of $2n-1$ bad cells. Notice that the cell with the maximum entry in each row and minimum entry in each column is always bad. But there might be cells which have the maximum entry in their row and minimum entry in their column. Now I claim that there can be at maximum of one such cell. FTSOC assume there are at least 2. Now in the figure attached, its easy to see that $a>c>b$ and $a<d<b$ , contradiction, so our claim is proven.
Therefore, it follows that there are at least $2n-1$ of bad cells and our result follows (construction has been provided above.)

For example, here there is not a contradiction:

$\begin{tabular}{| c | c | c c c | c |c |} \hline & 3 & & & & 3 & \\ \hline 1& 2 & 1 & \dots & 1 & 2 & 1 \\ \hline & 3 & & & & 3 & \\ & 3 & & & & 3 & \\ \hline 1& 2 & 1 & \dots & 1 & 2 & 1 \\ \hline & 3 & & & & 3 & \\ \hline \end{tabular}$
I don't say that there is an example with various of that type of cells and answer more than $(n-1)^2$ , but I think that the solution doesn't finish in that part (a friend showed me a solution if the cells are equal)

This post has been edited 2 times. Last edited by edfearay123, Nov 4, 2021, 2:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

554183

484 posts

554183

#27 h Nov 6, 2021, 6:27 AM

Y by

i mean we can wlog assume that the entries in all cells are distinct by just increasing the entries in the appropriate cells by a very small value chosen so that the "good" cells (the ones satisfying the problem condition) remain good, right?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#31 h Nov 26, 2021, 7:09 PM • 1 Y

Y by centslordm

A bit overcomplicated but I used Hall's on an actual problem without being told to use Hall's for the first time. Did not think of infinitesimal perturbations

The answer is $c=(n-1)^2$ , which is achievable by making the bottom right cell $0$ , the rest of the bottom row $-1$ , the rest of the right column $1$ , and everything else $0$ . It remains to prove that this is the maximum.
Call a square that's greater than its column's average but less than its row's blue. Evidently there must be at most $n-1$ blue cells in a single column or row. Now, suppose FTSOC that there are at least $n^2-2n+2$ blue squares, so there are most $2n-2$ non-blue squares. Given this, the key claim is the following:

Claim: There exists a perfect matching of rows to columns such that their intersection is a blue square.
Proof: We will use Hall's marriage lemma, so it suffices to prove that any set $S$ of $k$ rows there are at least $k$ columns that intersect some element of $S$ at a blue square. Suppose otherwise. Then for $k<n$ , among the $k$ rows in $S$ there are at most $k(k-1)$ blue cells, and in the remaining $n-k$ rows there are at most $(n-k)(n-1)$ , for a total of
$k(k-1)+(n-k)(n-1)=k^2-nk+(n^2-n),$ which being a upwards-opening parabola in $k$ symmetric about $k=\tfrac{n}{2}$ is maximized when $k=1$ , where it attains a value of $n^2-2n+1<n^2-2n+2$ , contradiction. If $k=n$ , then note that the rows which do overlap some element of $S$ , of which there are at most $n-1$ , can have at most $n-1$ blue squares, for a total of $(n-1)^2<n^2-2n+2$ cells in total as well. Thus Hall's condition holds so a perfect matching exists. $\blacksquare$

Given this perfect matching, let $f(r)$ denote the column paired with row $r$ and $g(r)$ the (blue) intersection between $r$ and $f(r)$ . Next let $M(a)$ denote the average of row or column $a$ , so we have
$M(r)>g(r)>M(f(r)).$ Summing over all $r$ , this means
$\sum_{r \in R} M(r) > \sum_{c \in C} M(c),$ where $R,C$ denote the sets of rows and columns respectively. But this is absurd, as the two quantities should be equal by double counting. Hence $c \geq (n-1)^2+1$ is impossible, as desired. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Nov 26, 2021, 7:11 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cindy.tw

54 posts

Cindy.tw

#32 h Feb 11, 2022, 1:48 PM • 1 Y

Y by centslordm

The answer is $(n-1)^2$ .

Construct a $n \times n$ grid of numbers in the following way
$\begin{matrix} 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 0 & 1 \\ \vdots & & \cdots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \\ -1 & -1 & \cdots & -1 & 0 \end{matrix}$ Thus $(n-1)^2$ is obtainable. Now we show that $(n-1)^2$ is optimized.

Let $r_i$ be the average of the $i$ -th row and $c_j$ be the average of the $j$ -th column. Assume for the sake of correctness that there are $(n-1)^2 + 1$ cell satisfying the condition. Draw a bipartite graph with vertex $r_i$ s and $c_j$ s, if the cells in the $i$ -th row and $j$ -th column satisfies the condition, connect two vertex $r_i$ and $c_j$ . In this case, we have $r_i > \text{the entry in the cell} > c_j$ . While the number of edges is at least $(n-1)^2 + 1$ , thus, there is a perfect matching between $r_i$ and $c_j$ (well-known). However, this will derive $\sum_{i=1}^n r_i > \sum_{j=1}^n c_j$ , which is absurd since it is an equality.

This post has been edited 1 time. Last edited by Cindy.tw, Feb 11, 2022, 1:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TortilloSquad

305 posts

TortilloSquad

#33 h Aug 9, 2022, 2:59 AM • 1 Y

Y by Mathlover_1

The answer is $(n-1)^2$ , which can be achieved with the bottom right square $=0$ , the rest of the rightmost column $=1$ , the rest of the bottom row $=-1$ and everything else $=0$ .

Call a cell good if it satisfies the problem condition and call it bad if it doesn't. Consider a grid, and if the values are not unique simply shift them by very small numbers to make them unique. Clearly, if a cell is the maximum in its row, it is bad. If it is the minimum of its column, it is also bad. Call a cell that is both the maximum in its row and the minimum in its column noob.

Claim: There is at most one noob cell in the grid.

Assume there can be more than one, and consider two noob cells $X$ and $Y$ . Clearly they are in different rows and columns. Let $X=(x_1,y_1)$ and $Y=(x_2,y_2)$ . Then, let $A=(x_1,y_2)$ and $B=(x_2,y_1)$ . Since $A$ is in $X$ 's column, we have $A>X$ . Since $A$ is in $Y$ 's row, we have $A<Y$ , so we have $X<A<Y$ , so $X<Y$ . Doing something similar for $B$ we end up having $Y<B<X$ , which is a clear contradiction.

Therefore we have at least $n+n-1=2n-1$ bad cells, so at most $n^2-(2n-1)=(n-1)^2$ good cells, which is achievable with the construction above. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PHSH

60 posts

PHSH

#35 h Sep 20, 2022, 9:31 PM

Y by

Here goes my lol IQ solution.

We claim the answer is ${(n-1)}^2$ which is achived by similar constructions described in the above solutions (say, make a $(n-1)\times (n-1)$ square with whatever you want, and then make each number in the remaining column large enough and all number in the remaining row small enough).

Now we show ${(n-1)}^2$ is optimal. Call a cell good if it satisfies the conditions in the problem statement. Define a group as a set of $n$ cells such that any two among them lie in different row and column. The key idea (of my solution) is to notice that we cannot have an entire row, column or group covered by good cells (row and column is clear; in order to see that a group cannot be covered by good cells, notice that this would imply that the sum of all numbers in the grid(counted by row) is stricktly greater than the sum of all numbers in the grid(now counted by columns) which is absurd). Now we can rephrase problem as follows

Quote:

If $S$ is a set of cells in a $n\times n$ grid such that $S$ does not covers a group, a row or a column, then $S$ has at most ${(n-1)}^2$ cells.

Proof:
We proceed by induction with base case trivial. First notice that if any row in the grid has at most $n-2$ cells in $S,$ then we have in total at most $n(n-2) = {(n-1)}^2-1$ cells and we are done. Similarly, we take off the cases where each column and each group has at most $(n-2)$ cells.

Now assume that the situations described in the last paragraph does not hold any, and furthermore assume for the sake of contradiction that $S$ has at least ${(n-1)}^2+1$ cells. Then let $i$ and $j$ be a row and a column, respectively, containing $n-1$ cells of $S.$ If $i\cap j$ is not an empty cell, we can remove $i$ and $j$ and then apply inductive hyphothesys to the remaining square which contains at least ${(n-1)}^2-2(n-1) + 2 = {(n-2)}^2 +1$ so that we find a row, line or group $k$ covered by $S$ in the remaining square. If $k$ is a group, we can merge it with $i\cap j$ and we die. Otherwise, $k$ is a row or a column; if $k$ is a column (respectively row), it must be the case that, in the original grid, the column of $k$ (respectively row) must contain the unique non-covered cell of $j$ (respectively i). In either case, by replacing $j$ with $k$ (respectively $i$ with $k$ ) we find a row and a column $p$ and $q$ each with $n-1$ cells in $S$ , intersecting at the unique non-covered cell of both.

Now remove $p$ and $q$ from the grid. Then the remaining square has at least ${(n-2)}^2$ cells in $S.$ We cannot apply inductive hyphothesis directly but we can proceed as follows: consider a cell of the square which is not in $S$ and put in $S$ temporally. Then we find a group, row or column in $S$ (which may contain our added cell); if it is a group, we can delete a cell of this group (if one of these cells is the one we added, then we necessarily remove this one) and add the two corresponding cells in $p$ and $q$ (i.e., the cell in $p$ which is at the same column of the deleted cell, and the cell in $q$ that is at the same row of the deleted cell); these cells are necessarily in $S$ by construction and so we find a group in the original grid and then die. Finally, we repeat this to all non-empty cells of the new grid, if we have not died after this, we conclude that each non-covered cell of the new grid must lie on a row or in a column with all other cells in $S.$ This bounds the number of non-covered cells in the new grid by $n-1$ so that we can apply inductive hyphothesis now and get an absurd once again. $\square.$

remark

This post has been edited 8 times. Last edited by PHSH, Sep 20, 2022, 9:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#36 h Jan 16, 2023, 1:26 AM • 2 Y

Y by centslordm, Mango247

The answer is $(n-1)^2$ .

Construction: Fix some very small $\varepsilon$ , and use the grid
$\begin{bmatrix} 1 & 1 & \cdots & 1 & 1/\varepsilon \\ 1 & 1 & \cdots & 1 & 1/\varepsilon \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \varepsilon & \varepsilon & \cdots & \varepsilon & 1. \end{bmatrix}$ This obviously works when $\varepsilon$ is sufficiently small: every square in the top $(n-1) \times (n-1)$ portion of the grid satisfies the conditions.

Proof of Bound: Call a balanced square in the grid a square that does not satisfy the given conditions, and let there be $k$ balanced squares. Observe that there must be at least one balanced square in every row and column. Furthermore, color a balanced square red if it is the local maximum in its row and blue if it is the local minimum in its column. It is guaranteed that there are exactly $2n$ colorings, including multiplicity.

Claim. There cannot be two squares that are double-colored.

Proof. Suppose that there are two such squares, say containing values $a$ and $b$ , respectively. Furthermore, let the numbers in the squares that constitute the other two intersections between those two rows and columns be $c$ and $d$ , with $c$ sharing a row with $a$ . Then, by definition, we have $a>c>b \text{ and } a<d<b$ simultaneously, which is obviously impossible. $\blacksquare$

Because no square can be triple-colored, this implies that there are at least $2n-1$ balanced squares. Thus, the number of valid squares is at most $n^2-k \leq n^2-(2n-1) = (n-1)^2,$ as required.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Taco12

1757 posts

Taco12

#37 h Feb 2, 2023, 1:31 AM • 1 Y

Y by megarnie

We claim the answer is $(n-1)^2$ . Our construction is to keep the bottom right cell as a $0$ , the rest of the bottom row as a $-1$ , the rest of the rightmost column as a $1$ , and the rest of the cells as $0$ s. We now show that this is optimal. Note that a square is "bad" (doesn't satisfy the condition) if it is the max in its row and the min in its column.

Claim: At most $1$ square can be the max in its row and the min in its column.
Proof. Assume that there are $2$ such cells, with entries $a$ and $b$ . Let the intersection of $a$ s row and $b$ s column be $c$ . Let the intersection of $a$ s column and $b$ s row be $d$ . Then note that we have $c < a < d, d<b<c,$ a contradiction. $\square$

Thus, there are a maximum of $n^2-(2n-1)=(n-1)^2$ cells satisfying the requirement. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#38 h Aug 5, 2023, 1:35 AM

Y by

The answer is $(n-1)^2$ . To construct this take a 0 in the top right, -1s in the top row other than that, and 1s in the right column other than that. Now, we complement count. If X and Y are the sets containing the cells such that they're the smallest cell in their column and largest in their row and vice versa, respectively, then |X|+|Y|=2n (for example, for X, in each row there's one cell that satisfies, so in n rows there's n ways).

Now, we prove the intersection of X and Y is at most 1. FTSOC if there were at least two elements, taking the intersections of their 2 rows and 2 columns (let these cells be P and Q) makes two other cells R and S. From the condition of P and Q we know that Q>R>P and P>S>Q, contradiction.

So the complement set union is at least 2n-1, hence the cells that work are at most $n^2-2n+1=(n-1)^2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Jndd

1416 posts

Jndd

#39 h Aug 11, 2023, 7:22 PM

Y by

The answer is $(n-1)^2$ , so let's prove it. A construction to show that's possible is
$\begin{align*} &1\text{ }\text{ } 1\text{ }\text{ } 1\text{ }\text{ } 2\\ &1\text{ }\text{ } 1\text{ }\text{ } 1\text{ }\text{ } 2\\ &1\text{ }\text{ } 1\text{ }\text{ } 1\text{ }\text{ } 2\\ &0\text{ }\text{ } 0\text{ }\text{ } 0\text{ }\text{ } 1 \end{align*}$ which is an example for a $4\times 4$ grid, but we can extend this by letting the upper left $(n-1)\times (n-1)$ grid be all $1$ s, and extend the bottom row and right column accordingly as well.

Now we consider what happens when the least number of every column and greatest number of every row is distinct. For each row, at least one number must be greater than or equal to its average, and for each column, at least one number must be less than or equal to its average. That makes the number of bad cells at least $2n-\alpha$ where $\alpha=\text{number of cells that are both greater than the row average and less than the column average}$ .

Now we show that $\alpha$ is $1$ at maximum. Let $a_1, a_2,\ldots, a_{n-1}$ be the numbers in a row, $c_1, c_2, \ldots, c_{n-1}$ be the numbers in a column, and let $b$ be a cell that's in both the row and the column. Now, let $a_i<b<c_j$ for all $i,j\in\{1, 2, \ldots, n-1\}$ , so $b$ counts for $\alpha$ . Now, say there was another cell $b'$ that also counter for $\alpha$ . That would mean for some $a_i$ , we have $a_i$ is in the column of $b'$ , and for some $c_j$ , we have that $c_j$ is in the row of $b'$ , meaning $c_j<b'<a_i$ , contradiction. So, $\alpha$ is at most $1$ .

So, since the number of bad cells is at least $2n-1$ , the number of good cells is at most $n^2-(2n-1)=(n-1)^2$ . Now, if the least number from a column or the greatest number from a row wasn't distinct, we can perturb those numbers by a sufficiently small amount so that the state of every cell being good or bad for doesn't change, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#40 h Oct 27, 2023, 11:07 PM

Y by

The answer is $\boxed{n^2-2n+1}$ , achievable with the following formation:

$\begin{bmatrix} 0&0&0&1\\ 0&0&0&1\\ 0&0&0&1\\ -1&-1&-1&0 \end{bmatrix}$
which is easily generalized to $n>4$ .

Notice that there is at most one number that is the least in their column and the most in their row. If there are two, an impossible chain of inequalities arises.

Then, consider the set of numbers that are either the least in their column or the most in their row. There are at least $2n-1$ of them, none of them being able to be $c$ . This means the maximum is $n^2-2n+1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

794 posts

shendrew7

#41 h Dec 18, 2023, 1:24 AM

Y by

Claim: There is at most one number which is strictly the greatest in its row and strictly the least in its column.

Suppose FTSOC there exists two numbers $a \ge b$ (obviously in different rows and columns) which satisfies this condition. Then the cell in the same column as $a$ and the same row as $b$ should be greater than $a$ but less than $b$ , contradiction. ${\color{blue} \Box}$

Note each number which is the greatest in its row or the least in its column cannot satisfy the problem statement, and PIE tells us there must be at least $2n-1$ of them. Hence the greatest possible number of valid cells is $\boxed{n^2-2n+1}$ , which are the 0's in the top left of the following construction:
$\begin{matrix} 0 & 0 & \cdots & 0 & -1 \\ 0 & 0 & \cdots & 0 & -1 \\ \vdots & \vdots & \cdots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & -1 \\ 1 & 1 & \cdots & 1 & 0 \end{matrix}$

This post has been edited 1 time. Last edited by shendrew7, Dec 18, 2023, 1:42 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RGB

19 posts

RGB

#42 h Dec 20, 2023, 11:07 AM

Y by

Denote the $i$ th row's average as $r_i$ and the $j$ th column's average as $c_j$ .

For a cell $c_{ij}$ at the intersection of row $i$ and column $j$ , the condition given can be represented as $c_{ij} > r_i$ and $c_{ij} < c_j$ . We want to maximize the number of cells that satisfy this condition.

Let's consider the strategy to maximize the count of such cells:

Assign the maximum value to the top-left cell $c_{11}$ .
Assign increasing values to the first row $r_1$ from left to right.
Assign increasing values to the first column $c_1$ from top to bottom.
This pattern ensures that for any cell $c_{ij}$ beyond the first row and first column, it will have a value greater than the average of its row and less than the average of its column. Therefore, all cells beyond the first row and first column satisfy the given condition.

The count of such cells beyond the first row and first column is $(n - 1) \times (n - 1) = (n - 1)^2$ .

Additionally, the top-left cell $c_{11}$ is greater than the averages of both its row and column. Therefore, the total count of cells satisfying the condition is $(n - 1)^2 + 1$ .

Hence, the greatest possible number of cells that satisfy the given condition in an $n \times n$ grid of real numbers is $(n - 1)^2 + 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

196 posts

de-Kirschbaum

#43 h Apr 13, 2024, 5:39 PM

Y by

We claim that the answer is $(n-1)^2$ . Let us denote each cell by $a_{11}, a_{12},...a_{1n}, a_{21},...,a_{nn}$ . Let us denote the sum of the $i$ th row as $r_i$ and the sum of the $i$ th column as $c_i$ . Note that in any row if we take $n$ cells to be entries satisfying the condition, then we get that $r_i<r_i$ and if we take $n$ cells in a column to be entries satisfying the condition, we get that $c_i>c_i$ . Thus, $c \leq (n-1)^2$ . We will show by construction that $c=(n-1)^2$ works. If it does, that means the following inequalities are true
$(r_1+...+r_{n-1}-a_{1n}-a_{2n}-...-a_{n-1n})<\frac{n-1}{n}(r_1+...+r_{n-1})$ Note $a_{1n}+a_{2n}+...+a_{n-1n}=c_{n}-a_{nn}$ .
Thus
$(r_1+..+r_{n-1})<n(c_n-a_{nn})$ Similarly, $(c_1+...+c_{n-1})>n(r_n-a_{nn})$
Summing the two inequalities up and manipulating, we get $c_n>r_n$ which motivates the construction. Consider $a_{nn}=\pi$ (just because it can be anything really). Let every other entry in the n-th column be $\frac{\pi+1}{n-1}$ , every other entry in the n-th row be $\frac{\pi-1}{n-1}$ . Let every entry in the $(n-1) \times (n-1)$ grid be $\frac{\pi}{n-1}$ . Then, we have that every entry in that grid is strictly greater than the average of its column since $\frac{\pi}{n-1}>\frac{\pi+\frac{\pi-1}{n-1}}{n} \implies \pi>\pi-1$ . We can check the other condition similarly.

This post has been edited 1 time. Last edited by de-Kirschbaum, Apr 13, 2024, 5:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

surpidism.

10 posts

surpidism.

#45 h Jun 3, 2024, 6:11 PM

Y by

The answer is $(n-1)^2$ . This can be achieved by the following construction:
$\begin{matrix} -1 & -1 & \cdots & -1 & 0 \\ 0 & 0 & \cdots & 0 & 1 \\ \vdots & \vdots & \cdots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 0 & 1 \end{matrix}$
Now we prove that we can't attain more than this.

Call a cell 'good' if entry in it is both strictly greater than the average of its column and strictly less than the average of its row, and remaining cells as 'bad'. Note that maximizing the number of good cells is equivalent to minimizing the number bad cells.
Observe that if an entry in a cell is the smallest in its column or the largest in its row, then it must be a bad cell. And each row and colum has a largest and smallest entry, respectively. Let $a$ be the number of cells that is both the largest in its row and smallest in its columns (these cells are counted twice), then number of bad cells $\geq 2n - a$ .

Claim: $max(a) = 1$
Proof: FTSOC, assume $max(a) > 1$ . Then consider any two cells with entries $p$ and $q$ with such property. Clearly, $p$ and $q$ are in differetn rows and columns. Now consider the intersection fo rows and columns containing $p$ and $q$ ; $r$ be the intersection of row with $p$ and columns with $q$ and $s$ be the other intersection.
We get the inequalities; $p > r > q$ and $p < s < q$ . Clearly a contradiction.

Hence, number of bad cells $\geq 2n - 1$ which implies, maximum number of good cells $= n^2 - (2n -1) = (n-1)^2$ , as required. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3443 posts

ihatemath123

#46 h Aug 19, 2024, 9:29 PM

Y by

The answer is $(n-1)^2$ , obtained by making the top left square $0$ , the rest of the top row $-1$ , the rest of the left column $1$ and everything else $0$ . All the cells that are not in the top row or leftmost column will satisfy the condition in the problem.

To prove the bound: assume WLOG that all the numbers are distinct. Suppose FTSOC there are two distinct cells $A$ and $C$ which are the largest in the column and smallest in the row. But then consider cells $B$ and $D$ such that $ABCD$ is a rectangle – we have $A > B > C$ and $C > D > A$ simultaneously, which is a contradiction.

So, there are at least $2n-1$ cells which are the largest in the column or the smallest in the row – none of these satisfy the condition in the problem, leaving us with at most $n^2 - 2n + 1$ cells which do.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PEKKA

1844 posts

PEKKA

#47 h Sep 1, 2024, 6:48 PM

Y by

The answer is $(n-1)^2.$
This works by making the top row $0,$ the rightmost column except the top-right square a really big number (call it $N$ for now) and every other entry some positive real a lot smaller than $N.$ Call this other entry $k.$
Notice that every cell filled with $k$ exceeds the average of its column and is under the average of its row, showing that $(n-1)^2$ works.
To see why any larger value fails, notice that by pigeonhole a larger value implies some column contains $n$ numbers that contribute to the total, which means all $n$ elements exceed the average of the $n$ elements, which is a contradiction.
The stuff in red is actually false. Will fix

This post has been edited 1 time. Last edited by PEKKA, Sep 1, 2024, 6:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gladIasked

648 posts

gladIasked

#48 h Mar 26, 2025, 8:18 PM

Y by

The answer is $\boxed{(n-1)^2}$ .

We can achieve this with the following construction ( $n=5$ case):
$[asy] size(5cm); // Default size based on your preference unitsize(1cm); for (int i = 0; i < 4; ++i) { for (int j = 1; j < 5; ++j) { draw(shift(i, j) * unitsquare); label("0", (i+0.5, j+0.5), fontsize(10pt)); } } for (int i = 4; i < 5; ++i) { for (int j = 1; j < 5; ++j) { draw(shift(i, j) * unitsquare); label("1", (i+0.5, j+0.5), fontsize(10pt)); } } for (int i = 0; i < 4; ++i) { for (int j = 0; j < 1; ++j) { draw(shift(i, j) * unitsquare); label("-1", (i+0.5, j+0.5), fontsize(10pt)); } } draw(shift(4, 0) * unitsquare); label("1434", (4+0.5, 0.5), fontsize(10pt)); [/asy]$
Clearly, all sixteen of the $0$ 's satisfy the problem's conditions.

Note that there must be exactly one number in each row that is the largest in the row. Similarly, there must be exactly one number in each column that is the smallest in the column. Also, let there be $x$ numbers that are the largest in their row and the smallest in their column. Thus, we must have at least $2n-x$ numbers (cells) that don't satisfy the problem's conditions.

It's easy to see that $x\le 1$ ; if $x>1$ , then we can choose two such numbers $a$ and $b$ that are the largest in their row and the smallest in their column. Let $c$ be the number in $a$ 's column and $b$ 's row, and let $d$ be the number in $a$ 's row and $b$ 's column. Note that $a<c$ , $a>d$ , $b>c$ , and $b<d$ . These inequalities tell us that $a>b$ and $a<b$ simultaneously, a contradiction. Therefore, $x\le 1\implies 2n-x\ge 2n-1$ .

Our upper bound on the number of cells satisfying the problem's conditions is clearly $n^2-(2n-1)=(n-1)^2$ , so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

akliu

1795 posts

akliu

#49 h Apr 2, 2025, 5:24 PM

Y by

In every row, there exists at least one number that is greater than the row average. Similarly, in every column, there exists at least one number that is less than the column average. Therefore, there exist at least $2n-1$ tiles that violate the conditions of the grid, giving us a bound of $c \leq (n-1)^2$ . This is attainable; consider a grid in which the cells in the bottom row have value $-1$ , the cells in the right column have value $1$ , and the cell on the bottom right has value $0$ .

Z K Y