Словник / Гармонічний ряд
Покладіть книжку на край стола й посувайте, поки вона не почне падати: нависати вона буде рівно на половину довжини. Тепер кладіть книжки одна на одну, кожну трохи далі за попередню. Здається, що далеко так не зайдеш: стос завалиться, щойно верхня книжка відійде від краю на довжину-другу. Насправді, якщо книжок вистачає, верхня може нависати над підлогою як завгодно далеко. Усе через гармонічний ряд: суму 1 + ½ + ⅓ + ¼ + …, яка росте без кінця, хоч і неймовірно повільно.
Шар «На пальцях» приховано на всіх задачах.
Додавайте книжки. Кожну нову підкладаємо знизу, а весь стос над нею зсуваємо так далеко, як тільки можна, щоб він ще не впав. Масштаб не змінюється: пунктир — довжини книжки за краєм стола. Скільки книжок треба, щоб верхня повністю вийшла за край?
Скільки книжок треба, щоб верхня нависала на:
На малюнку щонайбільше 300 книжок, решту ми порахували.
Перша книжка висувається на половину довжини, друга додає чверть, третя — шосту частину, четверта — восьму. Кожна наступна дає менше, і здається, що такі дрібниці десь зупиняться. Але вони не зупиняються. З чотирма книжками верхня вже вся над підлогою, з 31 — на дві довжини. Ціна росте страшенно: на п'ять довжин піде 12 367 книжок. Якщо кожна завтовшки 3 см, це стос заввишки 371 м, вищий за Ейфелеву вежу. Проте межі немає: будь-яку відстань можна перевищити.
Шар «Строго» приховано на всіх задачах.
Гармонічний ряд — це сума чисел, обернених до натуральних: 1 + ½ + ⅓ + ¼ + … Суму перших n доданків називають n-м гармонічним числом і позначають Hn. Ряд розбігається: Hn зростає без межі, хоча доданки прямують до нуля.
H4 = 1 + 1/2 + 1/3 + 1/4 = 25/12 ≈ 2,08 · H10 ≈ 2,93 · H100 ≈ 5,19 · H1000 ≈ 7,49
Стос книжок — це той самий ряд, лише поділений навпіл: нависання n книжок дорівнює ½ · Hn довжини книжки. З 4 книжками ½ · 25/12 = 25/24, трохи більше за одну довжину.
Порівняйте з рядом 1 + ½ + ¼ + ⅛ + …, де кожен доданок удвічі менший за попередній. Його доданки теж прямують до нуля, і навіть швидше. Але він ніколи не перейде 2: кожен крок долає лише половину відстані, що лишилася до двійки. Гармонічний ряд на перших кроках ледь від нього відстає, а потім повільно, але невпинно йде вгору. Перемкніть шкалу.
Скільки доданків треба, щоб сума перейшла задане число? Додавати по одному доданку щосекунди — і порахуйте, скільки на це піде часу.
Шар «Глибше» приховано на всіх задачах.
Близько 1350 року французький філософ Нікола Орем помітив простий прийом. Згрупуйте доданки: друга група має два доданки, третя — чотири, четверта — вісім. У кожній групі всі доданки не менші за останній, тож уся група не менша за половину.
1 + ½ + (⅓ + ¼) + (1/5 + 1/6 + 1/7 + 1/8) + … ≥ 1 + ½ + (¼ + ¼) + (⅛ + ⅛ + ⅛ + ⅛) + … = 1 + ½ + ½ + ½ + …
H2k ≥ 1 + k / 2
Половинок нескінченно багато, тож сума перевищить будь-яке число. Подивіться, як оцінка тримається знизу.
Оцінка груба: справжня сума росте швидше, ніж на ½ за групу. Але для доведення досить і цього.
Сума 1/1 + 1/2 + … + 1/n майже дорівнює площі під кривою 1/x від 1 до n, а ця площа — натуральний логарифм ln n. Різниця між ними не росте, а прямує до сталої γ ≈ 0,5772, яку назвали на честь Леонарда Ейлера. Досі невідомо навіть, чи можна записати γ звичайним дробом.
Hn = ln n + γ + 1/(2n) − …
Звідси й числа з розділу вище: щоб Hn перейшло t, треба n ≈ et − γ. Для 10 це близько 12 367, для 100 — близько 1,5 · 1043 доданків. Щоб стос книжок нависав на 50 довжин, книжок треба саме стільки.
Стос стоїть, поки спільний центр мас кожної верхньої частини лежить над книжкою під нею. Тож найдалі можна висунути так, щоб центр мас верхніх k книжок припадав рівно на край (k + 1)-ї. Нехай так і є, і рахуємо від того краю. Центр k книжок там, де край, тобто в нулі, а центр (k + 1)-ї книжки на половину довжини лівіше. Спільний центр k + 1 книжок — середнє з вагами:
(k · 0 + 1 · ½) / (k + 1) = 1 / (2(k + 1))
Саме над ним має бути край наступної книжки, отже (k + 1)-ша книжка висувається за неї на 1/(2(k + 1)). Додаючи зсуви 1/2, 1/4, 1/6, …, 1/(2n), маємо ½ · Hn. Останній зсув — над столом: центр мас усього стосу стоїть рівно на краю стола.
Це рекорд для стосу, де на кожному рівні лежить одна книжка. Якщо дозволити класти кілька книжок поруч і використовувати їх як противаги, нависання росте значно швидше: це показали Майк Патерсон і Урі Цвік у 2006 році.
Ще один парадокс. Приберіть з гармонічного ряду всі доданки 1/n, у записі n яких є цифра 9: 1/9, 1/19, 1/90, 1/199… Здається, ми викинули дрібницю, бо серед малих чисел дев'ятка трапляється рідко. Але сума стає скінченною, менше за 80. Серед d-цифрових чисел без дев'ятки їх 8 · 9d − 1, і кожне з обернених не більше за 1/10d − 1. Тож уся сума не більша за
8 · (1 + 9/10 + (9/10)2 + …) = 8 · 10 = 80
Річ у тім, що серед дуже довгих чисел майже всі містять дев'ятку. Викидаємо ми не дрібницю, а майже весь ряд. Цей ряд вивчив Обрі Кемпнер у 1914 році.
Число посередині: якщо всіх вишикувати за зростанням, половина буде нижче, половина вище.
До бару заходить мільйонер, і середній дохід відвідувачів злітає, а медіана ледь ворухнеться.
Сума всіх значень, поділена на їхню кількість: скільки дісталося б кожному, якби поділити порівну.
Майже кожна людина має більше ніг, ніж у середньому: середнє трохи менше за дві.
Середній результат, якого можна чекати, якщо повторювати те саме дуже багато разів.
У грального кубика сподівання 3,5, хоча такої грані немає.
Число від −1 до +1, що показує, наскільки дві величини рухаються разом.
Улітку ростуть і продаж морозива, і кількість утоплень. Морозиво тут ні до чого: обох розганяє спека.
Міра розкиду: наскільки значення в середньому відходять від середнього. Стандартне відхилення — корінь з дисперсії, у тих самих одиницях.
Два міста з однаковою середньою температурою: в одному весь рік близько +15, в іншому то −20, то +50.
Розподіл у формі дзвона: більшість значень біля середнього, а що далі від нього, то рідше.
Кожна кулька на дошці Гальтона падає навмання, а тисячі кульок щоразу складаються в той самий дзвін.
Що більше повторень, то ближче частка результату до його справжньої ймовірності.
Частка орлів підповзає до 50%, а різниця між орлами й решками в штуках зазвичай росте.
Шанс події за умови, що вже відомо щось інше.
Майже всі баскетболісти НБА високі, але майже всі високі люди не баскетболісти.
Події незалежні, якщо знання про одну не змінює шансів іншої.
Після п'яти орлів поспіль решка не стає ймовірнішою: монета нічого не пам'ятає.
Скільки разів треба помножити основу саму на себе, щоб отримати число: log₂ 8 = 3, бо 2 · 2 · 2 = 8.
Аркуш паперу, складений навпіл 42 рази, був би товщим за відстань до Місяця.
Вибірка, у яку одні потрапляють частіше за інших, тож вона погано описує всіх.
1936 року журнал опитав мільйони американців і все одно помилився з переможцем виборів.
Як часто сам лише випадок дав би розрив щонайменше такий, як у вас, якби різниці насправді не було.
Коли ефекту немає зовсім, p < 0,05 випадає так само часто, як p між 0,50 і 0,55.
Діапазон навколо виміряного числа, побудований методом, що накриває справжнє значення в обраній частці вибірок, наприклад у 95%.
Із двадцяти чесних 95% інтервалів у середньому один промахується, і жоден не знає, чи це він.
Імовірність, що тест помітить справжній ефект заданого розміру. Потужність 80% означає: один робочий ефект із п'яти тест пропустить.
Слабкий A/B-тест, який таки знайшов ефект, майже завжди його перебільшує: справжні +10% на дашборді стають +24%.
Наскільки зазвичай промахується середнє чи частка, пораховані з вибірки: σ, поділене на корінь з розміру вибірки.
Щоб удвічі зменшити похибку, треба вчетверо більше даних.
Наука про те, скількома способами можна впорядкувати або вибрати речі: перестановки n!, сполучення C(n, k).
Добре перетасована колода майже напевно лежить у порядку, якого ще не бачив ніхто й ніколи.
Правило, як змінювати впевненість, коли з'являються нові докази: апріорні шанси × сила доказу.
Два слабкі докази разом бувають сильними, а один яскравий нічого не важить, якщо твердження було малоймовірним.
Зростання, за якого величина щоразу множиться на те саме число, тож подвоюється через рівні проміжки часу.
Одне зернятко на першій клітинці шахівниці й подвоєння на кожній наступній: на останній клітинці стільки рису, скільки світ вирощує понад 300 років.
Рух, у якому кожен наступний крок робиться навмання: вперед чи назад, ліворуч чи праворуч.
П'яний завжди дійде додому, а птах, що літає навмання, може не повернутися ніколи.
Потік незалежних випадкових подій зі сталою середньою частотою: дзвінки, клацання лічильника, краплі дощу.
У 1944 році лондонцям здавалося, що німецькі літаючі бомби влучають прицільно, а це була звичайна випадкова купчастість.