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

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

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

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

 

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

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

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

[Задача] Співвідношення хлопчиків і дівчаток

Задача, варіант 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.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 хвилини.