scientific article; zbMATH DE number 1496423
The results in this paper are motivated by the following betting problem. The National Football League consists of 31 teams, each of which plays 16 games during a 17-week season. For each team, there is one week in which it does not play. Every week the teams are assigned to a group of 31 gamblers, each gambler betting on the team assigned to him. The gambles require that no team is assigned to the same gambler more than once and furthermore no gambler wishes to be assigned more than once to a team that does not play in that week. The question is whether an assignment that satisfies the first condition but not the second, can be changed to one that satisfies both conditions by reordering the teams. An entry in row \(i\) and column \(j\) of a matrix \(M\) with \(m\) rows is said to be on the \(k\)th extended diagonal if \(i-j+ 1\equiv k\pmod m\). The main result, in matrix terminology, is the following theorem: Let \(M\) be an \(m\times n\) 0-1 matrix with one 1 in each row. There is a permutation of the rows that yields a matrix with one 1 in each extended diagonal if and only if the sum of the original column numbers of the ones is congruent to \(0\pmod m\). The result is a special case of a theorem due to \textit{M. Hall jun.} [A combinatorial problem on Abelian groups, Proc. Am. Math. Soc. 3, 584-587 (1952; Zbl 0047.02701)].
- Extending subpermutation matrices in regular classes of matrices
- Extending partial tournaments
- scientific article; zbMATH DE number 5016698
- Some (0,1)-matrices enumerative problems
- Representing integers in the binary number system as permanents of certain matrices
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Permutation matrices related to Sudoku
- Zero-one matrices without consecutive ones
- Patterns that allow given row and column sums
- Matrices all of whose principal submatrices of some order have a nonzero permanent
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500618)
