Arrangement of numbers in a grid I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) &gt; 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P[i]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=[3, 1, 2]$ and $M=$

2 6 7
3 4 8 
1 5 9


According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$.
Observe that there are 5 pairs in the Cartesian product $\{2,6,7\}\times\{1,5,9\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?
Here are some ideas for you to start thinking.

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).

More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L_m$ for all $m$, and $3 \in L_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L_m$ (why?).

It remains to determine $L_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.