Školjka

%V0 Spojimo u parove ovih $ n $ točaka te provucimo kroz njih $ n \choose 2 $ pravaca. Obzirom da je to konačno mnogo pravaca, slijedi da možemo odabrati neki pravac $ p $ tako da nije paralelan s niti jednim od ovih $ n \choose 2 $ pravaca. Označimo kružnice na neki način s brojevima od $ 1 $ do $ n $. Neka je $ S_i $ središte kružnice $ k_i $ koju smo označili s $ i $ za $ 1 \leq i \leq n $. Na početku su sve kružnice obojane u boju $ 0 $ (ona nije konačna boja), a možemo ih obojati u jednu od boja iz skupa $ B = \big\{ 1, 2, 3, 4 \big\} $. Dokazat ćemo tvrdnju zadatka tako što ćemo pronaći konstrukciju bojanja. [b] Konstrukcija [/b] Na početku postavimo pravac $ p $ negdje u ravninu tako da ne sijeće niti jednu kružnicu te da su sve kružnice s jedne strane pravca $ p $. Pomičemo pravac $ p $ u smjeru kružnica sve dok sve kružnice ne prijeđu s jedne strane pravca na drugu. Kako je pravac $ p $ neparalelan s svim ostalim pravcima, slijedi da u jednom trenutku može najviše jedna kružnica prijeći s jedne strane pravca $ p $ na drugu. Promotrimo u nekom trenutku kružnicu $ k_x $ koja prelazi na drugu stranu pravca (pod "prelaskom" podrazumijevamo prelazak središta $ S_x $ na drugu stranu pravca $ p $). Nju ćemo obojati u boju (čiji je broj najmanji mogući) iz skupa $ B $ tako da se taj broj boje ne poklapa sa brojevima boja kružnica koje $ k_x $ dodiruje. To uvijek možemo zbog Lemme jer se ne može dogoditi da neka kružnica ima boju $ 0 $, a više od tri kružnice (koje dodiruju tu kružnicu) imaju boju veću od $ 0 $. Na početku obojamo kružnicu koja je najbliža pravcu $ p $ u boju $ 1 $, te dalje provodimo već objašnjeni postupak bojanja za ostalih $ n - 1 $ kružnica. [b] Q.E.D. [/b] [b] Dokaz Lemme [/b] Tvrdnja: Ne može se dogoditi da neka kružnica ima boju $ 0 $, a više od tri kružnice (koje dodiruju tu kružnicu) imaju boju veću od $ 0 $. Pretpostavimo suprotno, tj. da neka kružnica ima boju $ 0 $, a više od tri kružnice (koje dodiruju tu kružnicu) imaju boju veću od $ 0 $. Provest ćemo dokaz ako se radi o $ 4 $ kružnice koje imaju boju veću od $ 0 $, jer je dokaz analogan i za $ 5 $ i za $ 6 $ (kružnica ne može imati više od $ 6 $ susjeda). Neka kružnica $ k_a $ ima boju $ 0 $, a kružnice $ k_b $, $ k_c $, $ k_d $ i $ k_e $ (koje je dodiruju) boju veću od $ 0 $ (neka vrijedi da su kružnice $ k_b $, $ k_c $, $ k_d $ i $ k_e $ poredane u smjeru kazalje na satu oko kružnice $ k_a $). Vrijedi: $$ \angle S_b S_a S_c \geq 60^{\circ} \qquad (1) $$ $$ \angle S_c S_a S_d \geq 60^{\circ} \qquad (2) $$ $$ \angle S_d S_a S_e \geq 60^{\circ} \qquad (3) $$ $$ (1) + (2) + (3) \implies \angle S_b S_a S_e \geq 180^{\circ} $$ Kako je $ \angle S_b S_a S_e \geq 180^{\circ} $, slijedi da je nemoguće da su u nekom trenutku središta $ S_b $ i $ S_e $ već "prešla" pravac $ p $, a da $ S_a $ još nije. Kontradikcija.