Kombinatorika. Shaxmat masalasi Kombinatorika turidagi masalalar

1. Kombinatorika. Shaxmat masalasi

   1. Kombinatorika turidagi masalalar.

Kombinatorika matematikaning bo’limi bo’lib, unda biror-bir qonuniyatga bo’ysingan nechta har xil kombinatsiya borligi masalasi o’rganiladi. Ularni berilgan ob’ektlardan ham tashkil qilish mumkin.
Insoniyat faoliyatining deyarli barcha sohalarida ob’ektlarni tanlash va ularni biror tartibda joylashtirish masalalari bilan shug’ullanishga to’g’ri keladi, masalan, mexanizmlarning yangi modellarini yaratayotgan konstruktorga, qishloq xo’jaligi strukturalarini bir nechta maydonga taqsimlashni rejalashtirayotgan agronom-olimga, berilgan atom tarkibiga ega bo’lgan organik molekulalarning tuzilishini o’rganayotgan ximikga va boshqalar.
Kombinatorli deb nom olgan, shunga o’xshash masalalar bilan juda qadim zamonlarda ham duch kelingan. Qadimgi Xitoyda bundan bir nechta ming yillar avval berilgan sonlarning barcha gorizontallari, vertikallari va bosh diagonallari bo’yicha yig’indilari teng bo’lgan sehrli kvadaratlarni yasash bo’yicha shug’ullanishgan. Qadimgi Gretsiyada she’r o’lchovlaridagi uzun va qisqa bo’g’inlarning har xil kombinatsiyalari sonini sanashda, figurali sonlar nazariyasi bilan shug’ullanishda, maxsus tarzda qirqilgan kvadrat bo’laklaridan figuralarni yasashda bunday masalalarga duch kelishgan.
Kombinator masalalar shashka, shaxmat, domino, kara, kosti va boshqa o’yinlar bilan bog’liq holda ham kelib chiqadi (Masalan, shaxmat doskasida birortasi ham boshqalari bilan kesishmaydigan qilib 8 ta ruxni joylashtirish, shaxmat doskasining barcha maydonlarini asp bilan kezib chiqish va boshqa shu kabi masalalar). Shaxmat nafaqat ommaviy o’yin, balki qiziqarli matematik masalalar to’plamining manbai hamdir. Shuning uchun ham shaxmat terminlarining kombinatorikaga oid adabiyotlarda, graflar nazariyasida, kibernetikada, o’yinlar nazariyasida, programmalashda uchrashi bejiz emas.
Quyida shaxmat doskasiga oid bir nechta masala keltirilgan.
1 masala
Asp bilan taxtadagi hamma maydonni har katakda bir martadan bo’lib aylanib chiqing.

Bu masala bilan XVIII va XIX a.ning ko’pchilik matematiklari, jumladan L. Eyler ham shug’ullangan. Aslida masala Eylergacha ma’lum bo’lgan bo’lsa ham, u birinchi bo’lib masalaning matematik mohiyatiga ahamiyat beradi. Marshrutlarning soni 8 mln. dan ko’p emasligi isbotlangan bo’lishiga qaramay, hozirgacha nechta marshrut mavjudligi noma’lum. Asp matshrutini qurishning ko’p metodlari topilgan, har xil matematik qonuniyatlar aniqlangan. Uchta marshrut keltiramiz. 1- rasmda marshrut maydonlari 1 dan 64 gacha ketma-ket nomerlangan, 1, 3 -rasmdagi marshrutlar yopiq (boshlang’ich va oxirgi kataklar asp yurishi bilan o’zaro bog’langan), 2- rasmdagi marshrut yarim sehrli (8x8) - kvadrat hosil qiladi (istalgan vertikaldagi va gorizontaldagi sonlar yig’indisi 260 ga teng, lekin bosh diagonaldagi sonlar yig’indisi undan farq qiladi: bu marshrut bundan tashqari g’aroyib simmetriyaga ega - taxta 180⁰ ga burilsa, marshrutning birinchi yarmi (1 dan 32 gacha yurishlar) ikkinchi yarmiga (32 dan 64 gacha yurishlarga) aylanadi.

50	11	24	63	14	37	26	35
23	62	51	12	25	34	15	38
10	49	64	21	40	13	36	27
61	22	9	52	33	28	39	16
48	7	60	1	20	41	54	29
59	4	45	8	53	32	17	42
6	47	2	57	44	19	30	55
3	58	5	46	31	56	43	18

1-rasm.

Boshqa figuralar uchun ham marshrutlar haqidagi masalalar tuzilgan. 2 - rasmda farzinning butun taxta bo’ylab eng qisqa yopiq marshruti tasvirlangan, bu 14 yurishni oladi.

2-rasm.

2 masala
8 ta farzinni bir - biriga zarb beraolmaydigan qilib, ya’ni ulardan hech qanday ikkitasi bir vertikal, gorizontal yoki diagonal chiziqda turmaydigan qilib necha usul bilan joylash mumkin?
U yoki bu joylashuvni topish unchalik qiyin emas, ularning umumiy sonini hisoblash qiyinroq. 92 xil talab qilingan joylashuv borligi, ular 12 asosiy joylashuvdan taxtani burish va ko’zgu simmetriyasi yordamida hosil qilinishi aniqlangan. Masala echimlaridan biri 3 - rasmda berilgan.

			F
	F
							F
				F
						F
F
		F
					F

3-rasm.
Bunday masalalar barcha shaxmat figuralari uchun qo’yiladi. Oldin bir figura ko’pi bilan nechta olinganda taxtada bir - biriga zarb bermasligi aniqlanadi, so’ng nechta joylashuv mavjudligi aniqlanadi. Farzinlar kabi, ko’pi bilan 8 dona Rux qo’yish mumkin (joylashuvlar jami !-40320 ta). Masalan, ularni 3-rasmda farzinlar qo’yilgan kataklarning o’ziga qo’yish mumkin.
Bir-biriga duch kelmaydigan fillarning maksimal soni 14, ja’mi 256 ta joylashuvlar, asplar-32 ta (hamma yoki hamma qora kataklarga joylashuv 2- usul), shohlar 16 ta 5- rasm (281571 xil joylashuv).

	S	S	S	S	S	S
S	S	S	S	S	S	S	S

4-rasm

Kr		Kr		Kr		Kr
Kr		Kr		Kr		Kr
Kr