Let m and n be positive integers. Let a₁,...,a_m, b₁,...,b_n be positive integers such that a₁+...+a_m = b₁+...+b_n. Show that there exists an mxn matrix, containing only zeros and ones, such that

the sum of the entries in row i is a_i
the sum of the entries in column j is b_j

(this is similar to exercise 21.5 on page 366).

Sorry! This statement is false. For example, taking a=b=(5,1), there is no 2x2 matrix containing only zeros and ones such that the sum of the entries in the first row and column is 5 and the sum of the entries in the second row and column is 1.

Consider the following sets:
S₁ = {a,c,d}, S₂ = {b,e,f}, S₃ = {c,h}, S₄ = {d,h}, S₅ = {e,g}, S₆ = {f}, S₇ = {a,b}
It is desired to find a system of distinct representatives (that is to pick 7 distinct elements from the 7 sets). The constructive "marriage algorithm" can be adopted to this purpose. Suppose that it is being used, and that it starts out by picking a from S₁, b from S₂, c from S₃, d from S₄, e from S₅, and f from S₆. Show how the algorithm would finish up the job.

Suppose that the constructive marriage algorithm is used in an attempt to marry b "boys" to g "girls", but that it is impossible to do so. How will this failure manifest itself during the execution of the algorithm? What information does the algorithm provide at the moment when it becomes evident that it is not possible to marry all of the boys?