Задача

Сама задача відома з прадавніх часів під назвою “задача Йосифа Флавія“. На співбесідах її можна почути в такому вигляді.

100 воїнів вишикувалися у замкнене коло. У першого воїна і лише у нього є меч. Він цим мечем вбиває наступного за ним (тобто другого) і передає меч наступному ще не вбитому (тобто третьому). Той хто отримує меч так само вбиває наступного і передає меч далі. І так доки не лишиться лише один живий воїн. Питання – який номер залишиться в живих.

В більш загальному випадку кількість воїнів може бути довільною так само як порядок вбивств.

Рішення

Наївним рішенням буде створити у пам’яті колекцію флагів для кожного воїна і по колу позначати вбитих доки не лишиться один не позначений елемент. Таке рішення звісно буде працювати, але воно вимагатиме додаткової пам’яті і процесорного часу щоб зробити всі ітерації.

Щоб знайти номер воїна який вижив дешевшим способом можна спробувати наступне. Спочатку з’ясуємо для якої кількості воїнів перший виживе гарантовано. Це звісно буде парна кількість. Тепер щоб гарантувати що перший воїн виживе на наступні і  наступній ітерації і так далі нам теж треба щоб кількість елементів на кожній з них була парною. Таким чином якщо кількість воїнів дорівнює ступеню двійки то виживе перший воїн.

Для довільної кількості елементів N знайдемо найбільший ступінь двійки X такий що X <= N (це можна зробити, наприклад, модифікувавши алгоритм з Знайти найближчий ступінь двійки). Індекс з якого коло з N елементів перетвориться на коло з елементів кількість яких дорівнюватиме ступеню двійки і буде нашою відповіддю. Тобто нам треба знайти скільки елементів M треба пройти (половину з яких буде “вбито”) таких що M/2 + (N-M)=X. Просте рівняння з якого знаходимо що M=(N-X)*2.

Тобто для 100 воїнів (N=100) найближчим ступенем двійки не більшим за 100 буде 64 (X=64) і таким чином залишиться в живих 73-й воїн (M=(100-64)*2=72).

Задача

Двох друзів було ув’язнено і посаджено в різні камери. Перед ними поставили таку умову: кожного дня для кожного з них кидають монету і після цього кожен з них має сказати “реверс” чи “аверс” для монети яку кидали в іншій камері. Кожне з них не знає як монета випала в іншій камері. Якщо хоч один вгадав то їх залишають в спокої до наступного дня. Якщо ж обидва помиляться то їх обох негайно стратять. Не відповідати, або давати іншу відповідь крім “аверс” та “реверс” не можна. Друзі можуть узгодити свою стратегію до того як їх розведуть по камерах.

Як друзям гарантовано вижити?

Рішення

Перше на що треба звернути увагу це те що для виживання достатньо вгадувати лише одну з двох монет. Таким чином треба щоб кожна відповідь давала 50% шансів вгадати.

Нехай перший в’язень завжди повторює той результат який випав на його монеті. Таким чином ми покриваємо 50% варіантів для другої монети. Другий в’язень має дати відповідь яка покриє інші 50%: якщо перший в’язень не вгадав другу монету то значить перша монета випала не так як друга – перший просто повторює те що бачить, тобто другий в’язень має казати значення протилежне тому що бачить.

Виграшна стратегія в результаті виглядає так: один в’язень повторює результат своєї монети, а другий каже протилежний результат для своєї монети.

Табличка показує як це працює:

Монета 1 В'язень 1 каже: Монета 2 В'язень 2 каже: Результат
аверс аверс аверс реверс В'язень 1 вгадав монету 2
аверс аверс реверс аверс В'язень 2 вгадав монету 1
реверс реверс аверс реверс В'язень 1 вгадав монету 2
реверс реверс реверс аверс В'язень 2 вгадав монету 1

Задача, варіант 1

В одній країні діє закон за яким кожне подружжя коли народжує хлопчика не може мати більше дітей. А якщо народжується дівчинка то вони народжують ще одну дитину. Яке співвідношення хлопчиків та дівчаток у той країні? Вважаємо що немовлята обох статей народжуються з рівною імовірністю.

Рішення

Для N подружніх пар народиться N/2 хлопчиків (позначимо як A), та N/2 дівчат (позначимо як B). При цьому варіант A є остаточним, а для варіанту B далі можливі такі під-варіанти: у половини родин (N/4) народяться хлопчики (позначимо як B1), у другої половини (теж N/4) народяться дівчатка (позначимо як B2).

Таким чином матимемо:

  • хлопчиків: A + B1 = N/2 + N/4
  • дівчаток: B + B2 = N/2 + N/4

Тобто співвідношення буде 1:1.

