Problem # 1

Solution #1 (by W.McWorter)

For n even, the matrix contains a diagonal of blocks of 2 by 2 permutation matrices. The 1's in these matrices make a complete matching. For n odd, the (n+1)/2 columns with odd indices together only contain 1's from the (n-1)/2 rows with even indices. Hence the marriage condition is violated because (n-1)/2<(n+1)/2. The n even case shows that a maximal matching with only one girl going unmarried exists for n odd.

Solution #2 (by W.McWorter)

The problem can also be solved by row and column changes. For n>0 even, interchange rows 2i-1 and 2i, for i=1,...,n/2. The main diagonal is now all 1's. For n>1 odd, do the same thing. Interchange rows 2i-1 and 2i, for i=1,...,(n-1)/2. You get the picture

1  0  1        	  0
0  1  0      . . .
      .   .      .
        .    .     
           .   .  0
            1  0  1
0  .  .  1  0  1  0
0  .  .     0  1  0

None of the 1's below the main diagonal correspond to a 1 in the last column, so no way for the algorithm to get a 1 to percolate (from under the G submatrix) into the lower right corner. Hence there is no complete matching.

Solution #3

We may apply induction. Depending on the parity of n induction starts either with n = 1 or 2. For the inductive step, match girls {1,2} with boys {1,2}. Remove the columns #1,2 and rows #1,2. What remains is a matrix of exactly the same kind (bidiagonal) with the order reduced by 2.

Solution #4

Apply Konig's Theorem: The minimal number of lines that could be drawn through all the 1s equals the maximal number of marriages that can be arranged. For a 3x3 matrix one only needs 2 lines - through 2nd column and row. By induction, as before, for a (2n+1)x(2n+1) matrix, it will take only 2n lines to cover all 1s.