Let $\bf R$ be an $m \times m$ matrix with non-negative integer elements $r_{i,j}$, $0\leq r_{i,j} \leq n$ and $n=km$ (k is a positive integer), with the property $\sum_ir_{i,j}=\sum_jr_{i,j}=n$, i.e., every column and every row of $\bf R$ sums to $n$. I am interested in a lower bound for the following.
$$\underset{{\bf \Pi}} {\max} \underset{i \in [m]}{\min}\ \left( {\bf R} {\bf \Pi} \right)_{ii} $$
where $\bf \Pi$ is a permutation matrix and $[m] := \{1, 2, \dots, m\}$. In other words, a lower bound for the smallest diagonal value of ${\bf R \Pi}^*$, where
$$ {\bf \Pi}^* := \underset{{\bf \Pi}} {\operatorname{argmax}} \underset{i \in [m]}{\min} \left( {\bf R} {\bf \Pi} \right)_{ii} $$
In particular, I want to show that $n\,/\,m$ is a lower bound for all matrices $\bf R$ (for $m = 2$ this is easy to show by covering all possibilities). The coupling of the columns and the rows seems to make it, however, very tedious in arbitrary dimensions $m$, and I haven't been able to construct a counter example either.
Any hints, on a strategy to show this would be highly appreciated.
Edit: The problem above is related to the following problem:
Suppose you have an $n\times m$ matrix $\bf Y$, where every row of $\bf Y$ is a permutation of [m], meaning $$\bf Y = \begin{pmatrix}\pi_1([m])\\\pi_2([m])\\\vdots\\\pi_n([m])\end{pmatrix},$$ where $\pi_i$ is some permutation of $[m]$ and $i = 1,\dots,n$. Let the columns of $\bf Y $ be denoted as ${\bf y}_j,\:j = 1,\dots,m$. Suppose $n = km$, where k is a positive integer. Take for example the values $k = 2$ and $m=4$ with some corresponding matrix $$\bf Y = \begin{pmatrix} 1&2&3&4\\ 3&2&1&4\\ 4&2&1&3\\ 1&4&3&2\\ 2&1&3&4\\ 1&3&4&2\\ 2&4&3&1\\ 3&4&2&1\\ \end{pmatrix}.$$
If we were to select only one type of digit for every column of $\bf Y$, such that every digit has been selected exactly once (e.g., if I have selected 3 in ${\bf y}_1$ I cannot select it in another ${\bf y}_j,\:j\neq1$), is there a selection such that every digit appears in its respective column at least $k$ times.
My hypothesis is that it is, since for $k=1$ it is trivial to see that every digit has to appear at least once. I am not sure if I can argue that since it holds for one "elementary block" of size $m \times m$ it holds for all integers $k$ (via induction).
For visualization I have marked two possible selections in the example from above
$$\begin{pmatrix} 1&{\bf 2}&3&{\bf 4}\\ {\bf 3}&{\bf 2}&{\bf 1}&{\bf 4}\\ 4&{\bf 2}&{\bf 1}&3\\ 1&4&3&2\\ 2&1&3&{\bf 4}\\ 1&3&4&2\\ 2&4&3&1\\ {\bf 3}&4&2&1\\ \end{pmatrix}\quad\text{or}\quad \begin{pmatrix} {\bf 1}&2&{\bf 3}&4\\ 3&2&1&4\\ 4&2&1&3\\ {\bf 1}&{\bf 4}&{\bf 3}&{\bf 2}\\ 2&1&{\bf 3}&4\\ {\bf 1}&3&4&{\bf 2}\\ 2&{\bf 4}&{\bf 3}&1\\ 3&{\bf 4}&2&1\\ \end{pmatrix}$$
Of course, there could be other selections. The values of the elements in $\bf R$ are then the numbers of occurrence of each digit in every column of $\bf Y$.
The problem can be written as
\begin{align} \max_{t,\, \mathbf \Pi} \;& t\\ \text{subject to: }&& \sum_{j=1}^m \mathbf \Pi_{i,j}\mathbf R_{j,i} - t&\ge 0,&&\forall i=1,\ldots,m\\ &&\sum_{j=1}^n\mathbf \Pi_{i,j} &=1,&&\forall i=1,\ldots,m\\ &&\sum_{i=1}^n\mathbf \Pi_{i,j} &=1,&&\forall j=1,\ldots,m\\ &&\mathbf \Pi_{i,j} &\ge 0,&&\forall i,j=1,\ldots,m\\ \end{align}
By duality it is equivalent to:
\begin{align} \min_{\lambda,\, \mu,\, \delta} \;& \sum_{i=1}^m \lambda_i + \sum_{j=1}^m \delta_j\\ \text{subject to: }&& \lambda_i + \delta_j - \mathbf R_{j,i}\mu_{i} &\ge 0,&&\forall i,j=1,\ldots,m\\ && \sum_{i=1}^m \mu_i &=1\\ && \mu_i &\ge 0 &&\forall i=1,\ldots,m \end{align}
From the last it is not hard to prove your lower bound.