2
$\begingroup$

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers.

Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and zeros("0") where the number of ones("1") in row $i$ is $\forall i $ : $a_i$ and in column $j$ is $\forall j$ : $b_j$

Any hint is greatly appreciated.

$\endgroup$
3
  • $\begingroup$ If I understood, correctly, obviously not. Just let $m=2=n, a_1=3$. The number of $1$'s in row $1$ is supposed to be $3$, but the matrix is $2\times 2$, there isn't enough room in one row for three $1$'s. $\endgroup$
    – Git Gud
    Apr 16, 2014 at 12:32
  • $\begingroup$ Oh, wait, no sorry. The sequences are given. Updating question. $\endgroup$
    – Wanderer
    Apr 16, 2014 at 12:36
  • $\begingroup$ The problem still stands. We are given $(3,0)$ and $(0,0)$. The the number of $1$'s in row $1$ of a $2\times 2$ matrix is supposed to be $3$. $\endgroup$
    – Git Gud
    Apr 16, 2014 at 12:39

1 Answer 1

3
$\begingroup$

The answer to this innocent-looking problem is a well-known and nontrivial result in combinatorics, the Gale-Ryser theorem (see, for example, http://compalg.inf.elte.hu/~tony/Kutatas/EGHH/Gale-Ryser-Krause-1966.pdf).

$\endgroup$
7
  • $\begingroup$ That result isn't the same statement as the question. $\endgroup$
    – Git Gud
    Apr 16, 2014 at 12:42
  • $\begingroup$ Then I am missing something. $\endgroup$ Apr 16, 2014 at 12:46
  • $\begingroup$ The given sequences, in the paper, must sum up to certain constants. This restriction isn't imposed in the question. $\endgroup$
    – Git Gud
    Apr 16, 2014 at 12:47
  • 1
    $\begingroup$ If they don't sum up to the same constant, then the answer is somewhat trivially no, because the sums of both sequences will be the total number of $1$'s in the matrix. $\endgroup$ Apr 16, 2014 at 12:49
  • 1
    $\begingroup$ Another source is Ryser's book, Combinatorial Mathematics. It's in the MAA Carus Monograph series. $\endgroup$ Apr 16, 2014 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.