Maymun va kokos yong'og'i - The monkey and the coconuts

Bu maqola uchun qo'shimcha iqtiboslar kerak tekshirish. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Resurs manbasi bo'lmagan material shubha ostiga olinishi va olib tashlanishi mumkin. Manbalarni toping: "Maymun va kokos yong'og'i"  – Yangiliklar  · gazetalar  · kitoblar  · olim  · JSTOR (2019 yil dekabr) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Bu maqola ehtimol o'z ichiga oladi original tadqiqotlar. Iltimos uni yaxshilang tomonidan tasdiqlash qilingan va qo'shilgan da'volar satrda keltirilgan. Faqat asl tadqiqotlardan iborat bayonotlar olib tashlanishi kerak. (2019 yil dekabr) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Maymun va kokos yong'og'i a matematik jumboq sohasida Diofantinni tahlil qilish Bu jurnalda beshta dengizchi ishtirok etgan xayoliy qisqa hikoya va a maymun qoziqni ajratadigan cho'l orolida hindiston yong'og'i; muammo asl qoziqdagi kokos yong'og'ining sonini topishdir (fraksiyonel kokos yong'og'iga ruxsat berilmaydi). Muammo murakkab jumboq echuvchilar uchun juda qiyin bo'lganligi bilan mashhur, ammo to'g'ri matematik yondashuv bilan bu echim ahamiyatsiz. Muammo asosiy narsaga aylandi rekreatsiya matematikasi to'plamlar.

Umumiy tavsif

Maymun va hindiston yong'og'i - qoldiq bilan yoki bo'linmasdan, alohida-alohida bo'linadigan miqdorni rekursiv bo'linish yoki qismlarga ajratish kabi tuzilgan butun sonli echimlarni talab qiladigan jumboq muammolari sinfining eng taniqli vakili. qoldiq. Muammo shunchalik yaxshi ma'lumki, butun sinf ko'pincha "maymun va kokos yong'og'i turidagi muammolar" deb nomlanadi, ammo ko'pchilik muammo bilan chambarchas bog'liq emas. Yana bir misol: "Menda tsementning butun soni bor, men ularning qancha ekanligini bilmayman, lekin to'qqizinchi va o'n birinchi qo'shilgandan so'ng, har biri butun funt sterling bilan 3 qopga bo'linib ketdi. Necha funt tsement menda bormi? " Muammolar dastlabki yoki terminal miqdorini so'raydi. Belgilangan yoki nazarda tutilgan - bu echim bo'lishi mumkin bo'lgan eng kichik ijobiy raqam. Bunday muammolarda ikkita noma'lum narsa mavjud: boshlang'ich raqam va terminal raqam, ammo faqat bitta tenglama, ular orasidagi bog'liqlik uchun ifodani algebraik qisqartirish. Sinf uchun umumiy bo'lgan, natijada paydo bo'lgan tenglamaning tabiati, bu ikki noma'lumda chiziqli Diofant tenglamasi. Sinfning aksariyat a'zolari aniq, ammo ba'zilari aniq emas (maymun va kokos ikkinchisidan biri). Tanish algebraik bunday tenglamalarni echish uchun usullar mavjud emas.

Tarix

Bunday muammolar sinfining kelib chiqishi hind matematikiga tegishli Mahavira VI bobda, §131¹⁄₂, 132​¹⁄₂ uning Ganita-sara-sangraha ("Matematikaning mohiyati to'plami"), taxminan 850CE, bu meva va gullarni belgilangan qoldiqlari bilan ketma-ket taqsimlash bilan shug'ullangan.^[1] Bu zamonaviy davrda qayta tiklanishidan oldin 1000 yoshdan oshgan avlodlar muammolarini keltirib chiqaradi. Bo'linish bilan bog'liq muammolar Xitoyning qolgan teoremasi milodiy I asrdayoq Xitoy adabiyotida paydo bo'lgan. Sun Tsu so'radi: 3,5,7 ga bo'linishda 2,3,2 qoldiqlarini qoldiradigan sonni toping. Diofant Aleksandriya milodiy III asrda birinchi bo'lib butun sonli echimlarni talab qiladigan muammolarni o'rgangan. Bunday muammolarni hal qilishda yotadigan eng katta umumiy bo'luvchi uchun Evklid algoritmi yunon geometriyasi tomonidan kashf etilgan. Evklid va unda nashr etilgan Elementlar 300-yilda.

Prof. Devid Singmaster, jumboqlarning tarixchisi, O'rta asrlar davomida unchalik ishonchli bo'lmagan bir qator muammolarni izlaydi va 1700 yillarga qadar Bobil imperatorligiga qadar bir nechta ma'lumotlarga ega. Ular qoziqning qismlarini yoki alohida sonli diskret ob'ektlarni qo'shish yoki olib tashlash va boshida qancha bo'lishi mumkinligini so'rashning umumiy mavzusini o'z ichiga oladi. Shunga o'xshash muammoga keyingi murojaat Jak Ozanam "s Récréations mathématiques et physicues, 1725. Sof matematikada, Lagranj 1770 yilda uni tushuntirib berdi davom etgan kasr teoremasi va uni Diofant tenglamalarini echishida qo'llagan.

