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.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

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

What if applet does not run?

An investigation

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 N + 1. Indeed no sum could be greater than N. So the best we may expect to do is to get the sums 0, 1, ..., N-1, N, and there are N + 1 of them.

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

filling a rect array with 0s and 1s - and counting

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

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 N = M, the complement of an optimal distribution is also optimal.

71545309