Once more the bichrome 3 x 7 grid (See EWD764)

Once more the bichrome 3x7 grid (See EWD764)

This note deals with a minor observation, just big enough to be recorded. It compares three counting arguments. PPP refers to the Purified Pigeonhole Principle, which states that for a finite, non-empty bag of numbers the maximum is at least the average.

Consider a rectangular array of 7 rows, each consisting of 3 grid points, each of which is red or blue. The problem is to show the presence of a rectangle the 4 corners of which have the same colour.

Argument A

• since there are 3 columns and 2 colours, (PPP) each row has at least 2 points of the same colour; call that colour the dominant colour of that row;

since there are 7 rows and 2 colours, (PPP) at least 4 rows have the same dominant colour; call that the majority colour

• select for each of these 4 rows a pair of columns in what that row has grid points of the majority colour; since there are 4 of these rows and 3 pairs of columns, (PPP) for at least 2 rows the same pair of columns has been selected, and the conclusion follows.

Argument B

• since there are 3 columns and 2 colours, (PPP) we can select for each row a pair of columns in which that row has grid points of the same colour; call that pair of columns the equality pair of that row;

• since there are 7 rows and 3 pairs of columns, (PPP) at least 3 rows have the same equality pair; call that the target pair

• since these 3 rows are each monochrome in the target pair and there are 2 colours, (PPP) there are at least 2 such rows that have the same colour in the target pair, and the conclusion follows.

Argument C

• since there are 3 columns and 2 colours, (PPP) we can select for each row a pattern, i.e. a combination of a pair of columns and a colour, such that that row has in those columns grid points of that colour;
• since there are 2 colours and 3 pairs of columns, there are $6\left( { = 2 \times 3}\right)$ patterns; since there are 7 rows and 6 patterns, (PPP) there are at least 2 rows with the same pattern, and the conclusion follows.

The observation to be made is that argument C is better than arguments A and B, which both refer

to PPP once more than C. The only difference between A and B is that, in the last two appeals to PPP, A averages first over 2 and then over 3 , whereas B does that the other way round. Argument C com- bines these two appeals by averaging over 6 , thus, firstly, avoiding the choice of that irrelevant order, and, secondly, avoiding the additional no- menclature introduced to describe what is counted in the intermediate stage.

Note that the "patterns" - with their implicit Cartesian product- are very similar to the U.D. "labels" from the argument about maximum up/down sequence lengths as presented in EWD980.

Acknowledgement I am indebted to the students following my current course on Mathematical Methods. They provided all three above arguments.

Austin, 6 February 1989

prof. dr. Edsger W. Dykstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA