Raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

4-vazifa. 
Soxta tanga 2. 
8 tanga bor. Ulardan biri soxta va haqiqiy tanga uchun osonroq. Tangalardan qaysi 
birini soxtalashtirishini aniqlang. 
Qaror 
Tangalarni ikki teng huquqqa ajratamiz - har birida 4 tanga. Torting. Bu qoziq, bu 
osonroq bo'lgan ikkita o'xshash qo'llanmani yana ajratamiz - endi har biri ikkita tanga. 
Torting. Qaysi biri osonroq ekanligini aniqlaymiz. Biz ushbu qo'lqozondan 1 tanga 
og'irligi tarozilarini qo'ydik. Soxta bu osonroq. Vazifa hal qilinadi. 
5-band. 
Soxta tanga 3. 
10 tanga bor. Ulardan biri soxta va haqiqiy tanga uchun osonroq. Qanday qilib 
kubog 'vaznidan og'irlik bilan, tangalarning qaysi biri soxta? 
Qaror 
Biz 10 tangani 2 ta teng huquq bilan ajratamiz - 5 tanga. Biz tarozini kiydik. Biz 
ushbu oqimlarning qaysi biri soxta tanga ekanligini aniqlaymiz. Endi bu qoziq 3 taga 
bo'lingan - ikkitasida ikkita tanga, uchinchi tanga. Ikkala tanga shundaki, ikkita tanga. 
Agar tarozlar tenglik ko'rsatiladi, keyin uchinchi uyumda soxta. Agar tengsizlik 
ko'rsatilsa, unda qoziqdagi soxta tanga. Endi bu qo'lkochkaning 1 ta tanga tarozini kiying 
- soxta engilroq. Vazifa hal qilinadi. 
10. Iozef masalasi 
Muammo 1-asrda yashagan yahudiy tarixchisi Flaviy Iosif sharafiga nomlangan. 
Iosifning Yodfatni qamal qilish haqidagi maʼlumotlariga koʻra, u 40 nafar askari bilan 
gʻorda Rim askarlari tomonidan ushlangan. Ular qo'lga olishdan ko'ra o'z joniga qasd 
qilishni afzal ko'rishdi va lotereya orqali o'z joniga qasd qilishning ketma-ket usuliga 
qaror qilishdi. Iosifning ta'kidlashicha, omad tufayli yoki ehtimol Xudoning qo'li bilan u 
va boshqa bir kishi oxirigacha qolishdi va o'zlarini o'ldirish o'rniga rimliklarga taslim 

---

