Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source: original paper, printed p. 535, the counterexample following Theorem 3. The distance estimates below supply the omitted geometric verification.
Statement
There is a red-blue coloring of with no red unit-distance pair and no blue congruent copy of a particular -point set.
Full proof
Set , , and
Color red the closed squares
and color every other point blue. Points in one red square have mutual distance at most . Points in different red squares differ by at least in at least one coordinate, so their distance exceeds one. Thus there is no red unit pair, including on square boundaries.
Consider any congruent copy of , with arbitrary orientation and location. Its convex hull is a square of side
The red square centers form . A center lies at distance at most from the center of the grid square, by rounding the two coordinates to that lattice. Since , the point lies inside the grid square regardless of its orientation.
Round the two coordinates of in the grid's orthonormal coordinate system to the nearest grid positions. Because is inside the grid square, the resulting point belongs to the finite grid and satisfies
The disk of radius centered at lies in its red square, so is red. Every congruent copy of therefore meets the red set. None is wholly blue.
This is an array of small red squares, not a coloring by strips. The size is a historical sufficient example, not an optimal threshold. The argument does not refute the blue-unit-square conclusion of Problem 214.