To find the maximum number of distinct integers in a grid for given conditions.

Question

Problem:

Consider a $n × n$ square grid made up of $n^2$ small boxes. Each Column and row of this grid can contain upto a maximum of $m$ ($m <n$) distinct integers only. What is the maximum number of distinct integers that can be fitted in this grid so that no boxes remain empty?

What I have already tried:

I thought to start by putting distinct integers in the main diagonal. By this, we have filled $n$ boxes

Now, I put ($n-1$) distinct integers in the nearest and parallel diagonals to the main diagonal on either side. Thus, till now, I have filled $n+ 2(n-1)= (3n-2$) integers. We repeat this process of filling parallel and adjacent diagonals until each row and column( except the top and bottom row which have one less element than others) is filled with ($m-1$) distinct integers.

Now, I am stuck after this because I think it is more complicated than what I have learnt because I don't even know if this approach ensures that number of filled boxes get maximised or not.

P.S.: I have learnt till only basics of permutations and combinations so that might be the reason that I could not solve it. Although, I welcome all answers )

Thanks!

Answer 1

The best case for when $n \ge 2m-1$ or $(n-(m-1)) | n$ has $n(m-1) + k$ distinct integers, where$k=\max\left\{d : d|n \land d\le \frac{n}{n-(m-1)}\right\}$ . The construction works for all $n>m$ cases, but I don't have the proof for all cases. Please edit/comment them out if you get them.

