The answer is $9900$ , right? So like $n^2-n$ @below , wow, that's so cool ... i spent so much time trying to prove 9900 lol

a_n wrote: The answer is $9900$ , right? So like $n^2-n$ I'm getting zero on this now.

The answer is \(100^2-4\), achieved by generalizing the following construction: \[ \begin{bmatrix} 1&2&3&4&5\\ 3&1&2&4&5\\ 2&3&1&4&5\\ 4&4&4&\color{red}5&\color{red}6\\ 6&6&6&\color{red}6&\color{red}5 \end{bmatrix} . \] Now we prove that this is maximal. If some color appears at most 98 times, then we may find two rows and two columns without this color, so we may find four non-diverse squares. Henceforth all colors appear at least 99 times, so we may assume without loss of generality the colors, 1, 2, \ldots, 100, 101 each appear 99, 99, \ldots, 99, 100 times. For each \(k=1,\ldots,100\), select a color \(c_k\) that does not appear in row \(k\), and let \(x_k\) be the number of columns containing \(c_k\). If \(x_k\ne100\) for all \(k\), there is a non-diverse square in every row, so at least 100 non-diverse squares. Otherwise \(x_k=100\) for some \(k\), implying \(c_k=101\). Thus the color 101 does not appear in every row, so repeating the argument with columns instead of rows gives the required bound.

I'm not quite sure how the coloring works. Could someone formalize it into what $a_{ij}$ is?

guessed $9801$

Only the proof of the bound: We claim that atleast 4 non-diverse cell must be there in the grid. Name the rows $R_1,R_2\dots,R_{100}$.Similarly the columns $C_1,C_2,\dots,C_{100}$.Call $C_i\cup R_j$ the $(i,j)$-th collection.A collection is said to be diverse if it contains $\{1,2,\dots,101\}$.Otherwise call it non-diverse. Claim:At least one of the following situation holds. For any $i\in\{1,2,\dots,100\}$ there is a $j\in\{1,2,\dots,100\} $ such that $C_i\cup C_j$ is a non-divetse collection. There exists $b\in \{1,2,\dots,n+1\}$ such that $b$ belongs to every row. Proof.Suppose the first situation does not hold.This means there is a column say $C_i$ such that $C_i\cup R_j$ is diverse for all $j=1,2,\dots ,100$. Take any row,say $R_k$.Let this row contains $m$ distinct colours say $\{1,2,\dots,m\}$.Since $C_i\cup R_k$ is diverse so$$m+1,m+2,\dots,101\in C_i$$. Let $C_i=\{m+1,m+2,\dots,101\}\cup\{a_1,a_2\dots,a_s\}$. Where $\{a_1,a_2\dots,a_s\}\subseteq\{1,2,...,m\}$. Since for all $j$ we have $C_i\cup R_j$ A diverse collection hence all row contains $$L=\{1,2,...,m\}-\{a_1,a_2,...,a_s\}$$. It is easy to see that $L $ is a non-null set since atleast one element is missing from $C_i$. $\blacksquare$ If the first situation holds we get $n$ non-diverse collection.(1 non-diverse collection per column).If the 1st situation does not hold we then get a colour,say $b$, which appears in every row. Applying the claim for the row and assuming first situation does not holds for rows, we also have a colour ,say $m$ which appears in each column. If $m\neq b$ then there is at most $100^2-100-100$ cells where colour $m,b$ does not appear.And there is 99 remaining colours.By php one of this 99 colours appears At most 98 times.So this colour does not appear in at least 2 rows and 2 columns.Hence 4 of their intersections are non-diverse. Otherwise assume that $b=m$.So there is there is one number which appears in each roe and each columns.So the number of remaining cells where the other colour appear is atmost 9900.We have 100 remaining colours.By php one colour appears atmost 99 times.If one colour appears atmost 98 times then we are done by the previous stanza.Otherwise each of the remaining colours appears exactly 99 times. But in this case take any row and a colour missing in it.Since this colour is 99 times in the board there is a column also from where it is missing.So for each row we get a column such that the union of this row and column forms a non-diverse collection.So in this case we get a 100 non-diverse collection.[1 collection per row]. Hence in all the cases we get atleast 4 non-diverse cells. $\blacksquare$