Задача, варіант 2

Якщо умови змінити таким чином що пара народжує дітей доки у них не з’явиться хлопчик і на цьому зупиняється як зміниться співвідношення?

Рішення

На кожній ітерації половина родин народжує хлопчика і припиняє свої спроби. Інша ж половина відповідно має дівчат і на наступній ітерації знову ділиться навпіл. Таким чином на кожній ітерації кількість немовлят обох статей однакова.

Продемонструвати можна так:

ітерація 1 ітерація 2 ітерація 3 ітерація 4  …
хлопчиків: N/2(A) N/4(B1) N/8(B21) N/16(B221)
дівчаток: N/2(B) N/4(B2) N/8(B22) N/16(B222)

Таким чином кількість хлопчиків і дівчаток при скільки завгодно ітераціях буде однаковою і пропорція 1:1 зберігається.

Визначити скільки біт (двійкових розрядів) треба відвести під те, щоб записати число 532067?

Рішення:

Оскільки 2n=n біт, тож рішенням буде нерівність

2n-1< 532067 <=2n                          –                      логарифмуємо за основою 53, маємо

(n-1) log532<2067<=n log532,                            де log532= 0,1745,

тож

n-1<2067/0.1745<=n,                                          тобто n-1<11839.61<=n.

Oоп-ля (:

Логарифмування! обожнюю (:

Задача

Є функція random2() яка з рівною імовірністю повертає 0 або 1. Треба на її основі написати функцію яка з рівною імовірністю повертає 0,1 або 2.

Рішення

Треба якось привести результати виклику random2() до трьох рівноможливих варіантів. Побудуємо таку таблицю:

1-й виклик random2() 2-й виклик random2() Результат
0 0 0
0 1 1
1 0 2
1 1 ?

 

Бачимо що у нас 4 рівноможливі варанти. Якщо четвертий результат замінити на рекурсивний виклик цієї ж функції то матимемо три рівноімовірні варіанти.

int random3() { int result = random2() * 2 + random2(); if (result == 3) result = random3(); return result; }

Недолік методу – існує теоретична імовірність (хоча і дуже мала) входження у нескінченний цикл.

Задача

Якого розміру має бути група людей щоб імовірність народження хоч одного з неї в ту саму дати що народилися і ви (лише ісяць і число) складала не менше 50%?

Рішення

Для тих хто як і я математикою і теорією імовірності користувався останній раз в інституті/університеті спробую роз’яснити детально.

Для однієї випадкової людини імовірність народження в певну дату року складає 1/365. Позначимо її як p. Відповідность імовірність народження в будь яку іншу дату для тієї ж людини складає 1-p.

Тепер для двох людей складемо таку табличку:

А народився в певну дату

Б народився в певну дату

Імовірність того що дві ці події трапляться одночасно

ні так (1-p)*p
так ні p*(1-p)
так так p*p
ні ні (1-p)2

 

Щоб визначити імовірність народження в певну дату N людей треба скласти всі імовірності усих комбінацій крім тих де ніхто не народився у вказану дату. Або можна зробити простіше і взяти імовірність того що ніхто не народився у вказану дату – вона буде складати (1-p)n. Відповідно імовірність того що хоч хтось з N людей народився у вказану дату складатиме 1-(1-p)n.

Тепер треба знайти чому ж дорівнює n у рівнянні 1-(1-p)n=0.5

Як ми пам’ятаємо (якщо пам’ятаємо) функцією зворотньою ступеню є логарифм. Тому можемо записати так:

image

А як ми знаємо при маленьких значеннях p запис ln(1-p) можна спростити до –p.

Значення ln 0.5 можна знайти у таблицях (наприклад тут – http://www.piclist.com/images/www/hobby_elec/e_logarithm.htm).

Отже маємо:

image

Отже наша відповідь така – для того щоб імовірність що у випадковій групі людей є хоч хтось з такою самою датою народження як і у вас розмір групи має складати не менше ніж 252 людини.

Взагалі з математикою, статистикою та теорією імовірності у мене не дуже, тому подібні задачі важкі для мене Sad smile

Задача

Кожні 20 хвилин на платформу прибуває потягш. Стоїть він там рівно 2 хвилини. Який середній час очикування потягу для пасажира?

Рішення

2 хвилини з 20 очикування буде 0 хвилин (стільки потяг стоїть на платформі). Інші 18 хвилин час буде зростати з 0 до 18 хвилин.

2 хвилини з середнім часом очикування 0 це 10% від 20 хвилин.

Для інших 18 хвилин, які складають 90%, середній час очикування дорівнює 9 хвилинам.

Отже середній час очикування для усього 20-хвилинного проміжку буде 9 * 0,9 = 8.1 хвилини.