Muammoning zamonaviy ta'rifiga yaqin bo'lgan birinchi tavsifi matematik va muallifning kundaliklarida paydo bo'ldi Lyuis Kerol ("Alice in Wonderland") 1888 yilda to'rtta aka-uka tomonidan ketma-ket bo'lingan stol ustidagi yong'oq uyumini o'z ichiga olgan holda, har safar maymunga bittasi berilib, yakuniy bo'linish hattoki chiqadi. Muammo muallifning hech qanday nashr etilgan asarida bo'lmagan, ammo boshqa ma'lumotlarga qaraganda muammo 1888 yilda muomalada bo'lgan. Tez orada deyarli bir xil muammo paydo bo'ldi VW. To'pni to'plash "s Boshlang'ich algebra, 1890. Bunday yaqinlik umumiy manbani taklif qiladi; muammoni tarqatish Kerollning almashinuvi orqali sodir bo'lishi mumkin Bartolomey narxi, matematika professori va Kerrolning do'sti va o'qituvchisi. Muammoning to'rtta versiyasi mavjud edi: ikkita shakl, biri qoldiqlari bilan qolgani, qolganlari nolga teng, lekin bo'linishdan keyin yong'oqlar tashlanadi va ikkita tugatish, bittasi bo'linma qoldiqqa ega, ikkinchisi esa hatto chiqib ketadigan joy (yoki yong'oq yo'q) tashlanadi). Muammo davriy matematiklarning asarlarida zikr qilingan, echimlari, asosan noto'g'ri, bu muammoning o'sha paytda yangi va notanish bo'lganligidan dalolat beradi.

Bo'linishni qoldiq bilan kontseptsiyalashda yordam berish uchun belgilangan ob'ektlar qurilmasi (quyida joylashgan Moviy kokos yong'og'i) birinchi bo'lib 1912 yilda paydo bo'lgan. Norman H. Anning uch kishiga bo'lingan olma qutisini jalb qilish.

Muammo amerikalik roman yozuvchisi va qissa yozuvchisi tomonidan tanilgan Ben Ames Uilyams eski muammoni o'zgartirib, 1926 yil 9 oktyabrdagi sonida "Hindiston yong'og'i" nomli hikoyasiga kiritdi. Shanba kuni kechki xabar.^[2] Bu erda Uilyams tomonidan muammo qanday bayon qilingan (quyultirilgan va o'zgartirilgan):

Besh kishi va maymun orolda halokatga uchradi. Ular birinchi kechani kokos yig'ish bilan o'tkazishdi. Kechasi bir kishi uyg'onib, kokosdan o'z ulushini olishga qaror qildi. U ularni beshta qoziqqa ajratdi. Bitta hindiston yong'og'i qoldi, shuning uchun uni maymunga berdi, keyin o'z ulushini yashirib, qolgan qismini yana bir joyga yig'di va yana uxlab qoldi.

Tez orada ikkinchi bir kishi uyg'onib, xuddi shu narsani qildi. Hindiston yong'og'ini beshta qoziqqa ajratgandan so'ng, bitta kokos qoldi, u maymunga berdi. Keyin u o'z ulushini yashirib, qolganlarini yana bir joyga yig'di va yotoqqa qaytdi. Uchinchi, to'rtinchi va beshinchi odam aynan shu protsedurani bajargan. Ertasi kuni ertalab, ularning hammasi uyg'onganidan so'ng, qolgan kokoslarni beshta teng ulushga bo'lishdi. Bu safar hech qanday hindiston yong'og'i qolmadi.

Asl qoziqda qancha kokos yong'og'i bor edi?

Uilyams hikoyaga javobni kiritmagan edi. Jurnal muammoning javobini so'ragan 2000 dan ortiq xat bilan suv ostida qoldi. Post muharriri, Horas Lorimer, mashhur Uilyamsga: "MAYKNING SEVGISI UCHUN QANDAY KOKONUSTLAR? BU YERGA DUZOQ QO'YING" degan telegrammani o'chirib tashlagan. Uilyams kelgusi yigirma yil davomida echimini so'ragan yoki yangilarini taklif qilgan xatlar olishni davom ettirdi.^[3]

Martin Gardner muammoni 1958 yil aprel oyida namoyish etgan Matematik o'yinlar ustuni yilda Ilmiy Amerika. U Uilyams eskirgan muammoni yanada chalkashroq qilish uchun o'zgartirganligini aytdi. Eski versiyada so'nggi bo'linmada maymun uchun kokos yong'og'i mavjud; Uilyamsning versiyasida ertalab yakuniy bo'lim ham chiqadi. Ammo mavjud tarixiy dalillar Uilyamsning qaysi versiyalarga kirganligini ko'rsatmaydi.^[4] Gardner bir marta o'g'li Jimga bu uning sevimli muammosi ekanligini aytdi,^[5] shu qadar ko'pki, u keyinchalik uni "eng yaxshi ustunlar" to'plamining birinchi bobiga aylantirishni tanladi, Matematikaning ulkan kitobi.^[3] U Maymun va Hindiston yong'og'i "ehtimol eng ko'p ishlangan va kam hal qilingan" Diofantin jumboqidir.^[2] O'sha vaqtdan beri Uilyamsning muammoning versiyasi asosiy mahsulotga aylandi rekreatsiya matematikasi.^[6] Muammoni o'z ichiga olgan asl hikoya to'liq hajmda qayta nashr etildi Klifton Fadiman 1962 yildagi antologiya Matematik Magpie,^[7] bu kitob Amerika matematik assotsiatsiyasi bakalavriat matematikasi kutubxonalari tomonidan sotib olishni tavsiya qiladi.^[8]

Adabiyotda dengizchilar, maymunlar yoki maymun (lar) ga berilgan kokos yong'og'i sonini o'zgartiradigan ko'plab variantlar paydo bo'ldi.^[9]

Yechimlar

1928 yildayoq boshlangan ko'plab echimlar asl muammo uchun ham, Uilyamsning modifikatsiyasi uchun ham nashr etilgan.^{[11][12][13][14]} Modul muvofiqliklari, elaklari va muqobil raqamlar asoslaridan foydalangan holda aqlli va lochin echimlar qisman yoki asosan masalaning rekursiv ta'rifiga asoslanib ishlab chiqilgan bo'lib, bu tuzilma umumiy holatda qo'llanilmaydi. Ikkala versiyaning eng kichik ijobiy echimlari etarlicha katta, chunki sinov va xatolar samarasiz bo'lishi mumkin. Asl muammoni bemalol hal qiladigan salbiy kokoslarning mohirona kontseptsiyasi joriy etildi. Formalistik echimlar Diofantin koeffitsientlariga tatbiq etilgan Evklid algoritmiga asoslangan. Va nihoyat chekli farqlarning hisobi har qanday dengizchilar va asl qoziqda bo'lishi mumkin bo'lgan barcha kokos yong'og'i uchun parametrlangan umumiy echimni beradi. Zamonaviy davrda kompyuterning qo'pol kuchini musbat butun sonlar ustida qidirish tezda echimini topadi.