starchan wrote: I'm not quite sure how the coloring works. Could someone formalize it into what $a_{ij}$ is? Yep, someone please formalize the construction.

It's not that hard to generalize (I am talking about the construction of TheUltimate123) . If the colours are $1,2,...,n+1$, take colours $1,2,...,n-2$ and the upper left square $(n-2)$x$(n-2)$ and on each row cyclically permutate these colours, starting from $1,2,...,n-2$, then $2,3,...,n-2,1$, etc. The rest of the construction is the same as the one illustrated (take colour $n-1$ and colour the cells in the $(n-1)$-th row and column except their last two cells in colour $n-1$, and use colors $n, n+1$ to color the $n$-th row and column, except their last two cells, which are colored as shown)

Here's a possible way to generalize for $n\times n$. If $1 \leq i \leq n-2$ and $1 \leq j \leq n-2$, we define $a_{i, j} \in \{1, \dots, n-2\}$ so that \[a_{i, j} \equiv i + j \pmod{n-2}.\]This implies that rows $1$ to $n-2$ and columns $1$ to $n-2$ have all colors from $1$ to $n-2$. If $1 \leq i \leq n-2$, we define \[a_{i, n-1} = n-1,\]and if $1 \leq j \leq n-2$, we define \[a_{n-1, j} = n-1.\]If $1 \leq i \leq n-2$, we define \[a_{i, n} = n,\]and if $1 \leq j \leq n-2$, we define \[a_{n, j} = n+1.\] Lastly, we define $a_{n-1, n-1} = a_{n, n} = n$ and $a_{n-1, n} = a_{n, n-1} = n+1$.

Here's my solution : ) I claim that the answer is $100^2-4=9996$. $\underline{\textbf{\textit{Part I: Construction}}}$ Denote the colors by $1,2,3,...,101$. The construction is as follows: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & ... & ... & 101 & 3 & 1 \\ \hline 101 & 4 & 5 & 6 & 7 & ... & ... & 100 & 3 & 2 \\ \hline 100 & 101 & 4 & 5 & 6 & ... & ... & 99 & 3 & 3 \\ \hline 99 & 100 & 101 & 4 & 5 & ... & ... & 98 & 3 & 3 \\ \hline 98 & 99 & 100 & 101 & 4 & ... & ... & 97 & 3 & 3 \\ \hline ... & ... & ... & ... & ... & ... & ... & ... & ... & ... \\ \hline ... & ... & ... & ... & ... & ... & ... & ... & ... & ... \\ \hline 5 & 6 & 7 & 8 & 9 & ... & ... & 4 & 3 & 3 \\ \hline 2 & 2 & 2 & 2 & 2 & ... & ... & 2 & 1 & 3 \\ \hline 1 & 1 & 1 & 1 & 1 & ... & ... & 1 & 2 & 3 \\ \hline \end{tabular}In other words, the top-left $98\times98$ cells are colored $4$ to $101$ alternately, and the bottom-right $2\times2$ cells are colored as shown above. The rest of the cells in the bottom 2 rows are colored $2$ and $1$ respectively, while the rest of the cells in the rightmost 2 columns are colored $3$, except the top 2 cells in the rightmost column, which are colored $1$ and $2$ respectively. It is easy to check that in our construction, all cells except the bottom right $2\times2$ cells are diverse, hence there are a total of 9996 diverse cells. $\underline{\textbf{\textit{Part II: Upper bound}}}$ We prove that there are at least 4 non-diverse cells. For any cell, call the 199 cells in its row or column its neighborhood. Assume there are $n<4$ non-diverse cells. We divide into 2 cases. Case 1: There exists a color, say X, with only $\leq 98$ cells in that color. Then there are at least 2 rows and at least 2 columns without any cell of color X. Hence there are at least $2\times2=4$ cells without any cell of color X in its neighborhood, and hence at least 4 non-diverse cells. Case 2: All colors are used in at least $99$ cells. Due to size reasons, it must be the case that 100 of the colors are used 99 times, while 1 of the colors is used 100 times. Each of the 100 colors must be absent from at least 1 row and 1 column, hence each must be absent from 1 of the neighborhoods of the $n$ \textit{non-diverse} cells. Hence there exists a non-diverse cell whose neighborhood has $\geq \lceil \frac{100}{n} \rceil \geq 34$ colors absent, i.e. $\leq 66$ colors present. By pigeonhole again, among those 66 colors, there exists a color appearing $\geq \lceil \frac{199}{66} \rceil = 4$ times in that neighborhood, say color Y. If among those 4 monochromatic cells, at least 2 are in the same row, and at least 2 are in the same column, then similar to case 1, there must be at least 2 rows and at least 2 columns (within the entire grid) without any cell of color Y. Hence there are at least $2\times2=4$ cells without any cell of color Y in its neighborhood, and hence at least $4$ non-diverse cells. Otherwise, it must be that at least 3 cells of color Y are in the same row (or column, which is analogous). Then there must be at least 1 column, and at least 3 rows (within the entire grid) without any cell of color Y. This gives rise to 3 non-diverse cells, all in the same column, and since we assumed there are less than 4 non-diverse cells, these must be the only non-diverse cells in the entire grid. However, as noted in the beginning of case 2, each of the 100 colors must be absent in at least 1 of the neighborhoods of the 3 non-diverse cells. Hence, none of the 100 colors can be present in the column of the 3 non-diverse cells, so all cells of that column must be colored in the single remaining color. However, note that each cell of that column can now only contain at most 100 colors in its neighborhood, rendering them all non-diverse. Hence, this case leads to a contradiction as well. After considering all cases, we conclude that there must be at least 4 non-diverse cells, and hence at most 9996 diverse cells. So we are done. \(\blacksquare\) Comment: The main difficulty of the problem for me is to realize that the answer is 9996, since it is very easy, in my opinion, to fall into the belief that the answer is 9900. Upon finding the construction, however, the rest of the problem is hardly #3 difficulty.

