Pigeonhole in a Matrix
Both the problem and its solution were proposed by Professor McWorter. This problem reminds one of the #6 where we showed that a 2×2 submatrix exists that consists entirely of either 0's or 1's. We can't say in advance which it's going to be. Removal of the ambiguity makes the problem that much more difficult.
Let ai, i = 1, ..., 14, be the number of pairs of rows with 1's in the i-th column of A. Let P be the sum of the ai, i = 1, ..., 14. For example, suppose A is
1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1
Then a1 = 3(3 - 1)/2 = 3 because the first column has three 1's and so there are
If P is greater than the number of pairs of rows of A, which is
If any column, say the ith, of A has m 1's and some other column, say the jth, of A, has
Dividing the 58 1's as evenly as possible among the 14 columns of A, we get 12 columns with four 1's and 2 columns with five 1's
I don't know if this argument always gives the best possible result, but here is some evidence in support of this claim. Let A be the incidence matrix for a projective plane of order k. Then A is
#20 is almost the same kind as the problem at hand. It could have been phrased
If an 11 by 10 matrix A contains 40 1's, then some 2 by 2 submatrix of A consists of all 1's.
The only differences are that #20 involves a nonsquare matrix and assumes the columns of A are all different but have the same number of 1's. For both problems, though, it is irrelevant what the non-1 entries are, and so could be any matrix with enough 1's.
In this context, the 40 could be replaced by 39, or one 3-subset and 9 4-subsets.
I had been toying with the idea of posing to alt.math.recreational the problem of placing 25 checkers on a checkerboard so that no four would be the vertices of a rectangle with sides parallel to the sides of the checkerboard. The proof says that 26 checkers on a checkerboard gurantees four checkers as corners of a rectangle with sides parallel to the sides of the checkerboard. However, I could not place 25 checkers without forming the corners of a rectangle.
Then I noticed that a refinement of the argument shows that any 25 checkers on the checkerboard forces four of the checkers to be corners of a rectangle. For, if 25 checkers are on the board, then some row has at exactly four checkers; any more would guarantee the existence of four checkers which are corners of a rectangle. This determines four columns and seven rows that can contain at most seven checkers if no four checkers form the corners of a rectangle. But then there are four columns and seven rows which must contain at least 25-4-7=14 checkers. These 14 checkers determine at least seven pairs of columns, one more than six pairs of the four columns. Hence 25 checkers on a checkerboard must contain four which are corners of a rectangle with sides parallel to the sides of the checkerboard.
This raises the question, can 24 checkers be placed on the checkerboard so that no four form the corners of a rectangle with sides parallel to the sides of the checkerboard? The answer is yes. An example is below with 1 equal a checker.
1 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1
So, my proof is not best possible despite my protestations to the contrary.
Professor McWorter also noticed that the problem admits the following reformulation: Let G be a graph with 14 vertices and 29 edges. Show that G contains a 4-cycle.