# Pigeonhole in a Matrix

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander BogomolnyBoth 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 a_{i}, 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 a_{i}, 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 a_{1} = 3(3 - 1)/2 = 3 because the first column has three 1's and so there are _{2} = 2(2 - 1)/2 = 1,_{3} = 1,_{4} = 1,_{5} = 3.

If P is greater than the number of pairs of rows of A, which is

If any column, say the i^{th}, of A has m 1's and some other column, say the j^{th}, of A, has
^{th} column to the j^{th} reduces a_{i} by _{j} by n. Hence this move reduces P. Therefore, the smallest value P can have is that obtained by a matrix whose columns have numbers of 1's as nearly equal as possible. Call this least value L. We show that

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

### Note

#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.

### Remark

Alexander:

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.

### Note

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.

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny