[задача] Німецький танк

Постановка задачі

Ця задача насправді виникла у минулому і її було розв’язано математиками під час Другої Світової.

Союзники збирали інформацію про те скільки танків кожного типу було випущено Німеччиною. Від шпигунів було відомо що завдяки німецькій організованості та пунктуальності усі танки нумерувалися послідовно та унікально. Ну тобто номери у них були 1, 2, 3 і так до не відомо стільки. Але ті ж самі шпигуни давали очевидно недостовірну інформацію про кількість танків.

Якщо у нас є підбиті танки з номерами 12, 65, 34 та 51 то скільки усього таких танків було випущено?

 

Рішення задачі

Перше на що можна звернути увагу це на найбільший номер у нашому наборі – 65. З нього ми можемо сказати що було випущено як мінімум 65 танків.

Щоб зробити наступний крок треба бути трохи обізнаним зі статистикою. А саме в нагоді стане одна з теорем яка говорить що для унікальної нерозривної послідовності значень від 1 до Х якщо ми витягуємо випадкове значення то з найбільшою імовірністю ми витягнемо те що є медіаною (тобто значенням найближчим до середнього для всього набору). Уявіть собі коробку з невідомою кількістю пронумерованих кульок. Якщо ви витягуєте будь-яке значення то варто припустити що це медіана серед усіх значень бо для діапазону від 1 до Х з найбільшою імовірністю ви дістанете саме середнє значення.

Тепер ми можемо сказати що згідно максимального значення ми можемо припустити що танків було усього 130.

Час поглянути на інші значення. Важливе в них те що усі вони лежать від 65 зліва на осі Х. Враховуючи що імовірність кожного значення однакова той факт що усі вони групуються зліва означає що справжня медіана теж лежить десь зліва від максимального значення що ми його маємо. І так ми приходимо до формули N \approx m + \frac{m}{k} - 1. Тут N – кількість танків усього, m – найбільший відомий номер, k – кількість відомих номерів.

Для набору номерів наведеного вище отримаємо 80.

Більше теорії та пояснень можна знайти тут – https://en.wikipedia.org/wiki/German_tank_problem.

 

Практичні наслідки

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

Цікавим наслідком є також те що для нумерації та класифікації використовувати цілочисельні значення небезпечно і тому у військових тепер є спеціально буквено-цифрові системи в яких нумерація таки присутня, але сторонньому спостерігачеві невідомо достовірно як ті позначки переводити у послідовні номери (бо це можна зробити більше ніж одним способом).

[Задача] Воїни та меч

Задача

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

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оп-ля (:

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

Випадкове число від 0 до 2

Задача

Є функція 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; }

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

Розмір групи та імовірність народження більша за 0.5

Задача

Якого розміру має бути група людей щоб імовірність народження хоч одного з неї в ту саму дати що народилися і ви (лише ісяць і число) складала не менше 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 хвилини.