Kompleksa matemātikas problēma
SKOLA2030 uzdevums.
Piemērs:
Plaknē dotas galīga skaita taisnes.
Jāpierāda, ka apgabalus, kuros taisnes sadala plakni, var iekrāsot ar divām krāsām tā, lai divi apgabali, kuriem ir kopīga mala, nebūtu vienā krāsā (apgabali, kuriem ir tikai viena kopīga virsotne, var būt iekrāsoti vienā krāsā).
Risinājums
Tieši tā, kā aprakstīts uzdevumā, iekrāso ģeogrāfiskās kartes. Tāpēc šajā gadījumā doto plakni nosauksim par karti.
Uzdevuma formulējumā nekas nav teikts par naturāliem skaitļiem, tāpēc formulēsim apgalvojumu \(A(n)\) sekojoši:
Jebkuru karti, kuru sadala \(n\) taisnes, var iekrāsot ar divām krāsām, .
1) Indukcijas bāze. Pārbauda, vai ir patiess apgalvojums \(A(1).\)
Ja \(n=1\), karti sadala viena taisne, katru pusplakni varam iekrāsot atšķirīgi. Skat. attēlu:
2) Induktīvais pieņēmums (hipotēze). Pieņem, ka \(A(k)\) ir patiess.
Pieņemsim, ka karti var izkrāsot ar divām krāsām, ja to sadala \(k\) taisnes. Piemēram, šādi:
3) Induktīvā pāreja. Pierāda, ka apgalvojums \(A(k+1)\) ir patiess.
Novilksim kartē \((k+1)\)-mo taisni. Tagad karti sadala \(k+1\) taisne:
Rīkosimies sekojoši:
Visiem apgabaliem, kas atrodas taisnes \((k+1)\) vienā pusē, atstāsim iepriekšējo krāsu, bet taisnes otrā pusē krāsu mainām uz pretējo.
Ja divu apgabalu kopējā mala ir uz šīs taisnes, tad apgabali ir dažādās krāsās.
Ja apgabalu kopējā mala ir uz citas taisnes (kuru kopējais skaits ir \(k\)), tad apgabali ir iekrāsoti dažādās krāsās saskaņā ar induktīvo pieņēmumu.
Secinājums
Tātad apgalvojums \(A(n)\) ir spēkā visām naturālām \(n\) vērtībām.
Esam pierādījuši, ka jebkuru karti, kuru sadala \(n\) taisnes, var iekrāsot ar divām krāsām.