Шатрын тавцан дээр даалууг байрлуулах логик даалгавар. Математикийн олимпиад, олимпиадын бодлого
8х8 хэмжээтэй шатрын самбараас ташуу эсрэг талын хоёр буланг хайчилж, 31 даалууг өгсөн; даалуу бүр самбар дээрх хоёр квадратыг хамарч болно. Бүхэл бүтэн хавтанг ясаар хучиж болох уу? Хариултынхаа үндэслэлийг хэлнэ үү.
Шийдэл
Эхлээд харахад энэ нь боломжтой юм шиг санагдаж байна. Самбар нь 8х8, тиймээс 64 нүд байна, бид хоёрыг хасч, 62 үлдлээ гэсэн үг. 31 яс багтах ёстой юм шиг байна?
Эхний эгнээнд даалуунуудыг байрлуулахыг оролдоход бид ердөө 7 квадрат талбайтай, нэг яс нь хоёр дахь эгнээ рүү явдаг. Дараа нь бид хоёр дахь эгнээнд даалуунуудыг байрлуулж, дахин нэг хавтан гурав дахь эгнээ рүү явдаг.
Эгнээ бүрт нэг яс байх бөгөөд дараагийн эгнээ рүү шилжүүлэх шаардлагатай бөгөөд бид хичнээн олон зураглалыг оролдсон ч бид хэзээ ч бүх ясыг байрлуулж чадахгүй.
Шатрын самбар нь 32 хар, 32 цагаан нүдэнд хуваагддаг. Эсрэг талын булангуудыг арилгаснаар (эдгээр нүднүүд ижил өнгөтэй гэдгийг анхаарна уу) бидэнд нэг өнгийн 30 нүд, өөр өнгийн 32 нүд үлдэнэ. Одоо бидэнд 30 хар, 32 цагаан дөрвөлжин байна гэж бодъё.
Бидний самбар дээр тавих шоо бүр нэг хар, нэг цагаан нүдийг эзэлнэ. Тиймээс 31 даалуу 31 цагаан, 31 хар эсийг эзэлнэ. Гэтэл манай самбарт 30 хар, 32 цагаан эс л бий. Тиймээс ясыг задлах боломжгүй юм.
Шинжилгээг Г.Лакман Макдоуэллийн номын орчуулгаас авсан бөгөөд зөвхөн мэдээллийн зорилгоор хийгдсэн болно.
Хэрэв танд таалагдсан бол ном худалдаж авахыг зөвлөж байна.
Даамын самбар 10 гэдгийг баталX10-ыг торны шугамын дагуу тэгш өнцөгт 1 болгон огтолж болохгүйX4. (Д.Ю. Кузнецовын дагуу шийдэл.)
Шийдэл 1 . Самбарыг 2х2 квадрат болгон хувааж, даамын самбарын хэв маягаар будна (Зураг 1). Аливаа 1x4 тэгш өнцөгт нь ижил хэмжээтэй (2) хар ба цагаан нүдийг агуулна гэдгийг анхаарна уу, гэхдээ ийм будгаар самбар дээр 52 хар нүд, 48 цагаан нүд байна. тэнцүү биш. Энэ нь 10x10 хэмжээтэй хавтанг 1x4 тэгш өнцөгт болгон хайчлах боломжгүй болно гэсэн үг юм.
Шийдэл 2 . Самбарыг 4 өнгөөр диагональ будгаар будъя (Зураг 2). Аливаа тэгш өнцөгт нь дөрвөн өнгө тус бүрээс нэг нүдийг агуулна гэдгийг анхаарна уу, гэхдээ өгөгдсөн өнгөний хувьд самбар дээр 1 ба 3-р өнгөний 25 нүд, 4-ийн 2, 24 нүдний 26 нүд, өөрөөр хэлбэл. тэнцүү биш. Энэ нь 10x10 хэмжээтэй хавтанг 1x4 тэгш өнцөгт болгон хайчлах боломжгүй болно гэсэн үг юм.
1. Шатрын самбараас баруун болон зүүн доод булангийн нүднүүдийг хайчилж ав. Үүссэн дүрсийг 1х2 хэмжээтэй даалуу болгон хувааж болох уу? Хэрэв та баруун доод, зүүн дээд хэсгийг огтолж авбал?
2. 6х6 хэмжээтэй банзыг даалуу болгон хайчилж, дунд нь яг 11 хэвтээ мод байх боломжтой юу? (Хоёр өнгөөр хэвтээ будах.)
3. Зэргэлдээх хэсгүүдийг өөр өөр өнгөөр будахын тулд зургийг дөрвөн өнгөөр будна. Гурван өнгөөр явах боломжтой юу? (Үйл ажиллагаа 6: Өнгө будгийг үзнэ үү газарзүйн газрын зураг- 5-6 анги).
4. 4х4 дөрвөлжин талбайд зүүн талын нүдийг хараар, үлдсэн хэсгийг нь цагаанаар будна. Нэг үйлдлээр дурын тэгш өнцөгт доторх бүх нүдийг эсрэг өнгөөр дахин будахыг зөвшөөрдөг. Гурван үйлдлээр анхны будгаас шатрын будгийг хэрхэн яаж авах вэ?
5. Хэд хэдэн царцаа нэг шулуун дээр сууж, хөршүүдийн хоорондох зай ижил байна. Минут тутамд нэг нь өөр царцаатай харьцуулахад тэгш хэмтэй цэг рүү үсэрдэг. Хэсэг хугацааны дараа царцаа Саша хөрш Лёшагийн эхэнд сууж байсан газарт хүрч чадах уу?
6. а) Шатрын самбарыг "Т" үсгийн хэлбэртэй 4 нүднээс бүрдэх дүрс болгон хайчилж болох уу?
б) 10х10 хэмжээтэй шатрын самбарыг ийм дүрс болгон хайчилж болох уу?
7. Булангийн зүсэгдсэн 8х8 квадратыг 1х3 хэмжээтэй тэгш өнцөгт болгон хувааж болох уу?
8. 10х10 хэмжээтэй самбарыг "G" үсгийн хэлбэртэй дөрвөн нүдээр хувааж болох уу? (Хоёр өнгөөр хэвтээ будах.)
9. 8х8 хэмжээтэй банзыг 2х1 хэмжээтэй даалуу болгон зүснэ. Босоо 15, хэвтээ 17 даалуу байж болох уу?
10. Гурвалжин нь гурвалжинд хуваагдсан (25 ширхэг), зурагт үзүүлэв. Цох нь зэргэлдээх (хажуу талд) гурвалжингийн хооронд хөдөлж, гурвалжинд алхаж чаддаг. Хэрэв цох гурвалжин бүрт нэгээс илүүгүй удаа очсон бол хамгийн ихдээ хэдэн гурвалжинг дамжин өнгөрөх вэ?
11. 5-р талтай тэгш талт гурвалжнаас хайчилж авч болох 1-р талтай хоёр тэгш талт гурвалжнаас бүрдэх хамгийн олон тооны ромб хэд вэ (өмнөх бодлогын зургийг үз).
12. Гурвалжин цайз нь 100 ижил гурвалжин танхимд хуваагдана. Хана бүрийн голд хаалга байдаг. Хаана ч нэгээс олон удаа зочлохыг хүсдэггүй хүн хэдэн өрөөнд зочилж болох вэ?
2-р бүлэг
Бидний эхлэх гэж буй шатрын математикийн талаар дэлгэрэнгүй тайлбарлахын тулд дараахаас эхлэх нь зүйн хэрэг юм. математикийн асуудлуудсамбарын тухай, үүн дээр ямар ч хэсэг байрлуулахгүйгээр. Энэ бүлэг нь энэ сэдэвт зориулагдсан болно.
Юуны өмнө 2х1 даалуугаар хавтанг бүрхэх хэд хэдэн асуудлыг авч үзье. Хаа сайгүй даалуу бүр самбарын хоёр квадратыг, дөрвөлжин тус бүрийг даалууны хагасаар бүрхсэн гэж үздэг. Дараагийн хуучин асуудлаас эхэлье.
Эсрэг талын булангийн нүдийг хайчилж авсан 8х8 хэмжээтэй дөрвөлжин талбайг даалуугаар хучих боломжтой юу (Зураг 2а)?
Бид алгебрийн үндэслэлийг ашиглаж болох ч "шатрын" шийдэл нь илүү энгийн бөгөөд гоёмсог юм. Таслагдсан талбайгаа хар цагаан өнгөөр будаж, a8 ба h1 булангийн хоёр талбаргүй шатрын самбар болгон хувиргацгаая (Зураг 2b). Самбарын ямар ч бүрээсний хувьд даалуу бүр нэг цагаан, нэг хар дөрвөлжинг хамардаг. Бид хараас хоёр цагаан талбар багатай (зүссэн талбарууд нь цагаан) тул шаардлагатай хамрах хүрээ байхгүй байна! Бидний харж байгаагаар самбарыг будах нь шатарчин тоглоомын үеэр жолоодоход хялбар болгодог төдийгүй математикийн асуудлыг шийдвэрлэх хэрэгсэл болдог.
Боломжит асуудалд булангийн талбайнууд нь самбараас таслагдах нь чухал биш, харин тэдгээр нь ижил өнгөтэй байх нь чухал байв. Нэг өнгийн талбарыг хэрхэн хайчилж авсан ч үлдсэн самбарыг даалуугаар бүрхэж чадахгүй нь ойлгомжтой. Тиймээс дараах асуудал гарч ирнэ.
Одоо шатрын самбар дээр өөр өөр өнгийн хоёр талбайг хайчилж авлаа гэж бодъё. Үлдсэн самбарыг 31 даалуугаар бүрхэх боломжтой юу?
Үргэлж ийм байдаг. Гайхалтай нотолгоог Америкийн алдарт математикч Р.Гомори олсон. Зурагт үзүүлсэн шиг босоо болон хэвтээ тэнхлэгийн хоорондох заагийг шатрын самбар дээр зурцгаая. 3. Эдгээр хилийн хоорондох төөрдөг байшинд хар, цагаан талбарууд бие биенээ дагаж, битүү утсан дээрх хоёр өнгийн товчлуур шиг ээлжлэн солигдоно (энэ төөрдөг байшинг тойрч гарах зам хаалттай). Бид өөр өөр өнгийн хоёр талбарыг самбараас хайчилж авбал утас тасрах болно: хэрвээ зүссэн талбайнууд зэргэлдээ байвал нэг газар, бусад тохиолдолд хоёр газарт. Энэ тохиолдолд утас бүр нь тэгш тооны талбараас бүрдэнэ. Тиймээс эдгээр хэсгүүд, улмаар бүхэл бүтэн самбарыг даалуугаар хучиж болно!
Цагаан будаа. 3. Гомори лабиринт |
Товчлуур болон утастай холбоотой сонирхолтой санаануудыг 11-р бүлгээс олох болно.
Шатрын самбараас зарим талбайг хайчилж аваад үлдсэн хэсэгт нь даалуу тавихгүй гэж бодъё. Энэ шинж чанартай хамгийн бага тооны хайчлагдсан талбар нь 32 байгаа эсэхийг шалгахад хялбар байдаг - эдгээр нь бүгд ижил өнгөтэй (цагаан эсвэл хар) талбарууд юм.
Шатрын самбар, даалууны бодлого нь ийм төрлийн асар том цуврал бодлогын зөвхөн өчүүхэн хэсэг юм. Америкийн математикч С.Голомб бүхэл бүтэн шинжлэх ухааныг бий болгож, түүнийгээ полимипо гэж нэрлэсэн бөгөөд энэ сэдвээр бичсэн ном нь дэлхийн олон оронд, тэр дундаа манай улсад орчуулагдан хэвлэгджээ. Ерөнхийдөө полиомино бол квадратуудаас бүрдсэн энгийн холбогдсон дүрс юм. Шатарчин хүний үүднээс авч үзвэл зүгээр л холбогдсон байна гэдэг нь бүх полиомино квадратуудыг дэгээгээр тойрч гарах боломжтой гэсэн үг. 07 квадратын тооноос хамааран полиомино нь өөр өөр зэрэгтэй байдаг. Мономино нь нэг квадрат, даалуу хоёр, тромино гурав, тетрамино дөрөв, пентомино тав, гептомино зургаан квадрат гэх мэтийг агуулдаг. Бид энгийн шатрын хөлөгтэй холбоотой хэд хэдэн асуудалд анхаарлаа хандуулах болно. Мэдээжийн хэрэг, 64 нь 3-т хуваагддаггүй тул зөвхөн шулуун тромино, өөрөөр хэлбэл 3 × 1 даалуунуудаар dssk-ийг бүрхэх боломжгүй юм. Дараах асуудал гарч ирнэ.
21 шулуун тромино, нэг мономино бүхий шатрын самбарыг бүрхэх боломжтой юу? Хэрэв тийм бол мономино ямар талбайг эзэлж чадах вэ?
Зураг дээрх шаардлагатай дапо бүрээсүүдийн нэг. 4а. Мономинуудын боломжит зохицуулалтыг тодорхойлохын тулд бид самбар дээр параллель шугамын хоёр системийг зурж, зурагт үзүүлэв. 4б.
Аливаа бүрээсийн хувьд тромин бүр нь цул шугам дамждаг яг нэг талбарыг, тасархай шугам дамждаг яг нэг талбарыг хамардаг болохыг харахад хялбар байдаг. Хатуу шугамаар огтлолцсон талбайн тоо 22, мөн тасархай шугамаар огтлолцсон талбайн тоо 21 тромино байдаг тул мономинууд зөвхөн шугамын гэр бүлийн хоёроор огтлолцсон талбаруудыг хамрах боломжтой. Зөвхөн ийм квадратууд байдаг: c3, c6, f3, f6! Самбарыг 90, 180, 270° эргүүлснээр та эдгээр дөрвөн талбар бүрт тохирох хамрах хүрээг авах боломжтой.
Дараагийн даалгавар нь дээр дурдсанаас арай өөр юм.
Далууг давахгүйгээр босоо болон хэвтээ тэнхлэгийн хооронд нэг зааг зурах боломжгүй байдлаар даалуугаар шатрын самбарыг бүрхэж болох уу?
Хэрэв бид самбарыг хана, даалууг тоосго гэж төсөөлвөл заасан хил (давхарга) байгаа нь эмзэг өрлөгийг илтгэнэ. Өөрөөр хэлбэл, "хана" нурахгүй байхын тулд "тоосго" зохион байгуулах боломжтой эсэхийг асууж байна. Шаардлагатай аргаар бүрхэж болох тэгш өнцөгтийг "хүчтэй" гэж нэрлэдэг. Шатрын самбарын "хүч чадал" -ыг Зураг дээр харж болно. 5. Ерөнхий тохиолдолд, Гарднер даалууны талбай нь тэгш, урт ба өргөн нь дөрвөөс их байвал 6х6 квадратыг эс тооцвол "хүчтэй" тэгш өнцөгтийг нугалж болохыг харуулж байна.
Доор бид ихэвчлэн нэг хэмжээтэй тэгш өнцөгт шатрын самбаруудыг авч үзэх болно. Энэ тохиолдолд m×n самбар нь m босоо, n хэвтээ (шатар) байна гэж үргэлж үздэг. Талбайнх нь тоо тэгш байвал самбарыг "тэгш", бусад тохиолдолд "сондгой" гэж бид хэлдэг. Самбарын хэмжээсийг заагаагүй тохиолдолд бид m = n = 8 байх стандарт шатрын самбарыг хэлнэ.
100х4 хэмжээтэй самбар нь даалуугаар хучигдсан байдаг. Энэ нь ямар ч даалуунд нөлөөлөлгүйгээр босоо болон хэвтээ хоорондын хилийн аль нэгний дагуу таслагдах боломжтой гэдгийг батал.
Заасан хүрээнүүдийн аль нэг нь самбарыг тэгш тооны талбараас бүрдэх хоёр хэсэгт хуваана. Бид хэсэг тус бүрийн талбайг хоёр ангилалд хуваадаг: энэ хэсэгт бүхэлдээ хучигдсан даалуунууд, хилээр огтлолцсон хучигдсан даалуунууд. Хэсэг бүрийн талбаруудын тоо тэгш (магадгүй тэг), мөн эхний ангиллын талбаруудын тоо (домино тус бүр хоёр талбарыг хамардаг) тул хоёрдугаар ангийн талбайн тоо тэгш байна. Энэ нь хилээр давсан даалууны тоо тэгш байна гэсэн үг юм. Нийтдээ 102 хуваах хил байдаг (99 босоо, 3 хэвтээ) бөгөөд хэрэв тэдгээр нь тус бүр даалуунуудыг гаталж байвал хамгийн багадаа 102 × 2 = 204 даалуунууд хамрах хүрээг хамарна. Бидэнд ердөө 200 ширхэг бий! Үнэндээ бид 100х4 тэгш өнцөгт нь "сул" гэдгийг харуулсан.
Дурын тэгш өнцөгт самбарыг шугаман k-minos (далууны k × 1) -ээр бүрхэх боломжийн асуултыг дараах теоремоор шийднэ.
Хэрэв m эсвэл n тоонуудын ядаж нэг нь үлдэгдэлгүйгээр k-д хуваагдаж байвал m×n самбарыг шугаман k-minos-оор бүрж болно.
Бид теоремыг дараах жишээгээр тайлбарлав.
10х10 хэмжээтэй самбарыг (ийм самбар дээр нэг зуун дөрвөлжин даам тоглодог) шулуун тетраминогоор бүрхэж болох уу?
Шулуун тетрамино нь 4х1 хэмжээтэй бөгөөд энэ нь зарчмын хувьд 25 хавтан нь манай хавтангийн бүх талбайг хамарч чадна гэсэн үг юм. Гэсэн хэдий ч теоремоос харахад энэ нь боломжгүй юм - 10 нь 4-т хуваагддаггүй.
Шатрын самбартай холбоотой хэд хэдэн асуудлыг авч үзье. Дараахь асуудлыг шийдвэрлэхэд түүний будгийг ашиглана.
Самбарыг сондгой тооны талбараас бүрдүүл. Түүний талбай тус бүр дээр бид заримыг нь тавих болно шатрын хэсэг. Эдгээр бүх хэсгүүдийг зэргэлдээх квадратууд руу (босоо эсвэл хэвтээ) зөөж, хоёр нь нэг дөрвөлжин дээр дуусахгүй байх боломжтой юу?
Даалгавар нь боломжгүй юм. Үнэн хэрэгтээ, хэрэв заасан хэсгүүдийн нүүлгэн шилжүүлэлт байсан бол "цагаан" хэсэг бүр (цагаан талбар дээр зогсож байгаа) "хар" (хар талбар дээр унах), "хар" бүр "цагаан" болж хувирна.
Тиймээс самбар нь ижил тооны цагаан, хар талбайнуудаас бүрдэх бөгөөд энэ нь түүний "сонин" байдалтай зөрчилддөг.
Шатрын самбар огтлох асуудал түгээмэл байдаг. Тэдгээрийн хамгийн алдартай нь С.Лойдын эзэмшдэг дараах зүйл юм.
a1, b2, c3, d4 талбайд дөрвөн баатар байдаг. Самбарыг дөрвөн тэнцүү хэсэг болгон хайчилж (давхсан үед давхцаж байгаа) тус бүр нь морьтой болно.
Зүсэх асуудалд зөвхөн хавтангийн босоо болон хэвтээ хоорондын хилийн дагуу зүсэлт хийдэг гэж үргэлж үздэг. Энэ асуудлын шийдлийг Зураг дээр үзүүлэв. 6. Лойдын үеэс хойш энэ сэдвээр олон шинэ, илүү хэцүү асуудлууд гарч ирсэн. Ялангуяа баатруудын өөр өөр албан тушаалд зориулж самбарыг дөрвөн тэнцүү хэсэгт хуваах асуудлыг шийдсэн (мэдээж баатарууд энд зөвхөн бэлгэдлийн үүрэг гүйцэтгэдэг). Энэ асуудлаар шийдэгдээгүй олон асуудал байсаар байна. Жишээлбэл, ердийн хавтанг (хэсэггүй) хоёр тохирох хэсэг болгон хэрчиж болох аргуудын тоо одоогоор тодорхойгүй байна.
Цагаан будаа. 6. Лойдын дөрвөн морины асуудал |
Самбарыг хэд хэдэн зүссэний дараа үүссэн хэсгүүдийг шилжүүлэхийг зөвшөөрч, дараагийн зүсэлт нь нэг биш, харин хэд хэдэн хэсгийг нэг дор огтолж болно. 64 ширхэг самбарын зайг (1×1 квадрат) авахад хэдэн зүсэлт хийх вэ?
Эхлээд бид самбарыг хагасаар нь зүсэж, дараа нь хоёр талыг зэрэгцүүлэн тавиад, хавтанг дөрвөн ижил хэсэгт хуваана. .
Одоо самбарын хэсгүүдийг зөвхөн тусад нь таслахыг зөвшөөрнө үү. Энэ тохиолдолд 64 талбайг авахын тулд хэдэн зүсэлт хийх шаардлагатай вэ?
Дүрмээр бол энэ даалгавар (ялангуяа өмнөхийн дараа санал болгосон бол) тодорхой хүндрэл учруулдаг. Энэ нь бидний сэтгэлгээний зарим нэг инерцитэй холбоотой бололтой. Эцсийн эцэст, 63 зүсэлт шаардлагатай болох нь тэр даруй тодорхой байна! Үнэн хэрэгтээ, зүсэлт бүр хэсгүүдийн тоог нэгээр нэмэгдүүлдэг; Үүний зэрэгцээ, эхний мөчид бид нэг хэсэгтэй (самбар өөрөө), эцсийн мөчид - 64 (самбарын бүх талбар).
Цагаан будаа. 7. Ер бусын самбар дээрх гурван асуудал |
Зураг дээрх даалгаварт. 7a-д та нэг математик, хоёр нь цэвэр шатар гэсэн гурван даалгаврыг гүйцэтгэх хэрэгтэй.
a) самбарыг дөрвөн тэнцүү хэсэгт хуваасан;
б) цагаан нүүхэд хар хааныг хамгийн дөт замаар матлах;
в) хар хааныг хамгийн богино хугацаанд матлах; хар нүүж байхад үнэнч хүмүүс хамтран тоглодог).
Шийдэл: a) самбарыг хэрхэн огтлохыг зурагт үзүүлэв. 7б; б) Цагаан хөдлөхөд 12 дахь нүүдэл дээр мат өгөгдөнө. 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4 checkmate (хар хааны бүх нүүдлийг албадан хийдэг бөгөөд өгдөггүй); в) 1-ийн дараа зөв тоглосноор ... Ke6-e7 матыг олох боломжгүй, учир нь хар хаан e8 - 2. Be1-b4+ Ke7-e8 дээр нуугдаж, харанхуй дөрвөлжин бишоп нь a3 - e7 диагональыг орхихоос өөр аргагүй болно. мухардмал байдалд орох аюулын улмаас. Гэсэн хэдий ч, хэрэв Блэк хамтран тоглодог бол (Цагаан матад туслах) зорилгодоо ердөө гурван нүүдэлд хүрнэ:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Be4-d5 анд.Манай хавтангийн хэд хэдэн талбарыг үржүүлэхэд ашигладаггүй, гэхдээ тэдгээрийг хассан бол хавтанг огтлох асуудал гарахгүй.
Цагаан будаа. 8. Шатрын самбарыг огтлох парадокс: a) 8×8 = 64; б) 13×5 = 65 |
Одоо шатрын самбарыг огтлохтой холбоотой нэгэн алдартай парадоксыг авч үзье. Зурагт үзүүлсэн шиг бид самбарыг дөрвөн хэсэгт хуваасан. 8, a (энэ тохиолдолд түүний талбайг будах нь бидний хувьд ашиггүй) бөгөөд үүссэн хэсгүүдээс бид тэгш өнцөгтийг нэмнэ (Зураг 8, b). Самбарын талбай нь 64, үүссэн тэгш өнцөгтийн талбай нь 65. Тиймээс самбарыг огтлох үед хаа нэгтээгээс нэг нэмэлт талбар гарч ирэв!
Парадоксын шийдэл нь бидний зурсан зургууд бүхэлдээ үнэн зөв биш юм (бид алдааг нуухын тулд зориудаар бүдүүн зураас зурсан). Зураг дээрх зургийг болгоомжтой хийснээр. 8б-т тэгш өнцөгтийн диагоналын оронд алмааз хэлбэртэй, бага зэрэг сунасан дүрс гарч ирэх бөгөөд талууд нь бараг нийлсэн мэт харагдах болно. Энэ зургийн талбай нь "нэмэлт" нэгжтэй тэнцүү байх болно.
Зууны эхэн үеийн математикийн алдартай дэлгэрүүлэгч Е.Игнатьев янз бүрийн томьёо гаргаж авах боломжийг олгодог "шатрын самбарын арга"-ыг санаачилсан. Бид энэ сэдвээр хоёр энгийн жишээ өгдөг.
Эхний n натурал тооны нийлбэрийг "даамын самбарын арга" ашиглан олъё. Үүнийг хийхийн тулд самбар дээр (n + 1) × n (9-р зураг, a n = 8) бид эхний босоо хэсгийн бүх талбарыг, хоёр дахь босоо талын бүх талбарыг (дээд талынхаас бусад), гурав дахь босоо (хоёр дээд хэсгээс бусад) г.м., эцэст нь - доод талбар nthбосоо. Үүний үр дүнд манай самбар дээрх цагаан ба хар талбарууд тэнцүү байх болно, тухайлбал 1 + 2 + ... + n. Бүхэл бүтэн самбар нь n (n + 1) талбараас бүрддэг тул бид олж авна
2 (1 + 2 + … + n) = n(n + 1),
Эндээс арифметик прогрессийн нийлбэрийн сайн мэддэг томьёог дагадаг.
1 + 2 + … + n = n(n + 1)/2.
Одоо дараах томъёог баталъя.
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Үүнийг хийхийн тулд самбарыг (2n + 1) × (2n + 1) аваад, зурагт үзүүлсэн шиг хэд хэдэн талбарыг хараар будна. 9, 6 (n = 5 тохиолдолд). Мэдээжийн хэрэг, хар хэсэг бүр (1 + 2 + ... + n) талбаруудыг агуулдаг. Төв талбайг харгалзахгүйгээр бид энд дөрвөн ижил цагаан, хар хэсэг байна. Шаардлагатай томьёо нь манай самбар нь (2n + 1)² талбаруудыг агуулж, төв талбар, найман ижил хэсгээс (дөрвөн цагаан, дөрвөн хар - Зураг 9б) бүрдэнэ.
Парадоксыг тайлах, мөн "шатрын самбарын арга" -тай танилцахдаа самбарыг өөрөө алаг цаас эсвэл ширээгээр аюулгүйгээр сольж болно. Ийм объектуудтай холбоотой маш олон асуудал байдаг, гэхдээ тэдгээрийг нарийвчлан авч үзэх нь биднийг шатраас хэтэрхий холдуулах болно.
Бүлгийн төгсгөлд бид Пифагорын теоремын шатрын самбар дээрх нэг хуучин нотолгоог толилуулж байна. Зурагт үзүүлсэн шиг самбар дээр дөрвөлжин зур. 10, а. Самбар нь энэ дөрвөлжин ба дөрвөн тэгш өнцөгт гурвалжинд хуваагдана. Зураг дээр. 10, 6-д бид ижил дөрвөн гурвалжин, мөн хоёр квадратыг харж байна. Тиймээс гурвалжин хоёулаа ижил талбайг эзэлдэг. Тиймээс гурвалжингүй самбарын үлдсэн хэсгүүд нь ижил талбайг эзэлдэг, Зураг дээр. 10,a - нэг квадрат, зурагт. 10б - хоёр. Том дөрвөлжин нь тэгш өнцөгт гурвалжны гипотенуз дээр баригдсан бөгөөд жижиг квадратууд нь түүний хөл дээр байрладаг тул "Пифагорын өмд бүх чиглэлд тэнцүү байна"!
Мэдээжийн хэрэг, хатуухан хэлэхэд бидний үндэслэл нь Пифагорын теоремыг нотлохгүй (зөвхөн тодорхой тохиолдлыг судалсан), гэхдээ зөвхөн үүнийг дүрслэн харуулах болно. Гэхдээ ийм нотолгоо нь шатрын самбар ашиглахгүйгээр явагддаг - ямар ч тэгш өнцөгт гурвалжны хувьд та ижил төстэй байдлаар эвдэрсэн квадратыг сонгож болно.
Энэ шийдэл нь Т.Саатигийн "Бүтэн тоон оновчлолын аргууд ба холбогдох экстремаль асуудлууд" номонд өгөгдсөн (М., "Мир", 1973).
С.Голомб. Полиомино. М., Мир, 1974.
Үүнийг А.Сойфер "Алаг самбар ба полимипо" өгүүлэлд нотолсон ("Квант", 1972, No11); хэд хэдэн шинэ полиомино бодлогууд бас энд өгөгдсөн.
Э.Игнатьев. Авьяаслаг, эсвэл хүн бүрт зориулсан арифметикийн хүрээнд. Ном. 1 - 3. M. - Pg., Госиздат, 1923.
6. Хайрцагт 235 шүдэнз байна. Хоёр тоглогч тэднийг ээлжлэн авдаг. Нэг нүүдлээр та 1-ээс 6 шүдэнз авах боломжтой. Тоглогч ялна
сүүлийн тоглолтыг авч байна. Зөв тогловол хэн хожих вэ?
62
7. 8х8 хэмжээтэй самбараас булангийн дөрвөлжин зүсэгдсэн. 1×3 хэмжээтэй тэгш өнцөгт хавтанг байрлуулах боломжтой юу?
8. 30 тоглолтоос хоёр тоглогч өөрийн үзэмжээр 1-ээс авна
6 хүртэлх тоглолт. Сүүлийн тоглолтыг авсан хүн ялна.
9. Гурван овоолсон чулуу байна. Муж бол тооны гурвалсан тоо юм
(х
1
, x
2
, x
3
), энд x i
- i-р овоолго дахь чулуунуудын тоо. Нүүдэл гэдэг нь овоолгын чулууны тоотой тэнцэх хэмжээний чулууг овооноос овоолго руу шилжүүлэх үйл ажиллагаа юм. Анхны төлөвөөс (11, 7, 6) төлөвийг (8, 8, 8) авна.
10. Дөрвөн шулуун шугамыг ашиглан тойргийг хамгийн их тооны хэсэгт хуваа.
11. Грекийн загалмайг хоёр шулуун шугамаар хайчилж ав
үүссэн хэсгүүдээс нэг тал нь нөгөөгөөсөө хоёр дахин их тэгш өнцөгт үүсгэх.
12. 9-д 12 литрийн багтаамжтай шингэн ба хоосон савнууд байдаг
ба 5 л. Яг 6 литрийг хэмжих шаардлагатай. 12 литрийн нөөцөөс ийм савнуудаар хэдэн литрийг хэмжиж болох вэ?
13. (0, 1, 2) -аас n урттай дарааллын тоог тодорхойл.
дараалсан хоёр нэгж байхгүй.
14. 10х10 квадратыг маягтын дүрсээр бүрхэх боломжтой юу
15. Маягтын дүрсээр 10х10 квадратыг бүрхэх боломжтой юу
63
16. Хэлбэрийн дүрс бүхий хайчлагдсан булангийн нүдээр 8х8 квадратыг бүрхэх боломжтой юу?
17. Дөрвөлжин зүссэн 8х8 хэмжээтэй шатрын самбарыг дүрсээр хучих боломжтой юу?
18. Хэлбэрийн хэсгүүдээр сийлсэн булангийн тор бүхий шатрын тавцан тавих боломжтой юу
19. Эзнийхээ эзгүйд өөр хэн нэгний баатар(ууд)-тай нэг эрэгт байх боломжгүй бол дөрвөн хос хүлэг баатрыг хоёр хүний завины тусламжтайгаар гатлах боломжтой юу?
20. n тооны дараалалгүй хамгийн бага хоёр тоог олох алгоритмыг боловсруул.
21. Ширээн дээр хэвтэж буй 27 тоглолтоос хоёр тоглогч ээлжлэн дор хаяж нэг, дөрөвөөс илүүгүй тоглолт авдаг. Тоглолтын төгсгөлд тэнцүү тооны тоглолттой хүн ялагч болно. Эхний тоглогчийн тоглоомын алгоритмыг боловсруулах.
64
22. Тоглоомын хоёр оролцогч 1-ээс 10 хүртэлх дугаарыг ээлжлэн дууддаг.
Тоглогч дугаар руу залгахдаа үүнийг аль хэдийн байгаа тоонуудын нийлбэрт нэмнэ (эхний дугаар руу залгахад тоглогч үүнийг тэг дээр нэмнэ). 100 оноо авсан тоглогч ялна.
Эхний тоглогчийн тоглоомын алгоритмыг боловсруулах.
23. Асуултуудын хамгийн бага тоог олох (боломжтой хариултууд:
"тийм", "үгүй") нуугдмал 5 оронтой тоо, хэрэв эхний гурван орны нийлбэр нь 17 бол.
24. Асуултуудын хамгийн бага тоог олох (боломжтой хариултууд:
"тийм", "үгүй") хоёр ба дөрөв дэх цифрүүдийн нийлбэр нь 7 бол далд 4 оронтой тоо.
25. 100 рублийг хэдэн аргаар сольж болох вэ? зоос
5, 10, 20, 50 рубль үү?
26. Эхний дөрвөн оронтой тооны нийлбэр нь 26, сүүлийн хоёрын нийлбэр нь 14 байх зургаан оронтой тооны тоог рекурсив аргаар тооцоол.
27. Эхнийх нь 7, хоёр дахь нь 7-аас хэтрэхгүй таван гишүүнээр 37 тооны хуваалтын тоог рекурсив аргаар тооцоол.
- 5, гурав, дөрөв дэх нь багцаас утгыг авна
{5, 6, 7, 8}.
28. Эхний дөрвөн тооны нийлбэр нь 21, сүүлийн таван тооны нийлбэр нь 19 байх долоон оронтой тооны тоог рекурсив аргаар тооцоол.
29. Эхнийх нь 7-оос хэтрэхгүй дөрвөн гишүүнээр 27 тооны хуваалтын тоог рекурсив аргаар тооцоол.
хоёр дахь нь 8, гурав, дөрөв дэх нь олонлогоос утгыг авдаг (3, 5, 7).
30. Эхний гурван оронтой тоо нь 21, сүүлийн гурван цифр нь 12 хүртэл байх таван оронтой тооны тоог рекурсив аргаар тооцоол.
65
31. Нэг ба гурав дахь цифрийн нийлбэр нь 12, үлдсэн тавын нийлбэр нь 19 байх долоон оронтой тооны тоог рекурсив аргаар тооцоол.
32. Рекурсив аргаар тооцоол
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
a n−5
б
−(n+3)
33. Эхний дөрвөн цифрийн нийлбэр нь 17, сүүлийн гурвын нийлбэр нь 16 байх долоон оронтой тооны тоог рекурсив аргаар тооцоол.
34. 17-ын тооны хуваалтын тоог дөрвөн гишүүнээр тооцож, эхнийх нь 4-өөс хэтрэхгүй, хоёр дахь нь 8, гурав, дөрөв дэх нь (3, 4, 8) утгыг авна.
35. Эхний дөрвөн тооны квадратын нийлбэр нь 17, сүүлийн хоёрын квадратын нийлбэр нь 16 байх долоон оронтой тооны тоог рекурсив аргаар тооцоол.
36. Эхнийх нь 8-аас хэтрэхгүй дөрвөн гишүүнээр 25-ын тооны хуваалтын тоог рекурсив аргаар тооцоол.
хоёр дахь нь 3, гурав дахь, дөрөв дэх нь багцаас утгыг авдаг (2, 5, 9).
37. Самбар дээр N дэгээ байрлуулах тоог рекурсив аргаар тооцоол
N × N нь дэгээнүүд нь диагональуудын аль алиных нь хувьд тэгш хэмтэй бөгөөд бие биен рүүгээ дайрдаггүй.
38. Хоёр зэргэлдээх элемент дутуу байгаа n элементийн хоёртын дарааллын тоог рекурсив аргаар тооцоол.
39. N × M тор өгөгдсөн:
66
М
Н
А
Б
А-аас В хүртэлх замын тоог рекурсив аргаар тооцоол. Зам гэдэг нь зүүнээс баруун тийш, доороос дээш чиглэсэн сүлжээний дагуух хөдөлгөөнүүдийн дараалал юм.
40. a тоонууд өгөгдсөн
1
, . . . , a n
тодорхой дарааллаар. Бүтээгдэхүүнийг тооцоолохын тулд a
1
·. . .a n
хүчин зүйлсийн дарааллыг хадгалахын зэрэгцээ хүчин зүйлсийн хооронд хаалт хийх олон арга байдаг. Хаалт байрлуулах аргын тоог рекурсив байдлаар тооцоол.
41. Эхний таван цифрийн нийлбэр нь 29, сүүлийн гурван цифрийн нийлбэр нь 21 байх 8 оронтой тооны тоог рекурсив аргаар тооцоол.
67
3
. алгоритмын шинжилгээний аргууд
3.1. Алгоритмын ангиуд
Өмнөх хэсгүүдэд бид алгоритм бүтээхэд ашиглаж болох өөр өөр аргуудыг авч үзсэн. Шийдлийг олохын тулд энэ шийдлийн үр нөлөөг шинжлэхийн тулд янз бүрийн таамаглал дэвшүүлж, аль хэдийн мэдэгдэж байсан бусад алгоритмуудыг ашиглаж, асуудлын нөхцөлийг дахин боловсруулж болно. Та тодорхой шийдэлтэй ижил төстэй асуудлуудыг хайж олох бөгөөд энэ шийдлийг ашиглан шаардлагатай асуудлын алгоритмыг олох боломжтой.
Гэсэн хэдий ч шийдвэрлэх арга зам нь олдсон тодорхой асуудал маш олон байна. Зарим хязгаарлалт, нөхцлөөр шийдэгдээгүй эсвэл шийдэгдээгүй олон ажлууд бий. Бүхэл бүтэн багц асуудлуудын дунд ижил төстэй асуудлуудыг хайж олох, одоо байгаа шийдлүүдийг "тохиромжтой" байдлаар нь үнэлэх нь хэцүү, цаг хугацаа шаардсан, үргэлж шийдэгддэггүй асуудал байж болно. Нийтлэг асуудал, шийдвэрлэх нийтлэг арга, арга барилаар нэгтгэсэн асуудлын ангиллыг тодорхойлохыг хичээж, дараа нь шийдвэрлэх шаардлагатай бидний тодорхой асуудлыг аль ангид хамааруулж болохыг хайж олох нь илүү ашигтай бөгөөд үр дүнтэй байх болно. Мэдээжийн хэрэг, ийм ангиуд хэтэрхий олон байх ёсгүй, гэхдээ нөгөө талаас хэт цөөхөн байх ёсгүй, ингэснээр тус бүр нь шинэ даалгаварӨөр бусад асуудлыг шийдвэрлэхэд ашиглах боломжгүй шинэ ангиа тодорхойл.
Тодорхой ангилалд хамаарах асуудлын жишээ болгон хуурамч зоосыг тодорхойлох алдартай асуудлыг авч үзье.
Даалгавар 3.1 (тай холбоотой асуудал хуурамч зоос). n зоос байна,
тэдгээрийн дунд нэг хуурамч байж болно. Хуурамч зоос нь жингээсээ ялгаатай бөгөөд хоёр аягатай жинлүүр бидний мэдэлд байна. Хуурамч зоосыг хамгийн бага жингээр тодорхойлох эсвэл тогтоох шаардлагатай.
Хуурамч зоос байдаггүй.
68
Шийдэл. Хуурамч зоосны асуудлыг Sec-д шийдсэн. 2.2,
Харин дараа нь хуурамч зоос заавал хөнгөн байх нь тодорхой болсон. Одоо илүү ерөнхий тохиолдолд энэ асуудлыг шийдэхийг хичээцгээе. Энэ асуудлыг шийдэх аливаа шийдэл (заавал оновчтой биш)
жинлэх дараалал гэж ойлгож болно. Гэхдээ аль ч шатанд жинлэх зоосыг сонгохдоо ямар зоос ашигласан, өмнөх үе шатуудад жинлэлтийн үр дүнгээс шалтгаална гэдэг нь ойлгомжтой. Бид жинлэх дарааллыг дараах байдлаар дүрслэх болно. Бид зооснуудыг дахин дугаарлаж, тэдгээрийг S = (1, 2, . . ., n) олонлогоор тодорхойлно. Тэнцвэрийн зүүн ба баруун талд жинлэсэн зоосны тооны багцыг S гэж тэмдэглэж болно.
Л
болон С
Р
тус тус. С сетийн үндсэн шинж чанарууд л байвал жинлэх нь утга учиртай болох нь тодорхой байна
Л
болон С
Р
таарах, өөрөөр хэлбэл. Жин болгонд ижил тооны зоос байдаг. Жинлэлтийг ":" тэмдгээр тэмдэглэнэ, дараа нь жин бүрийг жинлэнэ
(С
Л
) : (С
Р
) гурван боломжит үр дүн байдаг. Маш олон зоос
С
Л
илүү хөнгөн, хүнд эсвэл S багцтай ижил жинтэй байж болно
Р
. Дараа нь бид эдгээр жинлэлтийн үр дүнг дараах байдлаар тэмдэглэнэ
"" эсвэл "=", тус тус. Дөрвөн зоосны жингийн жишээг Зураг дээр үзүүлэв. 3.1. Зууван нь жинг, дөрвөлжин нь үр дүнг илэрхийлж, хуурамч зоосны дугаар, бусдаас хөнгөн эсвэл хүнд эсэхийг илтгэнэ.
Хуурамч зоосгүй тохиолдлыг "0" гэж тэмдэглэсэн бөгөөд зурсан квадратууд нь тохиолдох боломжгүй тохиолдлуудад тохирч байна.
Бид асуудлыг шийдвэрлэхэд шаардагдах жингийн хамгийн их тоог тооцоолох болно, i.e. хамгийн муу хэрэг. Зураг дээрээс харж болно. 3.1, асуудлыг хамгийн муу тохиолдолд 3 жинлэхэд шийддэг. Хамгийн сайн тохиолдолд ч гэсэн бидэнд дор хаяж 2 хэрэгтэй гэдгийг анхаарна уу
жинлэх. Илүү сайн үр дүнд хүрч чадах уу?
Зураг дээр. 3.1-д дөрвөн зоосыг жинлэх асуудлыг шийдэх өөр нэг шийдлийг танилцуулж байна. Эхний алхамд бид хоёр зоос биш, харин бүх зоосыг хоёр багц болгон хуваана. Үүний үр дүнд бид хамгийн сайндаа зөвхөн нэг жинлэх шаардлагатай болсон.
гэхдээ хамгийн муу тохиолдолд жингийн тоо дахин 3 байна.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4 Т
4 л
3 Т
3 л
(1) : (4)
2 Т
1 л
(1) : (4)
2 л
1 Т
=
=
=
>
>
>
>
>
=
=
Цагаан будаа. 3.1. Хуурамч зоосны асуудлыг шийдэж байна
Эхний жинлэх сонголтоос ялгаатай нь гэдгийг анхаарна уу.
Зурагт үзүүлэв. 3.1, хоёр дахь хувилбарт бид жинлэлтийн схемийг тодорхойлсон төдийгүй хуурамч зоос нэр дэвшигчдийн шинэ ойлголтыг нэвтрүүлсэн. Үнэхээр эхний жинлэлтийн үр дүнг авч үзье, (1, 2) : (3, 4). (1, 2) L гэж үзье
= (1, 2) ба S
Р
= (3, 4). Дараа нь
С
Л
Р
. Үүний үр дүнд хуурамч зоос нь бусад бүх зоосоос хөнгөн эсвэл хүнд эсэхийг дүгнэх боломжгүй,
мөн энэ нь ямар багцад байна. Гэсэн хэдий ч үүнийг таамаглаж болно
(тэр ч байтугай илүү нарийвчлалтай - үүнийг маргаж болно) хэрэв хуурамч зоос нь S багцад хамаарна.
Л
, тэгвэл хуурамч зоос нь бусдаас хөнгөн байвал бид ийм багцыг L үсгээр тэмдэглэдэг. Манай тохиолдолд 1 эсвэл 2 дугаартай зоос хуурамч бол жинхэнэ мөнгөнөөс хөнгөн байна. Хуурамч зоос бол 3 эсвэл
4, дараа нь тэдгээр нь бодит хүмүүсээс илүү хүнд байна, бид T үсгээр харгалзах багцыг тэмдэглэнэ. Зураг дээр. 3.2 Хөнгөн, хүнд хэлбэрийн хуурамч нэр дэвшигчдийг модны ирмэг дээр тэмдэглэсэн тэмдэгээр тэмдэглэнэ.
Зоосыг сонгох боломжит схемүүдийг үргэлжлүүлэн эрэмбэлэх замаар жинлэлтийн оновчтой тооны талаархи асуултанд хариулж болох нь ойлгомжтой. Зоосны тоо хязгаарлагдмал байдаг тул эрт орой хэзээ нэгэн цагт ийм тооллого хийж болно. Одоохондоо олж авсан хоёр шийдэлд анхаарлаа хандуулж, тэдний өгсөн зүйлийг шинжлэхийг хичээцгээе
70
(1.2) Л
(3.4) Т
(1.2) Т
(3.4) Л
(1,2) : (3,4)
(3) : (4)
4 Т
3 Т
(1) : (2)
1 л
=
=
>
>
>
=
0 2 л
(3) : (4)
3 л
4 л
(1) : (2)
2 Т
=
>
>
=
1 Т
Цагаан будаа. 3.2. Асуудлыг шийдэх ерөнхий хандлагын үүднээс хуурамч зоосны асуудлыг шийдэх өөр нэг шийдэл.
Мэдэгдэж байгаагаар зоосыг жинлэх аливаа стратегийг гурвалсан эсвэл гурвалсан мод ашиглан дүрсэлж болно. Өөрөөр хэлбэл, авч үзэж буй асуудал нь асуудлын ангилалд хамаарна.
гурвалсан модоор дүрсэлсэн. Асуудлын ийм ангилал нь тодорхой шийдэл бүрийг биш, харин модны мэдэгдэж буй шинж чанарт үндэслэн бүх шийдлүүдийг шинжлэх боломжийг олгодог.
Тиймээс давталт дууссан боломжит арга замуудЖин гэдэг нь үнэн хэрэгтээ янз бүрийн гурвалсан модыг хайх явдал бөгөөд эдгээрийн дотроос мэдээжийн хэрэг маш олон байдаг. Нөгөөтэйгүүр, тухайн асуудлыг шийдвэрлэхдээ энэ ангид хамаарахыг ашиглан ерөнхийдөө юу хүрэх боломжтойг тодорхойлохыг хичээцгээе.
Зураг дээрээс. 3.1 ба 3.2-оос харахад модыг ашиглан жинлэх дарааллыг дүрслэн үзэхэд бид жин тус бүрийг навч биш (зууван хэлбэрээр дүрсэлсэн) модны оройд хамааруулж, харин үр дүн, түүний дотор боломжгүй зүйл,
модны навчтай тохирч (квадратаар харуулсан). Бүх модны зангилааг түвшингээр нь эрэмбэлж болно,
71
AT
а
=
=
>
AT
а
Тэгээд
Тэгээд
Тэгээд
=
>
AT
а
Тэгээд
Тэгээд
Тэгээд
=
>
AT
а
Тэгээд
Тэгээд
Тэгээд
=
>
AT
а
Тэгээд
Тэгээд
Тэгээд
=
>
AT
а
=
>
AT
а
=
>
AT
а
>
руу
AT
Л
At
0
At
1
At
л
-
1
At
л
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
Г
a =
л
Цагаан будаа.
3.3.
Т
хаврын жингийн мод
72
тэдгээр. модны үндсээс хол зайд. Түвшингийн дугаар нь орой руу хүрэхийн тулд үндэснээс дамжих ёстой ирмэгүүдийн тоотой тэнцүү байна. өгөгдсөн түвшин(Зураг 3.3). Хэрэв модны гүн нь үндэснээс хамгийн алслагдсан навчны түвшин юм бол энэ утга нь хамгийн муу тохиолдолд жингийн тоотой тэнцүү байна.
Бидний асуудалд хэр олон боломжит үр дүн байна вэ? n зоос бүр нь хуурамч хөнгөн эсвэл хуурамч хүнд зоос болж хувирах ба хуурамч зоос огт байхгүй байж болно.
Тиймээс бид 2n + 1 үр дүнтэй байна. Энэ нь модонд байна гэсэн үг
жинлэлтийн схемд тохирсон байх ёстой
2н + 1 навч. l гүнтэй гурвалсан мод хамгийн ихдээ:
3-аас илүү
би орхидог. Үүнээс бид модны хамгийн бага гүнийг тооцоолж болно
3
л
≥ 2n + 1,
мөн иймээс
l ≥ бүртгэл
3
(2n + 1).
(3.1)
Тиймээс n = 4-ийн хувьд жингийн хамгийн бага боломжит тоо нь 2-оос их буюу тэнцүү байна. Энд бид энэ схемийн жингийн хамгийн бага тоог биш гэсэн үг юм - Зураг дээрх шиг. 3.2, эхний жинлэлтийн дараа асуудлын шийдэл аль хэдийн олдсон тохиолдол байдаг - бид хамгийн муу сонголтыг үнэлдэг, жишээлбэл. өгөгдсөн схемийн жингийн хамгийн их тоо, өөрөөр хэлбэл бид дор хаяж 2n + 1 навчтай бүх модны хамгийн их гүнээс хамгийн бага хэмжээг хайж байна.
Гэсэн хэдий ч тооцоололд (3.1) тэгш байдлыг хангахуйц жинлэх арга байхгүй гэдгийг харуулж байна.
ТЕОРЕМ 3.1
Хуурамч зоосны асуудлын хамгийн муу тохиолдолд жингийн тоог l > log гэж тооцдог.
3
(2n + 1).
Баталгаа. Өмнө дурьдсанчлан, n зоосны хувьд 2n + 1 боломжит үр дүн байдаг. Жин бүр нь гурван боломжит үр дүнтэй байж болох бөгөөд үр дүн бүр өөрийн гэсэн байдаг
73
цаашид жинлэх схем. Үүний зэрэгцээ, схем нь сүүлчийн жинлэлтийн үр дүнг харгалзан өөрийн боломжит үр дүнгийн тоотой байдаг. Эхний жинлэхэд |С
Л
| = |С
Р
| = k, өөрөөр хэлбэл.
Нэг хайруулын тавган дээр к зоос, нөгөө талд нь к зоос ашигладаг.
Энд k ≤ n/2 . Хэрэв нэгэн зэрэг С
Л
Р
, дараа нь С-ийн зоос
Л
бид хөнгөн хуурамч зоос, С-ийн зоосыг нэр дэвшигчдийг зарлаж байна
Р
- Хуурамч хүнд зоосны нэр дэвшигчид. Энэ замаар,
Эхний жинлэлтийн үр дүнд 2к үр дүн гарах боломжтой.
Үүний нэгэн адил С
Л
>С
Р
2к өөр үр дүн гарах боломжтой. Тиймээс С
Л
=С
Р
Үлдсэн 2n + 1 - 4k үр дүн боломжтой.
Хэрэв тэгш байдал (3.1) -д байгаа бол энэ нь гурвалсан мод бүрэн бүтэн, бүх навч нь l-р түвшинд байна гэсэн үг юм.
Гэхдээ үүний тулд жинлэх бүрийн дараа боломжит үр дүнг гурван салбар, тэгш байдалд жигд хуваарилах шаардлагатай.
2k = 2n + 1 - 4k,
2k үргэлж тэгш тоо байдаг тул боломжгүй юм
2n + 1 - 4k нь үргэлж сондгой байдаг.
Теорем 3.1-ийн нотолгоонд нэгэн чухал санааг ашигласан:
Жинлэх модыг оновчтой, эсвэл ядаж аль болох оновчтой болгохын тулд үр дүнг жин бүрийн бүх үр дүнд жигд хуваарилах шаардлагатай.
Тиймээс бид энэ асуудлыг асуудлын ангилалд хамааруулж, хуурамч зоосны асуудлын хамгийн муу жингийн тооцоог олж авлаа.
гурвалсан модоор дүрсэлсэн. Одоо бага зэрэг өөрчлөгдсөн асуудлыг авч үзье.
Бодлого 3.2 (стандарт байгаа тохиолдолд хуурамч зоостой холбоотой асуудал). n зоос байдаг бөгөөд тэдгээрийн дотор нэг хуурамч, бас нэг зоос байж болох бөгөөд энэ нь жинхэнэ гэдгийг нь баттай мэддэг. Хуурамч зоосыг хамгийн бага жингээр тодорхойлох эсвэл хуурамч зоос байхгүй эсэхийг тогтоох шаардлагатай.
74
Шийдэл. Энэ асуудал нь өмнөх асуудлаас нэмэлт лавлагаа зоос байгаагаараа ялгаатай боловч энэ нэмэлт зоос нь (3.1)-ийн тэгш байдлыг хангасан оновчтой жингийн модыг барих боломжийг олгодог. n l-ээр тэмдэглэнэ
тэгш байдал хангагдсан тоо
3
л
= 2н л
+ 1.
(3.2)
Теорем 3.1-ийн өмнөх асуудлыг авч үзэхэд бид дараахь зүйлийг олж авсан: (3.1) тэгш байдлыг хангахын тулд жинлэх мод бүрэн байх ёстой. Тиймээс, хэрэв l түвшний ийм оновчтой модыг барих боломжтой бол n l-ийн хувьд l жингийн схемийг зааж өгнө.
зоос. Дараахь хамаарал үнэн болохыг анхаарна уу.
н л
= 3nl−1
+ 1.
(3.3)
Учир нь n
0
= 0-д (3.2) бид 3 0 тэгш байдлыг олж авна
= 2 0 + 1,
тэгвэл эндээс (3.3)-ыг ашиглан n-ийг авч болно
1
= 1, n
2
=
4, n
3
= 13 гэх мэт. Шийдэл (3.2) нь дараалал юм
0, 1, 4, 13, 40, . . ..
Тиймээс (3.2) тэгш байдал биелэх үед n олонлог
l зоосыг n l−1-ээр тэнцүү гурван хэсэгт хуваана
зоос, нэг зоос үлдсэн хэвээр байна. Жинлэх явцад үүсч болох янз бүрийн нөхцөл байдлыг авч үзье.
Схем 1. Жинлэхийн эхэнд бид n i байна
зоос, хаана n i
зарим i-ийн хувьд (3.3) дараалалд хамаарна. n i−1-ийг тавья
зоос, хаана n
би
= 3n i−1
+ 1,
Дараа нь жингийн зүүн талд лавлагаа зоос, үлдсэн n i−1-ийн нэгийг нэмнэ.
+ 1 зоос. Жигнэсэн олонлогуудыг өмнөх шигээ S гэж тэмдэглэ
Л
болон С
Р
Одоо жинлэсний үр дүнд С
Л
=С
Р
. Жишиг зоос жинлэхэд оролцсон тул хуурамч зоос байгаа бол ашиглагдаагүй n-ийн тоонд багтах нь илт байна.
i−1
зоос, мөн асуудал n i−1-тэй холбоотой асуудал болж буурсан
зоос. Хаана
75
Жинлэсний үр дүнд бид 2n i−1 боломжтой хэвээр байна
+ 1 =
3
i−1
үр дүн. Одоо С
Л
Р
. Энэ нь хуурамч зоос нь S багцад байгаа гэсэн үг юм
Л
мөн үүнтэй зэрэгцэн бусдаас хөнгөн, эсвэл багц S
Р
тэгээд бусадтай харьцуулахад хүнд байна.
Үүнээс гадна n i−1 байна
сэжигтэй цайвар зоос ба n i−1
+ 1 сэжигтэй хүнд ба энэ нь дахин 2n i−1-ийг өгнө
+ 1 = 3
i−1
боломжит үр дүн.
Эцэст нь хэлэхэд С
Л
>С
Р
. Дараа нь бидэнд n i−1 байна
хүнд зоосны нэр дэвшигчид ба n i−1
Уушигны хувьд +1 нэр дэвшигч, нийт 2n i−1
+1 =
3
i−1
үр дүн. Тиймээс, анхны жинлэлтийн ийм схемээр бид 3-ыг авдаг
i эхний үр дүнг жинлэлтийн үр дүнгийн дагуу жигд хуваарилсан. Жинлэх схемийг жинлэх бүрийн дараа үр дүнг тэнцүү тооны хэсэгт хуваах боломжтой эсэхийг тодорхойлохын тулд жинлэлтийн үр дүнг анхаарч үзээрэй. Мэдээжийн хэрэг, С
Л
=С
Р
Бид ижил асуудалд зөвхөн жижиг хэмжээстэй тулгардаг бөгөөд бид 1-р схемийн дагуу жинлэх ажлыг үргэлж хийж болно, гэхдээ i-ийн бага утгатай.
Схем 2. Одоо С
Л
Р
. Энэ тохиолдолд бид жинлэх стратегийг дараах байдлаар тодорхойлно. Эхний өгөгдөл нь жинлэлтийн дарааллын зарим i алхамд бид 3 байна
би
= 2n i
+ 1 зоос, тэдгээрийн дотор n i
хөнгөн хуурамч нэр дэвшигчид болон н би
+ 1 хүнд нэр дэвшигчид, харин тоо n би
Энэ нь маягтын тоо юм (3.3)
n i
= 3n i−1
+ 1.
Хайруулын тавган дээр n i−1 тавь
хялбар нэр дэвшигчид ба n
i−1
+1 хүнд. Зөвхөн 2n i байдаг тул
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
зоос, жинлэнэ
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
зоос, тэгвэл 2n i−1 хэвээр байна
+ 1 зоос, үүнд n i−1 байна
+ 1
уушиг ба n i−1
хүнд. Хоёр жин дээр ижил тооны хөнгөн, хүнд зоос байгаа тул жин нь тэнцвэргүй байвал
энэ нь n i−1-ийг өгнө
цайвар зоосны нэр дэвшигчид (хөнгөн болсон аяганаас) ба n i−1
Хүнд жинд + 1 нэр дэвшигч (аягатай болсон
76
илүү хүнд). Энэ нь биднийг ижил схемийн анхны өгөгдөлд хүргэдэг
(схем 2), гэхдээ 3
i−1
= 2n i−1
+ 1 зоос. Хэрэв жин нь тэнцвэртэй байвал бид жингүй n i-1-ийн дундаас хуурамч зоос хайх ёстой гэсэн үг юм.
+ 1 уушиг ба n i−1
хүнд зоос, энэ нь схем 3-тай тохирч байгаа нь ойлгомжтой, 2n i−1
+1 үр дүн, жишээлбэл. дахин бүх боломжит үр дүнгийн багцыг гурван тэнцүү хэсэгт хуваана.
Схем 3. Одоо С
Л
>С
Р
. Энэ тохиолдолд бидэнд 3 байна
би
=
2н би
+ 1 зоос, тэдгээрийн дотор n i
+ 1 хөнгөн хуурамч нэр дэвшигчид, мөн n i
хүнд жингийн нэр дэвшигчид. Бүх аргументууд нь 2-р схемтэй төстэй бөгөөд жинлэхдээ n i−1-ийг тавих хэрэгтэй.
+ 1 хялбар нэр дэвшигч, n i−1
хүнд. Хэрэв жин нь тэнцвэргүй байвал энэ нь 3-ыг 3-ын загварыг дахин өгнө
i−1
зоос, эс тэгвээс бид 2-р схемд тохирсон жинлэх нөхцөлийг олж авна. Дахин хэлэхэд бүх тохиолдолд боломжит үр дүнгийн багц нь 2n i−1-ийн гурван тэнцүү хэсэгт хуваагдана.
+ 1.
Тиймээс бид гурван удаа
1 2
3
=
>
=
=
Цагаан будаа. 3.4. Дээр дурдсан хувийн улсын хуурамч зоосны асуудал дахь жинлэх схем ба муж бүрийн жинлэх дүрэм хоорондын шилжилт. Жинлэх үр дүнгээс хамааран бид өөр муж руу шилждэг (эсвэл ижил төлөвт үлддэг), гэхдээ цөөн тооны зоосны хувьд. Жинлэх бүрт боломжит үр дүнгийн тоог жинлэлтийн үр дүнгийн дагуу жигд хуваарилдаг. Муж хоорондын шилжилтийн схемийг зурагт үзүүлэв. 3.4. 27 зоосны жингийн жишээг Зураг дээр үзүүлэв. 3.5.
77
Даалгавар 1: 5 × 5 квадратыг 1 × 2 тэгш өнцөгт (далуу) болгон хувааж болох уу? Даалгавар 2:Эсрэг талын булангийн квадратуудыг 8х8 хэмжээтэй шатрын самбараас таслав. Үлдсэн хэсгийг 1 × 2 тэгш өнцөгт (далуу) болгон хувааж болох уу? Шийдэл:Үгүй Далуу бүр нэг хар, нэг цагаан дөрвөлжин талбайг эзэлдэг бөгөөд самбар дээр өнцөггүй олон тооны хар, цагаан дөрвөлжин байдаг. Даалгавар 3: 10х10 хэмжээтэй самбарын эсрэг талын булангаас 3х3 хэмжээтэй хоёр квадратыг хайчилж авсан.Үлдсэн хэсгийг нь даалуу болгон хайчилж болох уу? Даалгавар 4:Шатрын тавцан дээр ижил тооны хар, цагаан эсүүд байдаг боловч даалуунд хуваагдах боломжгүй холбосон хэсгийг олоорой. Даалгавар 5: 10 × 10 квадратыг 25 хэсэг болгон хувааж болох уу? Даалгавар 6:Шийдэл:Самбарыг даамын самбараар будна. Тэгш тооны хар эсүүд байх бөгөөд тэдгээрийн нэг буюу гурав нь зураг бүрт унана. Даалгавар 7: 10 × 10 квадратыг 25 хэсэг болгон хувааж болох уу? Шийдэл:
Самбарыг дөрвөн өнгөөр будна (зураг харна уу). Зураг бүр өнгө бүрийн нэг нүдийг эзэлдэг бөгөөд эхний болон хоёр дахь өнгөний нүднүүд өөр өөр тоотой байдаг.
Чиглэл: Самбарыг гурван өнгөөр будна.
Даалгавар 12: 6 × 6 × 6 хэмжээтэй шоо дөрвөлжин хэрчиж болох 1 × 1 × 4 баарны хамгийн их тоо хэд вэ? Даалгавар 13:Тэгш өнцөгт нь дүрс болон . Алдагдсан хүмүүсийн нэг, гэхдээ үүнийг сольсон. Шинэ багц нь анхны тэгш өнцөгтийг хамарч чадахгүй гэдгийг батал. Даалгавар 14: 16 × 16 квадратыг 64 1 × 4 тэгш өнцөгт болгон хувааж болох уу, үүнээс 31 нь босоо, үлдсэн 33 нь хэвтээ байх уу? Шийдэл:Дөрөв дэх босоо тэнхлэг бүрийг будна. Даалгавар 15: n × n квадратыг ямар n-д хувааж болох вэ a) ;б)? Шийдэл:Дөрөв хуваагдах n-ийн хувьд.
Даалгавар 16: m × k тэгш өнцөгт нь 1 × n тэгш өнцөгт хуваагдана. m нь n-д хуваагддаг эсвэл k нь n-д хуваагддаг болохыг батал.в) дурын n-ийн хувьд. Шийдэл:
n өнгөөр өнгө.
Даалгавар 17:Дараах нөхцөл хангагдсан тохиолдолд m × n тэгш өнцөгтийг a × b тэгш өнцөгт болгон хувааж болохыг батал.1) m ба n-ийг ka + lb хэлбэрээр илэрхийлнэ (k ба l нь сөрөг бус бүхэл тоо)
2) m ба n нь а-д хуваагдана.
3) m эсвэл n нь b-д хуваагдана.
Даалгавар 18: m × n тэгш өнцөгтийг тэгш өнцөгтийн аль ч зүсэлт дор хаяж нэг даалуутай огтлолцох байдлаар даалуунд хувааж чадвал түүнийг хүчтэй гэж нэрлэдэг. Үүнийг батлах:a) 2 × n тэгш өнцөгт - эмзэг
б) 3 × n тэгш өнцөгт - эмзэг
в) 4 × n тэгш өнцөгт - эмзэг
г) 5х6 ба 6х8 тэгш өнцөгт - хүчтэй
e) хэрвээ m × n тэгш өнцөгт хүчтэй бол m × (n + 2) тэгш өнцөгт ч хүчтэй байна.
е) * 6х6 тэгш өнцөгт - эмзэг
g) Аль тэгш өнцөгт хүчтэй, аль нь хүчтэй биш вэ? Шийдэл:е) Санамж: 6×6 квадратын шугам бүр тэгш тооны даалууг гатлана.
g) 6 × 6-аас бусад бүх m × n тэгш өнцөгт, m,n ≥ 5 тэгш өнцөгт.
Даалгавар 19:Булан нь хэлбэрийн дүрс юм.
a) 5 × 9 тэгш өнцөгтийг булан болгон хувааж болох уу?
б) Талууд нь 100-аас их, талбай нь 3-т хуваагддаг тэгш өнцөгтийг булан болгон хувааж болохыг батал.
в) Аль тэгш өнцөгтийг булан болгон хувааж болох ба аль нь болохгүй вэ?
Даалгавар 20:Булангийн дөрвөлжингүй 2 n × 2 n хавтанг булан болгон хувааж болох уу? Шийдэл:Тиймээ чи чадна. Хуваалтыг индукцийн аргаар бүтээдэг.
Даалгавар 21:Булангийн нүдгүй самбарыг (2n + 1) × (2n + 1) ямар n хувьд босоо болон хэвтээ адил тэгш байдаг даалуунд хувааж болох вэ? Шийдэл:Тэр ч байтугай n.
