# Filling an Array with 0s and 1s - and Counting

The applet below serves an interactive tool to experiment with the following problem:

Fill an N×M array with 0s and 1s. Count the number of 1s in every row and in every column. How many distinct sums are there? What is the possible maximum of distinct sums?

(For the 10×19 matrix the problem has been offered at the 1993-1994 St. Petersburg Regional Mathematical Olympiad, Grade 10.)

Clicking on a number in the array changes 0 to 1 and vice versa. At the bottom of the applet, all distinct sums are collected into a set (note the curly braces) and the number of elements in the set (note the vertical bars) is shown on the right.

What if applet does not run? |

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Fill an N×M array with 0s and 1s. Count the number of 1s in every row and in every column. How many distinct sums are there? What is the possible maximum of distinct sums?

What if applet does not run? |

First, let's observe that neither row nor column sums change if we exchange a pair of rows or a pair of columns. One consequence of this remark is that placing the 1s in an orderly fashion does not cause any loss of generality.

Assume N ≥ M. Our second observation is that the maximum number of distinct sums could not exceed

One can get N + 1 distinct sums when N = M or N = M + 1 (the latter with

The maximum of N + 1 distinct sums is also attainable for N even and M ≥ N/2 + 1 or for N odd and

Two distributions of 0s and 1s are *complementary* if one is obtained from the other by replacing 0s with 1s and 1s with 0s. When

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71672651