(a small different) Case 1: There exists a color, say X, with only $\leq 98$ cells in that color. Then there are at least 2 rows and at least 2 columns without any cell of color X. Hence there are at least $2\times2=4$ cells without any cell of color X in its neighborhood, and hence at least 4 non-diverse cells. Case 2: All colors are used in at least $99$ cells. Due to size reasons, it must be the case that 100 of the colors are used 99 times (call $A_{1},....,A_{100}$), while 1 of the colors $(A_{101})$ is used 100 times. If have $\geq 4$ row don't have colour $A_{i}$ with $1 \leq i \leq 100$ we can choose 1 cell on it in a columns don't have that colour (so we have $\geq 4$ non-diverse cells) Otherwise we have $\geq 97$ row have colour $A_{1},....,A_{100}$ so don't have $A_{101}$. Similar column so we have $ \leq 3\times3=9$ cell colour $A_{101}$ (contradiction)

solved with CT17 The answer is $n^2-4$. For the construction, the idea is to first have a $n-2$ by $n-2$ sub-grid consisting of $n-2$ colors such that they are all exposed to each other and any additional cells are also exposed to all $n-2$ colors (e.g. having the first row contain all colors and each subsequent row being a cyclic shift) Then, we add a $1$ by $n-2$ rectangle to the right and down that are all the same color $n-1$. Then, we add another block of $1$ by $n-2$ consisting of color $n$ to the right, and a similar block of color $n+1$ down. This already makes the entire $n-2$ by $n-2$ good. Finally, colors $n$ and $n+1$ need to get exposed to each other, so we make the remaining four cells a checkerboard in $n$ and $n+1$. This makes the four $1$ by $n-2$ blocks good as well, and this achieves $n^2-4$. Now, assume for contradiction that at most 3 cells are bad. Then, note that if any color shows up at most $98$ times, then at least two rows and at least two columns do not have it at all. Their intersection (which is at least 4 cells) therefore must be bad. Thus, the color frequencies must be $99,99,99,\dots,99,100$. Now, the idea is, if a row does not have a color $C$, then "most of the time" every column has $C$, since otherwise we can isolate a bad cell from the column that does not have one. Call a row well-behaved if for any color it doesn't have, all columns have it. Since every row that is not well-behaved contains a bad cell, there is some well-behaved row. Say the well-behaved row does not have color $C$. Then, every column has $C$, so $C$ must be the 100 color. However, take any well-behaved column. Then, it has $C$, so it is missing some other color, so that other color appears in every row, but there is only one 100-color, contradiction. (picture of construction attached since the verbal description is very unaesthetic)