bo'lishdi. Bu Iosifning "Yahudiylar urushi" kitobining 3-kitobi, 8-bobi, 7-qismida 
keltirilgan hikoya (o'zi haqida uchinchi shaxsda yozgan): Biroq, bu o'ta qayg'uda u odatiy 
tushunchasini yo'qotmadi; lekin u Xudoning ilohiga ishonib, o'z hayotini xavf ostiga 
qo'ydi [quyidagicha]: "Va endi, - dedi u, - sizning orangizda o'lishingiz qaror qilinganligi 
sababli, keling, umumiy o'limimizni qat'iyatga topshiraylik. lot bo'yicha. Kim birinchi 
bo‘lib qur’a tashlasa, ikkinchi qur’a olgan kishi tomonidan o‘ldirilsin va shu tariqa omad 
hammamizga tarqaladi; va hech birimiz o'z o'ng qo'limiz bilan halok bo'lmaymiz, chunki 
qolganlar ketgandan keyin, kimdir tavba qilib, najot topsa, adolatsizlik bo'ladi. Bu taklif 
ularga juda adolatli tuyuldi; va ularni qur'a orqali aniqlashga ko'ndirganida, u ham 
qur'adan birini o'zi uchun tortdi. Birinchi qur’a olgan kishi keyingisini olganga bo‘ynini 
ochib, general shu zahoti ular orasida halok bo‘ladi, degan taxmin bilan; Chunki ular, 
agar Yusuf ular bilan birga o‘lsa, o‘lim hayotdan shirinroq, deb o‘ylar edilar.
Shunday bo'lsa-da, bu tasodifan sodir bo'lganmi yoki 
Xudoning ixtiyori bilanmi, deylikmi, u ikkinchisi bilan oxirigacha qoldi. Va u qur’a 
hukmiga mahkum bo‘lishni yoki oxirigacha qolsa, o‘ng qo‘lini vatandoshlarining qoniga 
ho‘llashni juda istamagani uchun uni o‘ziga bo‘lgan sadoqatiga ishonib, o‘zi kabi 
yashashga ko‘ndirgan. agar u oxirigacha qolsa, o'ng qo'lini vatandoshlarining qoniga 
botirib, unga sodiqligiga ishonib, xuddi o'zi kabi yashashga ishontirar edi. 
vatandoshlarining qoni to'kib, unga sadoqatiga ishonib, xuddi o'zi kabi yashashga 
ko'ndirar edi. 
Ushbu jasoratda ishlatiladigan mexanizmning tafsilotlari juda noaniq. Jeyms Doudi 
va Maykl Meyslarning taʼkidlashicha, 1612-yilda Klod Gaspard Bachet de Meziryak 
erkaklarni aylana boʻylab joylashtirish va yoʻq qilish tartibini aniqlash uchun uchliklarda 
sanashning maxsus mexanizmini taklif qilgan. Bu hikoya tez-tez takrorlanadi va aniq 
tafsilotlar manbadan manbaga sezilarli darajada farq qiladi. Misol uchun, isroillik Natan 
Xershteyn va Irving Kaplanskiy (1974) aylanada Jozef va 39 o'rtoqdan iborat bo'lib, har 
ettitadan bittasi bundan mustasno. Muammo tarixini SL Thebellning Fibonachchi 
Quarterly jurnalida muharrirga yozgan maktubida topish mumkin.
Yusufning sherigi bor edi; muammo so'nggi ikki omon qolgan 
(ularning fitnasi ularning omon qolishini ta'minlagan) joylarini topish edi. Aytilishicha, u 
o'zini va boshqa bir kishini mos ravishda 31 va 16-o'rinlarga qo'ygan.

---

Variantlar va umumlashtirishlar 
Yusuf 
muammosining o'rta asr versiyasiga bo'ron paytida kemada 15 turk va 15 nasroniy kiradi, 
agar yo'lovchilarning yarmi kemaga tashlanmasa, cho'kib ketadi. 30 kishining hammasi 
aylanada turishadi va har to'qqizinchisi dengizga tashlanadi. Faqat turklardan voz kechish 
uchun xristianlar qayerda turishlari kerak? Boshqa versiyalarda turklar va 
nasroniylarning rollari teskari.
Beton 
matematikasida: 
Computer Science Foundation, Graham, Knuth va Patashnik "standart" variantni 
ta'riflaydi va o'rganadi: Agar boshlash uchun n kishi bo'lsa va har soniyada (quyida k = 
2) yo'q qilinsa, oxirgi omon qolgan qayerda turishini aniqlang.
Ushbu muammoning umumlashtirilishi 
quyidagicha. Biz har bir m-chi shaxs omon qolgan n o'lchamdagi guruhdan qatl qilinadi 
deb taxmin qilamiz. Agar aylanaga x kishi qo'shilsa, u n + x dan kichik yoki teng bo'lsa, 
omon qolgan p + mx - o'rinda turadi. Agar x (p + mx) > (n + x) bo'lgan eng kichik qiymat 
bo'lsa, u holda omon qolgan (p + mx) - (n + x) pozitsiyasida. [o'n] 
Qaror [tahrir] 
Quyida, boshlang'ich doiradagi odamlar sonini bildiradi va har bir qadam uchun ballni bildiradi, 
ya'ni odamlar o'tkazib yuboriladi va -e bajariladi. Davradagi odamlar dan gacha raqamlangan. 
k=2[tahrir]
Biz har bir 
ikkinchi odam o'ldirilganda muammoni aniq hal qilamiz, ya'ni. (Umumiy holat uchun biz quyida 
yechimni tasvirlaymiz.) Yechimni rekursiv tarzda ifodalaymiz. Dastlab odamlar (va ) mavjud 
bo'lganda, tirik qolganning pozitsiyasini belgilaylik. Birinchi marta aylanada hamma hatto odamlar 
ham o'lishadi. Doira atrofida ikkinchi marta yangi 2-shaxs vafot etadi, keyin yangi 4-chi va hokazo; 
aylanada birinchi marta bo'lmagandek. 
Agar odamlarning dastlabki soni juft bo'lsa, 
aylana bo'ylab ikkinchi marta pozitsiyani egallagan kishi dastlab joyida edi (har bir tanlov uchun). 
Bo'lsin. Endi omon qoladigan odam dastlab . Bu bizga takrorlashni beradi. Agar odamlarning 
dastlabki soni toq bo'lsa, unda biz 1-shaxs aylananing birinchi aylanishi oxirida vafot etadi deb 
o'ylaymiz. Yana ikkinchi marta aylana bo'ylab yangi 2-shaxs vafot etadi, keyin yangi 4-shaxs va 
hokazo.Bu holda lavozimni egallagan shaxs dastlab shu holatda bo'lgan. Bu bizga takrorlashni 
beradi 
Biz jadvalga qiymatlarni kiritganimizda va naqshni ko'rganimizda: OEIS : A006257 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

