Školjka

%V0 Nazovimo dvije kružnice $k_1$ i $k_2$ "povezane" ako se dodiruju ili ako barem jedna od njih (WLOG $k_1$) dodiruje neku treću kružnicu koja je "povezana" s $k_2$. Skup kružnica u kojem su one sve međusobno "povezane" nazovimo "grupica". Potrebno je dokazati da je sve kružnice u svakoj "grupici" moguće obojati u 4 boje kako zadatak traži. Dokažimo sljedeću tvrdnju: U svakoj "grupici" postoji barem jedna kružnica koja dodiruje najviše 3 druge kružnice (u toj istoj "grupici") Dokaz: Pretpostavimo suprotno, postoji "grupica" u kojoj svaka kružnica dodiruje barem 4 druge kružnice (iste "grupice"). Promatrajmo jednu takvu "grupicu" i smjestimo ju u koordinatni sustav. Obratimo sada pažnju na kružnicu čije središte ima najmanju y koordinatu (ako ih ima više bilo koju od njih) i povucimo pravac paralelan s osi x kroz središte te kružnice ($S$). Tu kružnicu dodiruju bar 4 druge kružnice čija ću središta označiti $S_1$, $S_2$, $S_3$ i $S_4$ redom u smjeru kazaljke na satu oko $S$ tako da je veličina kuta $\sphericalangle S_1SS_4$ najveća (od kuteva $\sphericalangle S_2SS_1, \sphericalangle S_3SS_2, \sphericalangle S_4SS_3$ te $\sphericalangle S_1SS_4$). Primijetimo da vrijedi $|\sphericalangle S_2SS_1|, |\sphericalangle S_3SS_2|, |\sphericalangle S_4SS_3| \geq 60^{\circ}$ (zbog toga što sve kružnice imaju jednak radijus i nikoje dvije se ne sijeku) pa je minimalna vrijednost veličine kuta $\sphericalangle S_4SS_1$ 180°. Kako sve četiri kružnice moraju imati veću ili jednaku y koordinatu od kružnice oko $S$, zaključujemo da se to može dogoditi jedino za slučaj jednakosti, odnosno za $|\sphericalangle S_2SS_1|=|\sphericalangle S_3SS_2|=|\sphericalangle S_4SS_3|=60^{\circ}$. No sada sa svake strane kružnice oko $S$ imamo još dvije kružnice čija središta imaju jednaku y koordinatu i za njih vrijedi ista stvar pa će i oko njih postojati kružnice čija središta imaju jednaku y koordinatu i to će se nastaviti u beskonačnost, ali kako "grupica" nema beskonačan broj kružnica unutar sebe, to je kontradikcija te zaključujemo da u svakoj "grupici" uvijek postoji barem jedna kružnica koja dodiruje najviše 3 druge. Promatrajmo sada neku "grupicu". Dokazali smo da postoji kružnica (WLOG $k_1$) koja dodiruje najviše tri druge kružnice unutar te grupice pa zbog toga boja kojom ćemo obojati $k_1$ ovisi samo o bojama tih kružnica, a kako bojimo u četiri boje, uvijek će postojati boja kojom možemo obojati $k_1$ tako da su uvjeti zadatka zadovoljeni (možemo ju "dobro" obojati). Zbog te činjenice kružnicu $k_1$ možemo obojati zadnju i dovoljno je dokazati da možemo "dobro" obojati ostale kružnice u "grupici". Broj kružnica koje sada moramo "dobro" obojati smanjio se za jedan i opet imamo "grupicu" u kojoj opet postoji barem jedna kružnica koja dodiruje najviše tri druge kružnice i postupak ponavljamo; smanjujemo broj kružnica dok ne dođemo do četiri kružnice koje obojimo u 4 različite boje. Sada redom unatrag bojimo kružnice koje smo ignorirali i ovime smo obojali sve kružnice u nekoj "grupici" u 4 boje čime je ovaj zadatak gotov.