Muammoning echimini topishdan oldin, ikkita narsani ta'kidlash mumkin. Agar 5, 5 ning 6 ta bo'linmasi berilgan bo'lsa, qoldiqlar bo'lmasa⁶= Qoziqda 15625 kokos yong'og'i bo'lishi kerak; 6-va oxirgi bo'limda har bir dengizchi 1024 kokos yong'og'ini oladi. Kichikroq ijobiy raqam, natijada barcha 6 ta bo'linmalar teng chiqa olmaydi. Bu shuni anglatadiki, muammoga, qoziqqa har qanday 15,625 ko'paytmasi qo'shilishi mumkin va bu muammoning shartlarini qondiradi, shuningdek asl qoziqdagi hindiston yong'og'i soni 15,625 dan kichik bo'ladi, aks holda 15,625 ni olib tashlasak bo'ladi kichikroq echim. Ammo asl qoziqdagi raqam unchalik katta emas, masalan 5 yoki 10 (shuning uchun bu qiyin muammo) - bu yuzlab yoki minglab bo'lishi mumkin. Polinom ildizini taxmin qilishda sinov va xatolardan farqli o'laroq, Diofantin ildizi uchun sinash va xato aniq birlashishga olib kelmaydi. Qaror qanday bo'lishini taxmin qilishning oddiy usuli yo'q.

Asl versiyasi

Asl muammoning ham, Uilyamning versiyasining ham qisqacha tahlili taqdim etildi Martin Gardner u matematik o'yinlar ustunida muammoni aks ettirganda. Gardner asl muammoni echishdan boshlanadi, chunki Uilyamsning o'zgarishiga qaraganda unchalik chalkash emas. Ruxsat bering N asl qoziqning kattaligi bo'lishi va F ertalab 5 ta teng ulushga bo'linishidan so'ng har bir dengizchi tomonidan qabul qilingan kokos yong'og'i soni. Keyin ertalab bo'linishdan oldin qolgan kokoslar soni F· 5 + 1. Agar bu miqdor belgilangan bo'lsa n, oxirgi dengizchi bo'linmasidan oldin qolgan raqam:

