Arranging apples in an array
Given positive integers m and n together with integer sequences \(a=(a_ 1,a_ 2,...,a_ m)\) and \(b=(b_ 1,b_ 2,...,b_ n)\) satisfying \(0<a_ i<n\), \(0<b_ j<m\) for all i and j, and \(\sum a_ i=\sum b_ j,\) the problem is to find an \(m\times n\) matrix of zeros and ones such that \(\sum_{j}x_{ij}=a_ i\) and \(\sum_{i}x_{ij}=b_ j\) for all i and j. This is a well solved problem. This paper provides an overview and a synthesis of earlier results. A greedy algorithm developed from Ford-Fulkerson's approach is considered in depth. A new and simple proof of its correctness is presented. Finally a series of open questions is posed as suggestions for future research.
scientific article; zbMATH DE number 4085667
scientific article