Mavzu: 100 Mahbus va 100 quti muammosi

Mavzu:100 Mahbus va 100 quti muammosi

Muammoning sharti quyidagicha:
Qamoqxonada 100 mahbus bor, ularning har biri 1 dan 100 gacha shaxsiy raqamga ega. Qamoqxona nazoratchisi mahbuslarga ozodlikka chiqish imkoniyatini berishga qaror qiladi va o'zi o'ylab topgan testdan o'tishni taklif qiladi. Agar barcha mahbuslar muvaffaqiyatga erishsa, ular ozod bo'lishadi, agar kamida bittasi muvaffaqiyatsiz bo'lsa, hammasi o'ladi.
Qamoqxona nazoratchisi maxfiy xonaga borib, qopqoqli 100 ta quti tayyorlaydi. Har bir qutiga 1 dan 100 gacha raqamlarni belgilaydi. Keyin mahbuslar soniga qarab 100 ta qog'oz bo'lakchalarini olib keladi va bu qog'ozlarni 1 dan 100 gacha raqamlaydi. Shundan so'ng u 100 ta qo'gozni aralashtirib, har bir qutiga bittadan qog'oz bo'lakchalarini qo'yadi va qopqog'ini yopadi. Mahbuslar, qamoqxona nazoratchisi bu harakatlarning barchasini qanday bajarayotganini ko'rmaydilar.
Musobaqa boshlanadi, qamoqxona nazoratchisi har bir mahbusni qutilari bo'lgan xonaga birma-bir olib boradi va mahbuslarga ichida mahbusning raqami ko'rsatilgan qutini topish kerakligini aytadi. Mahbuslar qutilarni ochib, ularning raqami yozilgan qog'ozni topishga harakat qilmoqda. Har biriga 50 tagacha quti ochishga ruxsat beriladi; agar mahkumlarning har biri o'z raqamini topsa, mahbuslar ozod qilinadi, agar ulardan kamida bittasi 50 ta urinishda o'z raqamini topa olmasa, unda barcha mahbuslar o'ladi.
Mahkumlar ozod bo'lishlari uchun HAMMA mahbuslar sinovdan muvaffaqiyatli o'tishlari kerak.
Xo‘sh, mahbuslarning afv etilishi ehtimoli qanday?
Mahkum qutini ochib, raqamlarni tekshirgandan so'ng, u qutiga qayta joylashtiriladi va qopqog'i yana yopiladi;
Qutilarning joylarini o'zgartirish mumkin emas;
Mahkumlar sud jarayoni boshlangandan keyin bir-birlariga iz qoldira olmaydilar yoki hech qanday tarzda bir-birlari bilan muloqot qila olmaydilar;
Mahkumlarga sud jarayoni boshlanishidan oldin strategiyani muhokama qilishga ruxsat beriladi.
Yechim mumkin emasmi?
Bir qarashda, bu vazifa deyarli umidsiz ko'rinadi. Aftidan, har bir mahbusning raqamni topish imkoniyati mikroskopik jihatdan kichik. Bundan tashqari, mahkumlar bu jarayonda bir-biri bilan ma'lumot almasha olmaydi.
Bitta mahbusning koeffitsienti 50:50. Hammasi bo'lib 100 ta quti bor va u o'z belgisini qidirib 50 tagacha qutini ochishi mumkin. Agar u tasodifiy qutilarni ochsa va barcha qutilarning yarmini ochsa, u o'z raqamini qutilarning ochiq yarmida topadi yoki uning raqami yopiq 50 qutida qoladi. Uning muvaffaqiyatga erishish imkoniyati ya'ni ehtimoli ½.
Keling, ikkita asirni olaylik. Agar ikkalasi ham tasodifiy qutilarni tanlasa, ularning har biri uchun imkoniyat ½, ikkitasi uchun ½x½=¼ bo'ladi.
(ikki mahbus uchun muvaffaqiyat to'rt holatdan bittasida bo'ladi). Uch mahbus uchun koeffitsientlar ½ × ½ × ½ = ⅛.
100 mahbus uchun koeffitsienlar (100 marta ko'paytiring) ½×½×...×½
Bu teng
P ≈ 0,00000000000000000000000000000008
Demak, bu juda kichik imkoniyat. Ushbu strategiyada, barcha mahbuslar o'lish ehtimoli yuqori
Qarorni o'qishdan oldin yaxshilab o'ylab ko'rish tavsiya etiladi.
Aql bovar qilmaydigan javob
Agar har bir mahbus qutilarni tasodifiy ochsa, ular sinovdan o'tishlari dargumon. Mahbuslar 30% dan ko'prog'ida muvaffaqiyat qozonishlarini kutishlari mumkin bo'lgan strategiya mavjud. Bu hayratlanarli darajada aql bovar qilmaydigan natijadir (agar siz ilgari bu matematik muammo haqida eshitmagan bo'lsangiz).
Yechimini ko'raylik:
Strategiya juda oson. Mahbuslarning birinchisi kiyimida yozilgan raqam yozilgan qutini ochadi. Misol uchun, 78-raqamli mahbus 78-raqamli qutini ochadi. Agar u quti ichidagi plastinkadan o'z raqamini topsa, bu ajoyib! Agar yo'q bo'lsa, u "o'z" qutisidagi raqamga qaraydi va keyin bu raqam bilan keyingi qutini ochadi. Ikkinchi qutini ochib, ushbu quti ichidagi raqamga qaraydi va shu raqam yozilgan uchinchi qutini ochadi. Keyin biz ushbu strategiyani qolgan qutilarga o'tkazamiz.
Oxir-oqibat, mahbus o'z raqamini topadi yoki 50-quti chegarasiga etadi.
Xo'sh, nima uchun strategiya ishlaydi?
Har bir qutida bitta raqamlangan qog'oz bor - va bu qog'oz noyobdir. Bu shuni anglatadiki, plastinka bir xil raqamga ega bo'lgan qutida yoki u boshqa qutiga ishora qiladi. Barcha plitalar noyob bo'lganligi sababli, unga ishora qiluvchi har bir quti uchun faqat bitta plastinka mavjud (va bu qutiga borishning faqat bitta usuli).
Qutilar yopiq dumaloq zanjir hosil qiladi. Bitta quti faqat bitta zanjirning bir qismi bo'lishi mumkin, chunki quti ichida keyingisiga faqat bitta ko'rsatgich bor va shunga mos ravishda oldingi qutida bu qutiga faqat bitta ko'rsatgich mavjud
Agar quti o'zini ko'rsatmasa (quti raqami undagi plastinka raqamiga teng), u holda zanjirda buziladi. Ba'zi zanjirlar ikkita qutidan iborat bo'lishi mumkin, ba'zilari esa uzunroq.
Zanjir uzunligi
Barcha mahkumlar sinovdan o'tishi uchun zanjirning maksimal uzunligi 50 qutidan kam bo'lishi kerak. Agar zanjir 50 qutidan uzunroq bo'lsa, bu zanjirlardagi raqamlarga ega mahbuslar sinovdan o'ta olmaydi - va barcha mahbuslar o'lib ketadi.
Agar eng uzun zanjirning maksimal uzunligi 50 qutidan kam bo'lsa, unda barcha mahbuslar sinovdan o'tadilar!
Bir soniya o'ylab ko'ring. Ma'lum bo'lishicha, plitalarning har qanday tartibida 50 qutidan uzun bo'lgan faqat bitta zanjir bo'lishi mumkin (bizda faqat 100 ta quti bor, shuning uchun bitta zanjir 50 dan uzun bo'lsa, qolganlari jami 50 dan qisqa bo'ladi).
Zanjirlar uzun bo'lib ketganda
Muvaffaqiyatli bo'lish uchun zanjirning maksimal uzunligi 50 dan kam yoki teng bo'lishi kerakligiga va har qanday to'plamda faqat bitta uzun zanjir bo'lishi mumkinligiga ishonch hosil qilganimizdan so'ng, biz sinovdan o'tish ehtimolini hisoblashimiz mumkin:
Uzun zanjirning ehtimolini aniqlash uchun nima qilishimiz kerak?
Uzunligi l bo'lgan zanjir uchun qutilarning ushbu zanjirdan tashqarida bo'lish ehtimoli:
Ushbu raqamlar to'plamida (l-1) mavjud! belgilarni tartibga solish usullari.
Qolgan belgilar (100-l) joylashgan bo'lishi mumkin! yo'llar (zanjirning uzunligi 50 dan oshmasligini unutmang).
Buni hisobga olgan holda, aniq uzunlikdagi l qatorni o'z ichiga olgan almashtirishlar soni: (>50)
Ma’lum bo‘lishicha, l uzunlikdagi zanjirning mavjudligi ehtimoli 1/l ga teng bo‘lishi uchun plitalarni joylashtirishning 100(!) usuli mavjud. Aytgancha, bu natija qutilar soniga bog'liq emas.
Biz allaqachon bilganimizdek, uzunligi > 50 bo'lgan zanjir mavjud bo'lgan faqat bitta holat bo'lishi mumkin, shuning uchun muvaffaqiyat ehtimoli ushbu formula bilan hisoblanadi:
Natija
31,18% - eng uzun zanjirning o'lchami 50 dan kam bo'lishi va mahkumlarning har biri 50 ta urinish chegarasini hisobga olgan holda o'z raqamlarini topishi ehtimoli.
Barcha mahbuslar o'z raqamlarini topib, testdan o'tish ehtimoli 31,18% ni tashkil qiladi.
Quyida l uzunlikdagi (x o'qi bo'yicha) barcha zanjirlar uchun (y o'qi bo'yicha) ehtimolliklarni ko'rsatadigan grafik keltirilgan. Qizil barcha "muvaffaqiyatsizliklar" degan ma'noni anglatadi. Yashil "muvaffaqiyat" degan ma'noni anglatadi. Yashil chiziqlarning umumiy imkoniyati saqlanib qolish ehtimoli 31,18% ni tashkil qiladi.

Etiboringiz uchun rahmat