${ displaystyle n '= n cdot { tfrac {5} {4}} + 1}$

kecha davomida dengizchining tartibini o'zgartirish. Ammo har bir dengizchi xuddi shu tartibni bajargan; shunday qilib 5 ta rekursiv qator aniqlangan ${ displaystyle n '}$s (almashtirish) ${ displaystyle n}$ bilan ${ displaystyle n '}$ va yangi ishlab chiqarish ${ displaystyle n '}$), ularning beshinchisi va oxirgisi N o'zi, birinchi dengizchi tomonidan bo'linishidan oldin kokos soni. Muvaffaqiyatli ${ displaystyle n '}$s va ${ displaystyle n}$ hosil:

${ displaystyle N = (((((F cdot 5 + 1) cdot { tfrac {5} {4}} + 1) cdot { tfrac {5} {4}} + 1) cdot { tfrac {5} {4}} + 1) cdot { tfrac {5} {4}} + 1) cdot { tfrac {5} {4}} + 1}$

bu Diophantine tenglamasiga kamayadi:^[3]

${ displaystyle 1024N = 15625F + 11529}$

Asosiy teorema bo'yicha ushbu tenglama echimini topadi, agar 11529 raqamining ko'paytmasi bo'lsa Eng katta umumiy bo'luvchi 1024 va 15625. 1024 = 4⁵ va 15625 = 5⁶, shuning uchun ularning GCD 1, va 11529 1 ga ko'paytma, shuning uchun tenglama echilishi mumkin.

Gardnerning ta'kidlashicha, bu tenglamani sinov va xato bilan hal qilish juda qiyin.^[15] Bundan tashqari, u cheksiz ko'p echimlarga ega. Ammo Gardner qiyinligi haqida yanglishdi. Aslida, agar (N, F) bu shunday echim (N + 15625 t, F + 1024 t) har qanday butun son uchun t. Demak, tenglamaning manfiy butun sonlarda echimlari ham mavjud. Bir nechta kichik salbiy sonlarni sinab ko'rishda N = -4 chiqadi va F = -1 bu yechim.^[16] Bu salbiy kokos yong'og'ining bema'ni tushunchasini o'z ichiga oladi; shuning uchun biz eng kichik ijobiy eritmani olish uchun -6 ga 15625 qo'shamiz va 1024 dan -1 ga qo'shamiz (15621, 1023).^[17]

Uilyams versiyasi

Hindiston yong'og'ining salbiy yondashuvi Uilyams versiyasiga taalluqli emas, hech bo'lmaganda juda kichik |N|, shuning uchun yanada tizimli yondashuv zarur.

Elakdan foydalanish

Muammoning tuzilishini kuzatish orqali qidiruv maydonini tobora kattalashib boruvchi omillar ketma-ketligi bilan kamaytirish mumkin, shunda biroz sinov va xatolar echimini topadi. Ertalab bo'linishda har bir erkak tomonidan qabul qilingan kokos yong'og'i sonidan boshlanadigan bo'lsa, qidiruv maydoni ancha kichik bo'ladi, chunki bu raqam asl qoziqdagi raqamdan ancha kichikdir.

Agar F - har bir dengizchi ertalab yakuniy bo'linishda oladigan kokos yong'og'i, ertalab qoziq - 5F, u ham 4 ga bo'linishi kerak, chunki tungi so'nggi dengizchi ertalabki bo'linish uchun 4 ta qoziqni birlashtirdi. Shunday qilib, ertalabki qoziq, raqamga qo'ng'iroq qiling n, 20 ning ko'paytmasi. Oxirgi dengizchi uyg'onishidan oldin uyum 5/4 bo'lishi kerak (n) +1. Agar tunda faqat bitta dengizchi uyg'ongan bo'lsa, unda 5/4 (20) +1 = 26 asl qoziqdagi eng kam kokos miqdori uchun ishlaydi. Ammo agar ikkita dengizchi uyg'ongan bo'lsa, 26 ni 4 ga bo'linmaydi, shuning uchun ertalabki qoziq oxirgi dengizchi uyg'onishidan oldin 4 ga bo'linadigan qoziqni beradigan 20 ga ko'paytirilishi kerak. Shunday qilib, 3 * 20 = 60 ikkita dengizchi uchun ishlaydi: uchun rekursiya formulasini qo'llash n asl qoziqdagi eng kichik kokos yong'og'i sifatida ikki marta 96 hosil beradi. 96 yana 4 marta bo'linadi, shuning uchun uyg'ongan 3 dengizchi uchun qoziq 121 yong'oq bo'lishi mumkin edi. Ammo 121 4 ga bo'linmaydi, shuning uchun 4 dengizchi uyg'onishi uchun yana bir sakrash kerak. Shu nuqtada o'xshashlik ravshan bo'lib qoladi, chunki uyg'ongan 4 dengizchini joylashtirish uchun ertalabki qoziq 60 ga ko'paytma bo'lishi kerak: agar qat'iy bo'lsa, 17 * 60 = 1020 hiyla-nayrang va minimal sonni bajarishi mumkin asl qoziqda 2496 bo'ladi. 5 ta dengizchining uyg'onishi uchun 2496 da oxirgi takrorlash, ya'ni 5/4 (2496) +1 asl qoziqni 3121 kokosga keltiradi.

Moviy kokos yong'og'i

Muammoni oldindan belgilab qo'ygan yana bir qurilma - bu bo'linish jarayoniga oydinlik kiritish uchun qo'shimcha yoki belgilangan narsalardan, bu holda ko'k kokos yong'og'idan foydalanish. Faraz qilaylik, bo'linishdan oldin birinchi dengizchi, 5 ga bo'linishni kafolatlash uchun qoziqqa to'rtta ko'k kokos yong'og'ini qo'shadi (chunki biz buni bilmasak ham, qoldiq $ 1 $ bo'ladi, shuning uchun $ 4 $ qo'shib, qoziqni bo'linadi 5). U qoziqni ajratadi, beshinchisini qo'shimcha (ko'k bo'lmagan) kokos yong'og'i bilan oladi, uni maymunga uloqtiradi, o'z ulushini yashiradi, so'ng qolgan qismini yana 4 ta ko'k kokosni yon tomonga qo'yib qo'yadi. Har bir dengizchi xuddi shunday qiladi. Beshinchi dengizchidan keyin (yoki ertalab bo'linishdan keyin u erda qoldiq bo'lsa), ko'k kokoslar hech kimga tegishli bo'lmagan tomonda qoladi. Asl qoziq 5 marta (yoki ertalab qolgan bo'lsa, 6 marta) bo'linganligi sababli, ko'k kokos yong'og'ini ham qo'shganda, u 5 bo'lishi kerak⁵ (5⁶) kokos yong'og'i. Bu qoziqni 3125-4 = 3121 (15625-4 = 15621) kokosini qiladi. Moviy kokos yong'oqlari "virtual" kokoslar deb hisoblanishi mumkin, ular muammoda hech qanday rol o'ynamaydi, faqat bo'linishni aniqlashga xizmat qiladi.^[18]

5-sonli raqamlash

Oddiy va ravshan echim 5-qismda bo'linishlar va ayirmalar amalga oshirilganda paydo bo'ladi. Birinchi dengizchi o'z ulushini (va maymunnikini) olganda olib tashlashni ko'rib chiqing. N ga ruxsat bering₀, n₁, ... N raqamlarini, asl qoziqdagi hindiston yong'og'ining sonini va s ni ifodalaydi₀, s₁... dengizchilar ulushining S raqamlarini, ikkalasi ham 5-raqamni ifodalaydi. Maymun ulushidan keyin N ning eng kichik raqami endi 0 bo'lishi kerak; olib tashlanganidan so'ng, birinchi dengizchi tomonidan qoldirilgan N 'ning eng kichik raqami 1 bo'lishi kerak, shuning uchun quyidagilar (N va S sonlarining haqiqiy soni noma'lum, ammo ular hozir ahamiyatsiz):

n5n4n3n2n1 0 (N5) lar4s3s2s1s0   (S5) 1 (N ')5)

1 ta hosil olish uchun 0 taglik 5dan chiqarilgan raqam 4 ga teng, shuning uchun s₀= 4. Ammo S (N-1) / 5 bo'lgani uchun va 5 ga bo'linadi₅ shunchaki raqamni o'ng tomonga o'zgartiradi, n₁= s₀= 4. Shunday qilib, endi ayirish quyidagicha ko'rinadi:

n5n4n3n2 4 0 s4s3s2s1 4          1  

Keyingi dengizchi xuddi shu narsani N 'da qilmoqchi bo'lganligi sababli, maymunni tashlaganidan keyin N' ning eng kichik raqami 0 ga teng bo'ladi va shu sababli S 'ning LSD qiymati 4 ga teng bo'lishi kerak; N 'ning keyingi raqami ham 4 bo'lishi kerak. Demak, endi quyidagicha ko'rinadi:

n5n4n3n2 4 0 s4s3s2s1 4        4 1 

N dan qarz olish₁ (hozir 4 ga teng) 3 ta qoldiradi, shuning uchun s₁ 4 bo'lishi kerak, va shuning uchun n₂ shuningdek. Shunday qilib, endi quyidagicha ko'rinadi:

n5n4n3 4 4 0 s4s3s2 4 4        4 1  

Ammo yana bir xil fikr N 'ga nisbatan qo'llanilganidek, N' ga tegishli, shuning uchun N 'ning keyingi raqami 4 ga teng, shuning uchun s₂ va n₃ Shuningdek, 4 ta va boshqalar 5 ta bo'linma mavjud; birinchi to'rtlik keyingi bo'linish uchun qoziqda toq sonli bazani 5 qoldirishi kerak, lekin oxirgi bo'linma juft sonli bazani 5 qoldirishi kerak, shunda ertalab bo'linish juft bo'lib chiqadi (5larda). Shunday qilib, 1da LSD dan keyin N da to'rtta 4 mavjud: N = 44441₅=3121₁₀

Raqamli yondashuv

To'g'ridan-to'g'ri raqamli tahlil quyidagicha bo'ladi: Agar N boshlang'ich raqam bo'lsa, 5 ta dengizchi har biri asl qoziqni shunday o'zgartiradi:

N => 4 (N – 1) / 5 yoki unga teng, N => 4 (N + 4) / 5 - 4.

Ushbu o'tishni 5 marta takrorlash ertalab qolgan raqamni beradi:

N => 4 (N + 4) / 5 - 4

=> 16 (N + 4) / 25 - 4

=> 64 (N + 4) / 125 - 4

=> 256 (N + 4) / 625 - 4

=> 1024 (N + 4) / 3125 - 4

Bu raqam tamsayı bo'lishi kerak va 1024 3125 ga nisbatan nisbatan katta bo'lganligi sababli, N + 4 3125 ga ko'paytma bo'lishi kerak. Bunday kichiklik 3125 ga teng.· 1, shuning uchun N = 3125 - 4 = 3121; ertalab qolgan raqam 1020 ga etadi, bu talab bo'yicha 5 ga teng bo'linadi.

Modulo muvofiqligi

Muammoning rekursiv tuzilishidan to'g'ridan-to'g'ri foydalanib, oddiy qisqacha echimni olish mumkin: har safar kokoslarning beshtaga bo'linishi (ertalab yakuniy bo'linishni chetga surib qo'yish). Har bir bo'linishdan keyin qolgan qoziq ajralmas sonli yong'oqni o'z ichiga olishi kerak. Agar bunday bo'linish bitta bo'lsa edi, demak, bu 5 ga teng· 1 + 1 = 6 bu yechim. Aslida beshta plyusning har qanday ko'paytmasi echimdir, shuning uchun mumkin bo'lgan umumiy formula 5 ga teng· k - 4, chunki 5 plyus 1 ning ko'paytmasi ham 5 minus 4 ning ko'paytmasidir, shuning uchun 11, 16 va boshqalar ham bitta bo'linma uchun ishlaydi.^[19]

Agar ikkita bo'linish bajarilsa, 5 ga ko'paytiriladi· 5 o'rniga 5 = 25 dan foydalanish kerak, chunki 25 ni 5 ga ikki marta bo'lish mumkin. Shunday qilib, qoziqda bo'lishi mumkin bo'lgan hindiston yong'og'i soni k · 25 - 4.k= 21 hosil bo'lgan 1 - bu ketma-ket 5 ga ikki marta bo'linadigan eng kichik musbat son, qoldiq 1. Agar 5 bo'linish bo'lsa, unda 5 ga ko'paytiriladi⁵= 3125 talab qilinadi; eng kichik bunday raqam - 3125 - 4 = 3121. 5 ta bo'linishdan so'ng, 1020 ta hindiston yong'og'i qoldiqlari paydo bo'ldi, ularning soni 5 ga bo'linadi. Aslida, keyin n bo'linmalar, qolgan qoziqning bo'linishini isbotlash mumkin n, muammo yaratuvchisi tomonidan qulay foydalanilgan mulk.

Yuqoridagi dalillarni bayon qilishning rasmiy usuli bu:

Hindiston yong'og'ining asl qozig'i ertalabki oxirgi bo'linishni hisobga olmaganda, qolgan qismi 1 bilan jami 5 marta 5 ga bo'linadi. N = asl qoziqdagi hindiston yong'og'i soni. Har bir bo'linma yong'oq sonini bir xil muvofiqlik sinfida qoldirishi kerak (mod 5). Shunday qilib,

${ displaystyle N equiv 4/5 cdot (N-1)}$ (5-mod) (-1 - maymunga uloqtirilgan yong'oq)

${ displaystyle 5N equiv 4N-4}$ (mod 5)

${ displaystyle N equiv -4}$ (mod 5) (–4 - muvofiqlik sinfi)

Shunday qilib, agar biz modul -4 sinfidagi yong'oqlardan boshlagan bo'lsak, biz -4 modullari sinfida qolamiz. Oxir oqibat biz qoziqni 5 marta yoki 5 ^ 5 ga bo'lishimiz kerak, asl qoziq 5 ^ 5 - 4 = 3121 yong'og'i edi. Qolgan 1020 kokos yong'og'i ertalab soat 5 ga teng ravishda bo'linadi. Ushbu echim asosan muammoning qanday tuzilganligini (ehtimol) o'zgartiradi.

Diofant tenglamasi va eritma shakllari

Ushbu versiya uchun teng Diofant tenglamasi:

${ displaystyle 1024N = 15625F + 8404}$ (1)

qayerda N Hindiston yong'og'ining asl soni va F - bu ertalab yakuniy bo'limda har bir dengizchi tomonidan olingan raqam. Bu avvalgi muammo bo'yicha yuqoridagi tenglamadan shunchaki ahamiyatsiz farq qiladi va halollik bir xil mulohaza bilan kafolatlanadi.

Qayta tartiblash,

${ displaystyle 1024N-15625F = 8404}$ (2)

Ushbu Diofant tenglamasi to'g'ridan-to'g'ri quyidagi echimga ega Evklid algoritmi; aslida, u cheksiz ko'p ijobiy va salbiy davriy echimlarga ega. Agar (x₀, y₀) 1024x – 15625y = 1 eritmasi, keyin N₀= x₀ · 8404, F₀= y₀ · 8404 - bu (2) eritma, ya'ni har qanday eritmaning shakli bo'lishi kerak

${ displaystyle { begin {case} N = N_ {0} +15625 cdot t F = F_ {0} +1024 cdot t end {case}}}$

qayerda ${ displaystyle t}$ har qanday integral qiymatga ega bo'lishi mumkin bo'lgan ixtiyoriy parametrdir.

Reduksionist yondashuv

(1) ning ikkala tomonini 1024 modulidan yuqoriga olish mumkin, shuning uchun

${ displaystyle 1024N = 15625F + 8404 mod 1024}$

Bu haqda o'ylashning yana bir usuli - buning uchun ${ displaystyle n}$ tamsayı bo'lish uchun tenglamaning RHS qiymati 1024 ning integral ko'paytmasi bo'lishi kerak; ushbu mulk RHS dan iloji boricha 1024 ga ko'paytmalarni ajratish orqali o'zgartirilmaydi. Ikkala tomonni 1024 ga ko'paytirib,

${ displaystyle 0 = (15625F-15 cdot 1024F) + (8404-8 cdot 1024) mod 1024}$

ayirish,

${ displaystyle 0 = 265F + 212 mod 1024}$

faktoring,

${ displaystyle 0 = 53 cdot (5F + 4) mod 1024}$

RHS hali ham 1024 ning ko'paytmasi bo'lishi kerak; chunki 53 nisbatan 1024, 5 ga tengF+4 1024 ga ko'paytuvchi bo'lishi kerak. Bunday kichraytmaning eng kichigi 1 ga teng· 1024, shuning uchun 5F+ 4 = 1024 va F = 204. (1) ga almashtirish

${ displaystyle 1024N = 15625 cdot 204 + 8404 Rightarrow N = { frac {3195904} {1024}} Rightarrow N = 3121}$

Evklid algoritmi

Evklid algoritmi juda zerikarli, ammo integral javoblarni talab qiladigan ax + by = c ratsional tenglamalarini echishning umumiy metodologiyasi. Yuqoridagi (2) dan ko'rinib turibdiki, 1024 (2)¹⁰) va 15625 (5⁶) nisbatan sodda va shuning uchun ularning GCDlari 1 ga teng, ammo biz orqaga almashtirish uchun qaytarilish tenglamalariga muhtojmiz N va F ushbu ikki miqdor bo'yicha:

Birinchidan, GCD qolguncha ketma-ket qoldiqlarni oling:

15625 = 15 · 1024 + 265 (a)

1024 = 3 · 265 + 229 (b)

265 = 1 · 229 + 36 (c)

229 = 6 · 36 + 13 (d)

36 = 2 · 13 + 10 (e)

13 = 1 · 10 + 3 (f)

10 = 3 · 3 + 1 (g) (qoldiq 1 15625 va 1024 ning GCD)

1 = 10 - 3 (13-1 · 10) = 4 · 10 - 3 · 13 (tartib (g), (f) dan 3 ga almashtiring va birlashtiring)

1 = 4 · (36 - 2 · 13) - 3 · 13 = 4 · 36 - 11 · 13 ((e) dan 10 ga almashtiring va birlashtiring)

1 = 4 · 36 - 11 · (229 - 6 · 36) = –11 · 229 + 70 * 36 ((d) dan 13 ga almashtiring va birlashtiring)

1 = –11 · 229 + 70 · (265 - 1 · 229) = –81 · 229 + 70 · 265 ((c) dan 36 ga almashtiring va birlashtiring)

1 = –81 · (1024 - 3 · 265) + 70 · 265 = –81 · 1024 + 313 · 265 ((b) dan 229 o'rnini oling va birlashtiring)

1 = –81 · 1024 + 313 · (15625 - 15 · 1024) = 313 · 15625 - 4776 · 1024 ((a) dan 265 o'rnini almashtiring va birlashtiring)

Shunday qilib, juftlik (N₀, F₀) = (–4776 · 8404,313 * 8404); eng kichigi ${ displaystyle t}$ (oldingi qismdagi (3) ga qarang), bu ikkala N va F ni ijobiy holatga keltiradigan 2569 ga teng, shuning uchun:

${ displaystyle N = N_ {0} +15625 cdot 2569 = 3121}$

Davomi kasr

Shu bilan bir qatorda, qurilishi Evklid algoritmiga asoslangan davomli fraktsiyadan foydalanish mumkin. Uchun davom etgan kasr¹⁰²⁴⁄₁₅₆₂₅ (0.065536 aniq) bu [; 15,3,1,6,2,1,3];^[20] uning konvergenti takrorlanganidan keyin tugaydi³¹³⁄₄₇₇₆, bizga x beradi₀= –4776 va y₀= 313. Ning eng kichik qiymati t buning uchun ham N va F ham manfiy emas 2569, shuning uchun

${ displaystyle N = -4776 cdot 8404 + 15625 cdot 2569 = 3121}$.

Bu muammoning shartlarini qondiradigan eng kichik ijobiy raqam.

Umumiy echim

Dengizchilar soni parametr bo'lsa, bo'lsin ${ displaystyle m}$hisoblash qiymatidan ko'ra, dastlabki qoziqdagi hindiston yong'og'i va ertalab har bir dengizchiga ajratilgan son o'rtasidagi munosabatni algebraik ravishda kamaytirish natijasida koeffitsientlari quyidagicha ifodalanadigan o'xshash Diofantin munosabati hosil bo'ladi. ${ displaystyle m}$.

Birinchi qadam har bir dengizchining qoziqni o'zgartirishiga mos keladigan takrorlanish munosabatlarining algebraik kengayishini olishdir, ${ displaystyle n_ {i}}$ dengizchi qoldirgan raqam:

${ displaystyle n_ {i} = { frac {m-1} {m}} (n_ {i-1} -1)}$

qayerda ${ displaystyle n_ {i rightarrow 0} equiv N}$, dastlab yig'ilgan raqam va ${ displaystyle n_ {i rightarrow m}}$ ertalab qolgan raqam. O'zgartirish bilan takrorlanishni kengaytirish ${ displaystyle n_ {i}}$ uchun ${ displaystyle n_ {i-1}}$ ${ displaystyle m}$ marta hosil beradi:

${ displaystyle n_ {m} = chap ({ frac {m-1} {m}} o'ng) ^ {m} cdot n_ {0} - chap [({ frac {m-1} {) m}}) ^ {m} + ... + ({ frac {m-1} {m}}) ^ {2} + { frac {m-1} {m}} o'ng]}$

Oxirgi muddatni faktorizatsiya qilish,

${ displaystyle n_ {m} = chap ({ frac {m-1} {m}} o'ng) ^ {m} cdot n_ {0} - chap ({ frac {m-1} {m }} o'ng) cdot chap [({ frac {m-1} {m}}) ^ {m-1} + ... + { frac {m-1} {m}} + 1 o'ngda]}$

Shaklning qavsidagi kuch qatori polinom ${ displaystyle x ^ {m-1} + ... + x + 1}$ so'mga ${ displaystyle (1-x ^ {m}) / (1-x)}$ shunday,

${ displaystyle n_ {m} = chap ({ frac {m-1} {m}} o'ng) ^ {m} cdot n_ {0} - chap ({ frac {m-1} {m }} o'ng) cdot chap [ chap (1 - ({ frac {m-1} {m}}) ^ {m} o'ng) { bigg /} chap (1 - ({ frac {m-1} {m}}) o'ng) o'ng]}$

bu quyidagilarni soddalashtiradi:

${ displaystyle n_ {m} = chap ({ frac {m-1} {m}} o'ng) ^ {m} cdot n_ {0} - (m-1) cdot { frac {m ^ {m} - (m-1) ^ {m}} {m ^ {m}}}}$

Ammo ${ displaystyle n_ {m}}$ ertalab qolgan son, bu ko'paytmaga teng ${ displaystyle m}$ (ya'ni ${ displaystyle F}$, ertalab har bir dengizchiga ajratilgan raqam):

${ displaystyle m cdot F = chap ({ frac {m-1} {m}} o'ng) ^ {m} cdot n_ {0} - (m-1) cdot { frac {m ^ {m} - (m-1) ^ {m}} {m ^ {m}}}}$

Uchun hal qilish ${ displaystyle n_ {0}}$(=${ displaystyle N}$),

${ displaystyle N = m ^ {m} cdot { frac {m-1 + m cdot F} {(m-1) ^ {m}}} - (m-1)}$

Tenglama ikki o'zgaruvchida chiziqli Diofant tenglamasi, ${ displaystyle N}$ va ${ displaystyle F}$. ${ displaystyle m}$ har qanday tamsayı bo'lishi mumkin bo'lgan parametrdir. Tenglamaning mohiyati va uni hal qilish usuli bog'liq emas ${ displaystyle m}$.

Raqamlarning nazariy mulohazalari endi amal qiladi. Uchun ${ displaystyle N}$ tamsayı bo'lish uchun bu etarli ${ displaystyle { frac {m-1 + m cdot F} {(m-1) ^ {m}}}}$ tamsayı bo'ling, shunday bo'lsin ${ displaystyle r}$:

${ displaystyle r = { frac {m-1 + m cdot F} {(m-1) ^ {m}}}}$

Tenglama shaklga aylantirilishi kerak ${ displaystyle ax + by = pm 1}$ ularning echimlari formulaga ega. Shuning uchun:

${ displaystyle (m-1) ^ {m} cdot r-m cdot s = -1}$, qayerda ${ displaystyle s = 1 + F}$

Chunki ${ displaystyle m}$ va ${ displaystyle m-1}$ nisbatan sodda, to'liq echimlar mavjud ${ displaystyle (r, s)}$ Bézout kimligi bilan. Ushbu tenglamani quyidagicha o'zgartirish mumkin:

${ displaystyle (m-1) ^ {m} cdot r equiv -1 mod m}$

Ammo (m–1)^m polinom hisoblanadi Z · m–1 agar m toq va Z · m+1 agar m hatto, qaerda Z ning monomial asosli polinomidir m. Shuning uchun r₀= 1 agar m toq va r₀= –1 agar m hatto bu echim.

Bezoutning o'ziga xosligi davriy echimni beradi ${ displaystyle r = r_ {0} + k cdot m}$, shuning uchun o'rniga ${ displaystyle r}$ Diofantin tenglamasida va qayta tashkil etishda:

${ displaystyle N = r_ {0} cdot m ^ {m} - (m-1) + k cdot m ^ {m + 1}}$

qayerda ${ displaystyle r_ {0} = 1}$ uchun ${ displaystyle m}$ toq va ${ displaystyle r_ {0} = - 1}$ uchun ${ displaystyle m}$ hatto va ${ displaystyle k}$ har qanday tamsayı.^[21] Berilgan uchun ${ displaystyle m}$, eng kichik ijobiy ${ displaystyle k}$ shunday tanlanadi ${ displaystyle N}$ muammo qo'yishning cheklovlarini qondiradi.

Muammoning Uilyam versiyasida, ${ displaystyle m}$ 5 ta dengizchi, shuning uchun ${ displaystyle r_ {0}}$ 1 ga teng va ${ displaystyle k}$ eng past ijobiy javobni olish uchun nolga teng bo'lishi mumkin, shuning uchun N = 1  · 5⁵ - asl qoziqdagi hindiston yong'og'i soni uchun 4 = 3121. (Uchun tenglamaning navbatdagi ketma-ket echimi ta'kidlanishi mumkin k= -1, -12504, shuning uchun sinov va xato nol atrofida muammoning Uilyams versiyasini hal qila olmaydi, chunki uning asl nusxasidan farqli o'laroq, uning tenglamasi kichik kattalikdagi salbiy echimga ega edi).

Mana ijobiy echimlar jadvali ${ displaystyle N}$ birinchi bir necha uchun ${ displaystyle m}$ (${ displaystyle k}$ har qanday manfiy bo'lmagan tamsayı):

${ displaystyle m}$	${ displaystyle N}$
2	${ displaystyle 11 + k cdot 8}$[22]
3	${ displaystyle 25 + k cdot 81}$
4	${ displaystyle 765 + k cdot 1024}$
5	${ displaystyle 3121 + k cdot 15,625}$
6	${ displaystyle 233,275 + k cdot 279,936}$
7	${ displaystyle 823,537 + k cdot 5,764,801}$
8	${ displaystyle 117,440,505 + k cdot 134,217,728}$

Boshqa variantlar va umumiy echimlar

Boshqa variantlar, shu jumladan taxminiy salafiy muammo, o'zboshimchalik bilan dengizchilar uchun umumiy echimlarga ega.

Ertalab bo'linish ham qolgan qismga ega bo'lganda, echim quyidagicha:

${ displaystyle N = - (m-1) + k cdot m ^ {m + 1}}$

Uchun ${ displaystyle m = 5}$ va ${ displaystyle k = 1}$ bu muammoning Uilyamgacha bo'lgan versiyasi uchun 15621 ni eng kichik ijobiy kokos miqdori sifatida beradi.

Muammoning oldingi ba'zi muqobil shakllarida bo'linishlar ham chiqdi va qolgan qoziqdan yong'oq (yoki buyumlar) ajratildi keyin bo'linish. Ushbu shakllarda rekursiya munosabati:

${ displaystyle n_ {i} = { frac {m-1} {m}} n_ {i-1} -1}$

Muqobil shakl, shuningdek, ertalabki bo'linish hatto chiqib ketganda va maymun uchun bitta yong'oq qolganda, ikkita tugashga ega edi, ertalab bo'linish teng bo'lganda ham, umumiy echim shunga o'xshash lotin orqali kamayadi:

${ displaystyle N = -m + k cdot m ^ {m + 1}}$

Masalan, qachon ${ displaystyle m = 4}$ va ${ displaystyle k = 1}$, asl qoziqda 1020 kokos yong'og'i bor va har bir bo'linishdan keyin maymunga ajratilgan kokos bilan tunda to'rtta ketma-ket bo'linishdan so'ng, ertalab 80 kokos qoldi, shuning uchun ham kokos qolmagan holda yakuniy bo'linma chiqadi .

Ertalab bo'linish natijasida yong'oq qolgan bo'lsa, umumiy echim:

${ displaystyle N = r_ {0} cdot m ^ {m} -m + k cdot m ^ {m + 1}}$

qayerda ${ displaystyle r_ {0} = - 1}$ agar ${ displaystyle m}$ toq va ${ displaystyle r_ {0} = 1}$ agar ${ displaystyle m}$ hatto. Masalan, qachon ${ displaystyle m = 3}$, ${ displaystyle r_ {0} = - 1}$ va ${ displaystyle k = 1}$, asl qoziqda 51 ta kokos yong'og'i bor va har bir bo'linishdan keyin maymunga ajratilgan kokos bilan tunda uchta ketma-ket bo'linishdan so'ng, ertalab 13 kokos qoldi, shuning uchun yakuniy bo'linmada maymun uchun qolgan kokos bor.

Uilyamsdan keyingi boshqa variantlar, shu jumladan turli xil qoldiqlarni, shu jumladan ijobiylarni (ya'ni maymun uyumga hindiston yong'og'ini qo'shadi) belgilaydi, adabiyotda ko'rib chiqilgan. Yechim:

${ displaystyle N = r_ {0} cdot m ^ {m} -c cdot (m-1) + k cdot m ^ {m + 1}}$

qayerda ${ displaystyle r_ {0} = 1}$ uchun ${ displaystyle m}$ toq va ${ displaystyle r_ {0} = - 1}$ uchun ${ displaystyle m}$ hatto, ${ displaystyle c}$ har bir bo'linishdan keyin qolgan qism (yoki maymunlar soni) va ${ displaystyle k}$ har qanday butun son (${ displaystyle c}$ maymunlar uyumga hindiston yong'og'ini qo'shsa salbiy).

Erkaklar soni yoki qoldiqlar bo'linishlar orasida o'zgarib turadigan boshqa variantlar, odatda, maymun va kokos yong'og'i bilan bog'liq muammolar sinfidan tashqarida, ammo ular xuddi shu tarzda ikkita o'zgaruvchida chiziqli Diofant tenglamalariga kamayadi. Ularning echimlari xuddi shu usullarga mos keladi va yangi qiyinchiliklarga olib kelmaydi.

Shuningdek qarang

• Arximedning qoramol muammosi, Diofantin muammosi ancha qiyin
• Fermaning so'nggi teoremasi, ehtimol, eng mashhur Diofant tenglamasi
• To'p to'pi muammosi

Adabiyotlar

Manbalar

• Antonick, Gary (2013). Martin Gardner’s The Monkey and the Coconuts in Numberplay The Nyu-York Tayms:, October 7, 2013
• Pleacher, David (2005). Problem of the Week: The Monkey and the Coconuts 2005 yil 16-may
• Gardner, Martin (2001). Matematikaning ulkan kitobi: klassik jumboqlar, paradokslar va muammolar VW. Norton & Company; ISBN  0-393-02023-1
• Pappas, Theoni (1993). Joy of Mathematics: Discovering Mathematics All Around| Wide World Publishing, January 23, 1993, ISBN  0933174659
• Wolfram Mathworld: Monkey and Coconut Problem
• Kirchner, R. B. "The Generalized Coconut Problem." Amer. Matematika. Monthly 67, 516-519, 1960.
• Fadiman, Clifton (1962). Matematik Magpie, Simon & Schuster
• Bogomolniy, Aleksandr (1996) Negative Coconuts at cut-the-knot

Tashqi havolalar

• Monkeys and Coconuts - Numberphile video
• Hindiston yong'og'i, a copy of the story as it appeared in the Saturday Evening Post