Filling an Array with 0s and 1s - and CountingThe 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.
 |Contact| |Front page| |Contents| |Algebra| |Store| Copyright © 1996-2012 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?
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| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 41143663 |
