Putnam 1994 A-3

$X$ を、辺の長さが $1, 1, \sqrt{2}$ である直角二等辺三角形の点の集合とする。
もし、$X$ の元を4色で塗り分ける場合、同じ色の点が $2-\sqrt{2}$ 以上の距離に存在している。

---

「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」場合を仮定する。
$X$ の元が4色で塗り分けられないことを証明する。

直角三角形の各点を $A:(0, 0), B:(1, 0), C:(1,1)$ とする。
また、線分 $AB$ 上の点で、点 $A$ から $k=2-\sqrt{2}$ の距離にある点を $D$ とする。同様に、線分 $AC$ 上の点で、点 $A$ から $k$ の距離にある点を $E$、点 $C$ から $k$ の距離にある点を $F$、線分 $BC$ 上の点で、点 $C$ から $k$ の距離にある点を $G$ とする。（下図参照）

三角形 $ABC$ と、三角形 $DBG$ が相似形であることから、線分 $DB$ の長さは $k$ になり、四角形 $ADGE$ と四角形 $CFDG$ が平行四辺形であることが分かる。
よって、線分 $EG$ および 線分 $DF$ の長さも $k$ になる。

点 $A$ および点 $C$ は、どの点からも $k$ 以上離れている。少なくともこれらの点が別々の色である必要がある。点 $A$ 、点 $C$ の色をそれぞれ色 $cA$、色 $cC$ とする。
点 $D$ の色は、点 $A$ からの距離より、色 $cA$ ではない。また、点 $C$ からの距離より、色 $cC$ でもない。よって、色 $cD$ とする。
点 $G$ の色も同様、どの色とも異なる色 $cG$ となる。

点 $B$ の色を色 $cD$ としても一般性を失わない。
このとき、点 $E$ は、その位置から色 $cA$, $cC$ $cG$ のいずれでもない。また、色 $cD$ により点 $B$ を塗っているため、色 $cD$ でもない。

以上より、$X$ の元を4色で塗りつぶすことはできない。

これにより、「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」⇒ 「$X$ の元を4色に塗り分けられない」となる。
よって、上の命題の対偶「$X$ の元を4色で塗り分ける」⇒「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在する」は真となる。