Here is a fairly simple combinatorial problem that seems to have an important application. Maybe its generalizations deserve further study.
Let n be a positive integer, and r a positive divisor of n. An r-permutation matrix P of order n is a square (0,1)-matrix of order n with the following property: there is a subdivision of the row set I into a disjoint union of r-element blocks I_1, ... , I_{n/r}, and a similar subdivision of the column set J, such that the (i,j)-entry of P is equal to 1 if and only if i \in I_s, and j \in J_s (with the same s).
Thus P has exactly r units in each row or column; in particular, for r=1, we get precisely the permutation matrices.
Claim. Suppose n is a multiple of 6. If P_3 is a 3-permutation matrix, and P_2 a 2-permutation matrix of order n, then P_3 - P_2 has at least one positive entry and at least one negative entry.
Proof. The sum of all entries in P_3 - P_2 is equal to 3n - 2n = n, so at least one of them is positive.
Now the number of 2-blocks in P_2 is n/2, and the number of 3-blocks in P_3 is n/3 < n/2, implying that there exists a 2-block \{i,i'\} \subset I that is not contained in a 3-block. It follows that for some j \in J, both (i,j) and (i',j)-entries of P_2 are equal to 1, while one of these entries in P_3 (say the (i,j)-entry) is 0. Then the (i,j) entry in P_3 - P_2 is -1 < 0, finishing the proof.
Is there a natural generalization?
Let n be a positive integer, and r a positive divisor of n. An r-permutation matrix P of order n is a square (0,1)-matrix of order n with the following property: there is a subdivision of the row set I into a disjoint union of r-element blocks I_1, ... , I_{n/r}, and a similar subdivision of the column set J, such that the (i,j)-entry of P is equal to 1 if and only if i \in I_s, and j \in J_s (with the same s).
Thus P has exactly r units in each row or column; in particular, for r=1, we get precisely the permutation matrices.
Claim. Suppose n is a multiple of 6. If P_3 is a 3-permutation matrix, and P_2 a 2-permutation matrix of order n, then P_3 - P_2 has at least one positive entry and at least one negative entry.
Proof. The sum of all entries in P_3 - P_2 is equal to 3n - 2n = n, so at least one of them is positive.
Now the number of 2-blocks in P_2 is n/2, and the number of 3-blocks in P_3 is n/3 < n/2, implying that there exists a 2-block \{i,i'\} \subset I that is not contained in a 3-block. It follows that for some j \in J, both (i,j) and (i',j)-entries of P_2 are equal to 1, while one of these entries in P_3 (say the (i,j)-entry) is 0. Then the (i,j) entry in P_3 - P_2 is -1 < 0, finishing the proof.
Is there a natural generalization?
