Метод математической индукции

3-§. Xaritani bo‘yash
Tekislikda biror geografik xarita berilgan deb faraz qilaylik.
Ta’rif. Agar ixtiyoriy davlat ma’lum bo‘yoq bilan bo‘yalgan, umumiy chegaraga ega bo‘lgan ikkita davlat turli ranglar bilan bo‘yalsa xarita to‘g‘ri bo‘yalgan deyiladi.
To‘g‘ri bo‘yalgan xaritaga ixtiyoriy geografik xarita misol bo‘la oladi. Ixtiyoriy xaritani ma’lum bo‘yoq bilan bo‘yash mumkin, lekin bunday bo‘yash tejamli bo‘lmaydi. Shuning uchun quyidagi masalani qo‘yish lozim bo‘ladi: xaritani bo‘yash uchun bo‘yoqlar turlari iloji boricha kam bo‘lsin.
3.1-masala.

2 ta rang 3 ta rang 4 ta rang
Har qanday xaritani bo‘yash uchun 5 ta turdagi bo‘yoqlarni yetarli ekanligi isbotlangan.
Hozirgi kungacha to‘rtta bo‘yoq bilan to‘g‘ri bo‘yash mumkin bo‘lgan xarita topilmagan. Birinchi marotaba ushbu holatga nemis matematigi Myobius e’tibor berdi. Shu paytgacha yirik olimlar “To‘rtta bo‘yoq muommosi”ni yechish uchun harakat qilishgan. To‘rtta bo‘yoq bilan ixtiyoriy xaritani bo‘yash yoki bo‘yash mumkin emasligini isbotlashga harakat qilishgan. Lekin shu kunga qadar hech kim bajara olmagan. Qiziqarlisi shundaki, ba’zi sirtlar uchun xaritani bo‘yash muommasi hal etilgan. Ixtiyoriy xaritani bo‘yashda shunday sirtlar mavjudki, uni bo‘yash uchun 7 ta bo‘yoq etarli hisoblanadi. Shunday sirtlar ham mavjudki, 6 ta bo‘yoq bilan ham xaritani bo‘yash qiyin.
3.2-masala. To‘g‘ri tortburchak to‘g‘ri chiziq bilan n ta qismga bo‘lingan deb faraz qilaylik. Bunday holda umumiy tomonga ega bo‘lgan ikkita qismni turli rangdagi qora va oq bo‘yoqga bo‘yash mumkin.

Isboti. n = 1da quyidagiga egamiz:
n = k uchun tasdig to‘g‘ri deb faraz qilaylik. U holda n=k+1 da ham to‘g‘ri ekanligini isbotlash lozim.
n = k + 1 da k to‘g‘ri chiziqdan iborat k+1 to‘g‘ri chiziqli ma’lumotlardan tashkil etgan to‘g‘ri to‘rtburchakni bo‘yash lozim:

( k+1) to‘g‘ri chiziqdan qolgan qismlarni qarama-qarshi bo‘yoqga bo‘yash lozim bo‘ladi:

(k+1) to‘g‘ri chiziq