---

 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 
Bu shuni ko'rsatadiki, bu ortib borayotgan g'alati ketma-ketlik bo'lib, n indeks 2 ning daraj
asi bo'lganda qayta boshlanadi. Shuning uchun, agar biz m va l ni shunday tanlasak va , keyin . Jad
valdagi qiymatlar ushbu tenglamani qondirishi aniq. Yoki odamlar o'lganidan keyin faqat odamlar 
qoladi deb o'ylashimiz mumkin va biz 1-shaxsga o'tamiz. U omon qolgan bo'lishi kerak. Shunday 
qilib. Quyida biz induksiya orqali dalil keltiramiz.
Teorema: agar va bo'lsa, u hol
da . 
Isbot: Biz kuchli induksiyadan foydalanamiz. Asosiy holat to'g'ri. Juft va toq bo'
lgan holatlarni alohida ko'rib chiqamiz. 
Agar juft bo'lsa, va kabilarni tanlang. Bunga e'tibor bering. Bizda , bu erda ikkinchi teng
lik induksiya gipotezasidan kelib chiqadi. 
Agar g'alati bo'lsa, shunday va ni ham tanlang. Bunga e'tibor bering. Bizda , bu erda ikki
nchi tenglik induksiya gipotezasidan kelib chiqadi. Bu dalilni to'ldiradi. 
Biz aniq ifodani olishga qaror qilishimiz mumkin: 
Javobning eng oqlangan shakli o'lchamning ikkilik ko'rinishini o'z ichiga oladi: 
o'z-o'zidan bir bitli chapga aylanish orqali olinishi mumkin. Ikkilik formatda sifatida ifo
dalasak, u holda yechim ga o'xshash bo'ladi. Buning isboti as yoki uchun yuqoridagi ifo
dadan kelib chiqadi. 
Amalga oshirish: agar n - odamlar soni bo'lsa, xavfsiz pozitsiya , qaerda va tomonidan b
eriladi. 
Endi raqamni ikkilik formatda ifodalasak, birinchi bit ni, qolgan bitlar esa ni ifodalaydi. 
Masalan, n = 41 bo'lganda, uning ikkilik ko'rinishi bo'ladi 
n = 1 0 1 0 0 1 
2 m = 1 0 0 0 0 0 
l = 0 1 0 0 1
/ **
*
* @param n количество людей, стоящих в круге

---

* @ вернуть безопасную позицию, которая переживет казнь
* f (N) = 2L + 1, где N = 2 ^ M + L и 0 <= L < 2 ^ M
* /
public int getSafePosition ( int n ) {
// найти значение L для уравнения
int valueOfL = n - Целое число . highOneBit ( n );
int safePosition = 2 * значениеOfL + 1 ; 
return safePosition ;
} 
Bitta [tahrir] 
Xavfsiz joyni topishning eng oson yo'li bitli operatorlardan foydalanishdir. Ushbu yondashuvda n 
to'plamining eng muhim bitini eng kam ahamiyatli bitga o'tkazish xavfsiz holatni qaytaradi. [11] 
Musbat butun son kiriting. 
п = 1 0 1 0 0 1 
п = 0 1 0 0 1 1 
/ **
*
* @param n (41) количество людей, стоящих в круге
* @ вернуть безопасную позицию, которая переживет казнь
* ~ Integer.highestOneBit (n * 2)
* Умножьте n на 2, получите первый набор bit и взять его дополнение
* ((n << 1) | 1)
* Left Shift n и перевернуть последний бит
* ~ Integer.highestOneBit (n * 2) & ((n << 1) | 1)
* Побитовое И до биты копирования существуют в обоих операндах.
* /
public int getSafePosition ( int n ) {
return ~ Integer . highOneBit ( n * 2 ) & ((n << 1 ) | 1 );
} 

---

k=3[tahrir] 
1997 yilda Lorenz Halbeisen va Norbert Hungerbühler yopiq ish qog'ozini topdilar. Ular 
ma'lum bir doimiy borligini ko'rsatdilar 
ixtiyoriy aniqlik bilan hisoblash mumkin. Ushbu doimiyni hisobga olgan holda, eng katta 
butun sonni tanlang (u yoki bo'ladi). Keyin oxirgi omon qolgan 
agar biz ko'proq to'plagan bo'lsak 
Barcha uchun . 
Halbeisen va Hungerbuhler hisob-kitoblarga misol qilib keltirdilar (bu aslida Iosif 
muammosining asl formulasi). Ular hisoblashadi: 
va shuning uchun 
(esda tuting, biz pastga aylantirdik)