Prove that no matter how each cell of a 5 x 41 table is filled with a 0 or 1, one can choose 3 rows and 3 columns which intersect in 9 cells filled with identical numbers.

Prove that 41 is the lowest possible n for 5 x n table; i.e., the statement is not true for a 5 x 40 table.

Source: Colorado math contest.

There are exactly 10 ways in which 3 columns can match from 5 rows:

1,2,3, 1,2,4, 1,2,5, 1,3,4, 1,3,5, 1,4,5, 2,3,4, 2,3,5, 2,4,5, 3,4,5,

There are 32 different arrangements of 0's and 1's in a row of 5; simple binary. Of these, two, 00000 and 11111 match in all 10 possible ways. A further ten, corresponding to decimal 2,4,8,15,16,23,27,29,30,31 match in 4 ways. Because of their numerous matches, these candidates can be discarded. Now we have two sets of ten left with 3 0's and 3 1's respectively. Together with their unique matching patterns these are:

03 0 0 0 1 1 1,2,3
05 0 0 1 0 1 1,2,4
06 0 0 1 1 0 1,2,5
09 0 1 0 0 1 1,3,4
10 0 1 0 1 0 1,3,5
12 0 1 1 0 0 1,4,5
17 1 0 0 0 1 2,3,4
18 1 0 0 1 0 2,3,5
20 1 0 1 0 0 2,4,5
24 1 1 0 0 0 3,4,5,
      
28 1 1 1 0 0 1,2,3
26 1 1 0 1 0 1,2,4
25 1 1 0 0 1 1,2,5
22 1 0 1 1 0 1,3,4,
21 1 0 1 0 1 1,3,5,
19 1 0 0 1 1 1,4,5,
14 0 1 1 1 0 2,3,4,
13 0 1 1 0 1 2,3,5,
11 0 1 0 1 1 2,4,5,
07 0 0 1 1 1 3,4,5,

Note that every matching pattern is used exactly once for 0 and once for 1 in this table. By repeating the table twice, we can obtain 40 rows without triplication. But however the 41st row is completed, since every available pattern has already been used twice, there will have to be a triplication.

As was to be shown.

Edited on November 30, 2015, 11:55 pm

Posted by broll on 2015-11-30 23:53:34