Here is the construction for the $k=1$ case :$$\left[\begin{matrix}\#_1 & \#_2 & \#_3 & \dots & \#_{m-2} & \#_{m-1} & \$ & \$ & \$ & \dots &\$& \$ \\ \$ & \#_1 & \#_2 & \#_3 & \dots & \#_{m-2} & \#_{m-1} &\$&\$&\dots &\$& \$ \\ \$ &\$& \#_1 & \#_2 & \#_3 & \dots & \#_{m-2} & \#_{m-1} &\$ &\dots &\$& \$ \\\ddots& \ddots& \ddots& \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots& \ddots\\\$&\$&\$& \dots &\$&\$& \#_1 & \#_2 & \#_3 & \dots & \#_{m-2} & \#_{m-1}\\ \#_{m-1} &\$&\$& \dots &\$&\$&\$& \#_1 & \#_2 & \dots & \#_{m-3} & \#_{m-2}\\ \#_{m-2} & \#_{m-1} &\$& \dots &\$&\$&\$&\$& \#_1 & \dots & \#_{m-4} & \#_{m-3}\\\ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots\\ \#_2 & \#_3 & \dots & \#_{m-2} & \#_{m-1} & \$ &\$&\$& \dots &\$&\$& \#_1 \end{matrix}\right]$$

Here all $\#$'s are distinct integers (no two $\#$ in the matrix are equal), and $\$$ is a single integer different from all $\#$'s (all $\$$ in the matrix are equal, but no $\#$ and $\$$ are equal). So total number of distinct integers = $n(m-1)+1$.

Formally, let the $t^{th}$ diagonal $d_t$ of the matrix be all the cells $\{a_{i,j} | j-i \equiv t-1 \pmod n \}$, then the union of diagonals $d_1, d_2, \dots d_{m-1}$ can be filled with all distinct integers (like $\{1,2,3,\dots n(m-1)\}$), and the union of diagonals $d_m, d_{m+1}, \dots d_n$ should be filled by a single integer (like $n(m-1)+1$).

For $k>1$ case the construction is mostly similar, but the $\$$ diagonals have to be intermixed with the $\#$ diagonals. Specifically $d_k, d_{2k}, d_{3k} \dots d_{(n-(m-1))k}$ diagonals will be $\$$ diagonals. There is no change in property of $\#$'s, they are still all distinct. But now $\$$'s can be $k$ distinct integers, $\$_1, \$_2, \dots \$_k$, and for any $\$_t$ it will be placed at all $\$$ diagonals, $a_{i,j}$ cells which have the property $\{a_{i,j} | i \equiv t+1 \pmod k \}$.

Here is a matrix with this construction for $n=6, m=4$ where $\$$ numbers are $19$ and $20$.

$$\left[\begin{matrix} 1 & 19 & 7 & 19 & 13 & 19 \\ 20 & 2 & 20 & 8 & 20 & 14 \\ 15 & 19 & 3 & 19 & 9 & 19 \\ 20 & 16 & 20 & 4 & 20 & 10 \\ 11 & 19 & 17 & 19 & 5 & 19 \\ 20 & 12 & 20 & 18 & 20 & 6 \end{matrix}\right]$$

And another matrix with this construction for $n=6, m=5$ where $\$$ numbers are $25, 26$ and $27$. $$\left[\begin{matrix} 1 & 7 & 25 & 13 & 19 & 25 \\ 26 & 2 & 8 & 26 & 14 & 20 \\ 21 & 27 & 3 & 9 & 27 & 15 \\ 16 & 22 & 25 & 4 & 10 & 25 \\ 26 & 17 & 23 & 26 & 5 & 11 \\ 12 & 27 & 18 & 24 & 27 & 6 \end{matrix}\right]$$

---

The proof of this is by contradiction below. Also in the proof, I will be using some graph terminology, so I'll provide some short explanations for them here

• A graph $G$ is a collection of $N$ nodes (think of them as points), and $E$ edges where an edge is a connection between two nodes $(n_1, n_2)$ (think of them as lines between those points) : https://en.wikipedia.org/wiki/Graph_theory#Definitions

• A path $p$ is some ordered list of distinct nodes $[n_1, n_2, \dots n_k] : k \ge 1$, where for each $i : 1\le i \le k-1$, nodes $n_i$ and $n_{i+1}$ have an edge between them : https://en.wikipedia.org/wiki/Path_(graph_theory)

• A $\textbf{connected}$ graph is a graph $G$ where for any two nodes $n_x$ and $n_y$ in $G$, they have a path between them, i.e., there are some nodes $n_1, n_2, \dots n_k : k \ge 0$ such that $[n_x, n_1, n_2, \dots n_k, n_y]$ is a valid path : https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

Proof :

Let the maximum number of distinct integers be $ M > n(m-1) + k$, where $k=\max\left\{d : d|n \land d\le \frac{n}{n-(m-1)}\right\}$. Also lets define a graph $G$ with $n$ indexed nodes (each corresponding to a row in our matrix), and with edges $\{(x,y) : \text{row}_x \text{ and } \text{row}_y \text{ have a common integer between them}\}$

Now I show that if this graph $G$ is connected, then the maximum number of distinct integers the matrix can have is $n(m-1)+1$ using induction :

• for $n=1$ : the graph contains a single row, which can have a maximum of $m-1+1 = m$ distinct integers.
• for $n + 1 \ge 2$ from $n$ :
  • for a connected graph with $ \ge 2$ nodes, we can always find a node $x$, such that, removing this node and all its' adjacent edges from the graph results in a connected graph (with $1$ less node).
  • The corresponding rows of this graph with $n$ nodes, will have a maximum of $n(m-1)+1$ distinct integers from Induction Hypothesis.
  • Now connecting the node $x$ and its' edges back to the graph, it will have at least one edge to some node $y$ in the reduced graph (because the original graph was connected).
  • This means row $x$ and row $y$ have at least one common integer between them, and hence row $x$ can add a maximum of $m-1$ distinct integers to the total $n(m-1)+1$.
  • Total number of distinct integers $\le n(m-1)+1 + (m-1) = (n+1)(m-1) + 1$, proving the induction.

So graph $G \textbf{ must be disconnected}$, or in other words, graph $G$ must have at least two disjoint connected components $G_1$ and $G_2$, where the number of nodes in both components $|G_1|, |G_2| > 0$. In our case, $\textbf{the number of connected components must be } > k$; because if there are only $t \le k$ connected components, $G_1, G_2, \dots G_t$, then any $G_i$ connected graph has $ \le |G_i|(m-1)+1$ number of distinct integers. Then the total number of distinct integers : $$\le \sum_{i=1}^t (|G_i|(m-1)+1) = (m-1)\sum_{i=1}^t|G_i| + \sum_{i=1}^t1 = n(m-1)+t < M$$

Now we have at least $k+1$ disjoint components , $G_1, G_2, \dots G_{k+1}$ :

• Lets take node $x_1$ from $G_1$, node $x_2$ from $G_2$ and so on until node $x_{k+1}$ from $G_{k+1}$. As any two of these nodes do not have an edge between them (they belong to different connected components), row $x_1$, row $x_2$ and so on until row $x_{k+1}$ will not have any common integer between them.
• From this we can say, that for each column $y$ of the matrix, it will have only a maximum of $m-(k+1)$ distinct integers, except the ${k+1}$ numbers which lie at the intersection of row $x_1$ and column $y$, row $x_2$ and column $y$ and so on.
• So the total number of distinct integers in the matrix $=$ extra distinct integers from each column $+$ maximum number of distinct integers in row $x_1$ $+$ maximum number of distinct integers in row $x_2 + \dots$ $$\begin{align}\le \sum_{y=1}^{n}(m-(k+1)) + \sum_{i=1}^{k+1}m &= n(m-(k+1)) + (k+1)m \\ &= n(m-1) - kn + km -k + k + m \\ &= n(m-1) -k(n-(m-1)) + m + k \end{align}$$

Now we can take three cases:

• Case 1 : $n \ge 2m-1$ : Here $k\le\frac{n}{n-(m-1)} < 2$, so $k = 1$. Also the maximum number of integers here are $\le n(m-1) -k(n-(m-1)) + m + k = n(m-1)-n+2m \le n(m-1) + 1$
• Case 2 : $(n-(m-1)) | n$ : Here $k = \frac{n}{n-(m-1)}$, so the maximum number of integers here are $\le n(m-1) -k(n-(m-1)) + m + k = n(m-1)-n+m+k \le n(m-1) + k$

Both of these cases violates $M > n(m-1) + k$. Hence the maximum number of distinct numbers is $n(m-1) + k$, where $k=\max\left\{d : d|n \land d\le \frac{n}{n-(m-1)}\right\}$.

Answer 2

Here's a solution with $49$ distinct values, obtained via integer linear programming:

\begin{matrix}&1&11&1&1&1&1&1&1&1&1&1&1&27&12&1&1\\&1&25&1&1&1&1&1&1&8&1&10&1&1&1&1&1\\&44&42&1&1& 1&1&1&1&1&1&1&1&24&1&1&1\\&19&1&1&1&36&1&1&9&1&1&1&1&1&1&1&1\\&1&1&6&1&1&1&5&1&17&1&1&1&1&1&1&1\\& 1&1&46&1&1&28&1&1&1&1&1&1&1&47&1&1\\&1&1&13&1&1&1&1&1&1&1&1&1&1&41&26&1\\&1&1&1&1&1&1&1&1&1&1&22&1 &1&1&15&3\\&1&1&1&31&1&4&1&1&1&1&1&45&1&1&1&1\\&40&1&1&1&1&1&16&1&1&1&1&1&1&1&1&38\\&1&1&1&21&30&1 &1&14&1&1&1&1&1&1&1&1\\&1&1&1&1&1&1&1&1&1&33&1&1&1&1&32&2\\&1&1&1&1&35&1&1&1&1&37&1&43&1&1&1&1\\&1 &1&1&1&1&29&1&1&1&1&39&1&7&1&1&1\\&1&1&1&48&1&1&1&34&18&1&1&1&1&1&1&1\\&1&1&1&1&1&1&20&1&1&49&1&23 &1&1&1&1\\\end{matrix}