Artykuł źródłowy w wersji do druku [application/pdf]: (79 KB)
Na kartce narysowano pewną liczbę okręgów. Udowodnij, że uzyskaną w ten sposób mapę można pomalować dwoma kolorami.
Rozwiązanie
Każdy punkt mapy pomalujmy na czarno, jeśli leży on wewnątrz nieparzystej liczby spośród danych okręgów, a na biało w przeciwnym przypadku.
Uwaga
Można też kolorować mapę w miarę jej powstawania. Wnętrze pierwszego okręgu pomalujmy na czarno. Następnie po dorysowaniu każdego kolejnego okręgu, zamieńmy barwy wszystkich obszarów w jego wnętrzu. Nietrudno sprawdzić, że uzyskamy w ten sposób dobre pokolorowanie.