Force a collision without finding it

Try

With 13 people and 12 birth-month categories, at least two share a month. No distribution data are needed. The pigeonhole principle guarantees an occupied box without identifying which box it is.

Predict

Predict the bound for N objects in k≥1 boxes. Some box contains at least ceil(N/k) objects. If every box contained at most one less, the total capacity would be too small. A useful proof often depends more on designing the boxes than on doing arithmetic.

Experiment

Pair the integers 1 through 10 as (1,10),(2,9),…,(5,6). Selecting six distinct numbers must fill one pair twice, forcing a sum of 11. Select only the five smaller members to show that five selections do not guarantee such a pair.

Understand

Worked modular argument: among m+1 integers, two have the same remainder after division by positive m. Their difference is divisible by m. The boxes are remainders, not numerical intervals; negative integers still have unique least nonnegative remainders.

A stronger consecutive-sum application uses prefix sums S₀=0,S₁,…,Sₙ. Two of these n+1 values agree modulo n. Their difference is exactly a nonempty consecutive block of the original n integers, so that block sum is divisible by n. Including S₀ handles a block beginning at the first entry.

Invalid conclusion: the principle says every box has a collision. It guarantees at least one; other boxes can be empty.

Apply

For each proof, explicitly name objects, boxes and the rule assigning every object to one box. To show a threshold is sharp, give a counterexample just below it rather than only a proof above it.

Force a rectangle by remembering less of each row

Color a grid with two colors, written0 and1. A monochromatic rectangle means two distinct rows and two distinct columns whose four intersections all have the same color. It need not occupy adjacent rows or columns. Can a grid with four columns avoid such a rectangle?

There are sixteen possible complete binary rows. Seventeen rows force a repeated complete row, and that row contains a same-color column pair, so seventeen rows suffice. But a full row remembers more information than the desired rectangle needs. Keep only a certificate: its color and an unordered pair of columns with that color in one row. Four columns give six column pairs, and two colors give twelve certificate types.

If a row has a entries of color0 and4−a of color1, it contributes C(a,2)+C(4−a,2) certificates. The five possibilities a=0,1,2,3,4 give6,3,2,3,6. Every row therefore contributes at least two. Seven rows contribute at least fourteen certificates to twelve types, forcing a repetition. Within a single row a given type occurs at most once, so the repetition comes from two distinct rows. Those rows and that type’s column pair form the required four equal-colored corners. Independence, random colors and adjacent corners play no role.

Find a repeated small certificate

Each cell is color0 or1. Click a cell to change its color, then inspect which same-color column pairs repeat in different rows. Four corners of a rectangle must share one color.

Reset construction with 6 balanced rows7 rows: repeat the first balanced row

Row	Column1	Column2	Column3	Column4
1	0	0	1	1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0

Actual certificates: 12. Guaranteed minimum: 12. Buckets:12. Rectangle count: 0.

The row lower bound alone does not force a collision. Inspect this particular coloring rather than infer absence.

All twelve bucket occupancies are at most one: this displayed coloring has no monochromatic rectangle.

Color	Column pair	Rows contributing	Occupancy
0	1, 2	1	1
0	1, 3	2	1
0	1, 4	3	1
0	2, 3	4	1
0	2, 4	5	1
0	3, 4	6	1
1	1, 2	6	1
1	1, 3	5	1
1	1, 4	4	1
1	2, 3	3	1
1	2, 4	2	1
1	3, 4	1	1

Reset

The inspector checks at most84 row/certificate combinations. Counting unordered row pairs within buckets counts each rectangle once. The general proof below is separate from this bounded enumeration. Settings are temporary and do not award mastery.

Prove the six-row boundary, rather than infer it from a weak bound

The six rows 0011, 0101, 0110, 1001, 1010, 1100 are all ways to choose exactly two zero positions. A certificate of color0 and a chosen column pair occurs only in the row whose zero positions are exactly that pair. A certificate of color1 occurs only in the row whose zero positions are the complementary pair. Thus every type appears exactly once, and no rectangle occurs. This proves six rows can avoid a rectangle, while seven always force one: the threshold is sharp for four columns and two colors.

The inequality “at least twelve certificates in twelve types” alone would not prove avoidance. A modified six-row grid can repeat a type and contain a rectangle. The explicit construction supplies the lower-bound example; the universal count supplies the upper guarantee. In any displayed grid, if a certificate type occurs in b rows, it produces C(b,2) rectangles. Summing this over types counts every monochromatic rectangle exactly once, because its color, column pair and row pair determine it.

General colors and economical certificate bounds

Suppose there are q≥1 colors and c≥2 columns. Write c=q a+s with integers a≥0 and0≤s<q. A row with color counts n_i contributes the sum of C(n_i,2). This is minimized when the counts differ by at most one: if one count exceeds another by at least two, moving one entry from the larger to the smaller reduces the sum by the positive difference of those counts minus one. Repeating these moves terminates because the nonnegative integer sum decreases. The balanced counts are a+1 in s colors and a in the other q−s colors. The minimum is L=q C(a,2)+s a.

There are q C(c,2) certificate types. If R rows satisfy R L>q C(c,2), their certificates force a rectangle. For L>0 the sufficient row count is the floor of q C(c,2)/L, plus one. It need not be the optimal threshold without a matching avoidance construction. When L=0, this argument supplies no finite row threshold. In particular, if c≤q, a row can use distinct colors in every column; repeating that row arbitrarily many times never creates a monochromatic rectangle.

For three colors and seven columns, a=2 and s=1, so L=5 and there are63 types. Thirteen rows give at least65 certificates and force a rectangle. Twelve rows give only a lower bound of60, which does not settle existence or avoidance; a failed sufficient test is not a counterexample. The four-column binary construction proves sharpness only for its own parameters.

Continue

Depth: extremal arguments often choose a largest, smallest or longest object and exploit what would happen if it could be improved. Pigeonhole and extremal reasoning can prove existence without providing an efficient search algorithm; existence and computational cost are separate claims.