Стара задача
Задачу розглядав ще Абрахам де Муавр у XVIII столітті, пізніше П'єр-Сімон Лаплас. У XX столітті до неї поверталися Дьордь Пойя, а також Пал Ердеш і Альфред Реньї, які описали, як саме результати розподілені навколо середнього.
В альбомі 50 місць, а наліпки в пакетиках випадкові. Скільки наліпок у середньому потрібно купити, щоб заповнити весь альбом? Зафіксуйте свою відповідь, а потім перевірте її на власному альбомі, на симуляції та через п'ять пояснень.
Скільки наліпок потрібно купити, щоб зібрати альбом? Здається, що трохи більше, ніж місць в альбомі. Насправді для альбому на 50 наліпок у середньому потрібно 225, і більшість із них припадає на останні порожні місця. Перевірте це на власному альбомі, на симуляції та через п'ять пояснень.
У теорії ймовірностей це задача про збирача купонів. Вона трапляється в багатьох формах: наліпки до альбому, іграшки з шоколадних яєць, картки в пачках жуйки. Відповідь завжди однакова: кінець колекції дається найдорожче.
В альбомі 50 пронумерованих місць. Для кожного місця є своя наліпка.
Наліпки продаються в закритих пакетиках. Яка трапиться, невідомо: кожна з 50 однаково ймовірна, і кожна покупка не залежить від попередніх.
Якщо наліпка вже є в альбомі, вона стає дублікатом і йде в стос. Поки що обмінюватися ні з ким не можна.
Скільки наліпок у середньому треба купити, щоб заповнити весь альбом?
«Місць 50, отже, наліпок треба трохи більше, ну, може, 70»
Насправді в середньому потрібно 225 наліпок, у 4,5 раза більше, ніж місць. Перша половина альбому заповнюється швидко, а кожне наступне порожнє місце коштує дорожче за попереднє.
Обмін, рідкісні наліпки й купівлю останніх наліпок напряму розглянемо в раунді 5.
Зафіксуйте свою відповідь, перш ніж читати далі. Так ви побачите, наскільки сильно інтуїція промахується.
Тут з'явиться порівняння вашої відповіді з правильною.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Не рахуйте місця в альбомі. Подумайте, як часто покупка виявляється марною, коли альбом уже майже повний.
Розбийте збирання на етапи й чекайте кожну нову наліпку окремо. Коли порожніх місць k, нова наліпка випадає з імовірністю k/50, тож чекати її в середньому 50/k покупок.
Остання наліпка коштує в середньому 50 покупок, передостання 25, третя з кінця близько 17. Продовжте цей ряд до першої наліпки й оцініть суму.
Наступні раунди показують, скільки наліпок іде на альбом: ви збираєте альбом, 10 000 альбомів і пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Кожен пакетик дає кілька випадкових наліпок. Нові займають своє місце, повтори йдуть у стос дублікатів. Стежте за графіком праворуч: спочатку альбом росте швидко, а наприкінці майже кожна наліпка виявляється дублікатом.
Число в кутку клітинки показує, скільки дублікатів цієї наліпки вже лежить у стосі.
Комп'ютер заповнює тисячі альбомів і записує, скільки наліпок пішло на кожен. Стовпчики показують симуляцію, лінія показує точний розподіл.
Ключ у тому, що шанс отримати нову наліпку весь час падає. Коли бракує лише однієї, підходить тільки одна покупка з 50. Ось п'ять способів це побачити.
Шар «На пальцях» приховано на всіх задачах.
Коли бракує однієї наліпки, кожна покупка дає її з шансом 1/50. Такої події доводиться чекати в середньому 50 спроб, стільки ж, скільки місць в альбомі. Лише ця одна наліпка коштує як увесь альбом за наївним підрахунком.
Шанс, що наступна наліпка нова, дорівнює частці порожніх місць. Коли альбом заповнений на 90%, дев'ять покупок із десяти дають дублікати. Інтуїція рахує так, ніби майже кожна наліпка нова, тому й відповідає «трохи більше за 50». На 225 куплених наліпок у середньому припадає 175 дублікатів.
Шар «Строго» приховано на всіх задачах.
| n | Hₙ | ln n + 0,5772 | n·Hₙ |
|---|
Якщо скласти всі етапи, вийде n · (1/n + 1/(n−1) + … + 1/1) = n · Hₙ. Число Hₙ називають гармонічним. Воно росте дуже повільно, приблизно як ln n + 0,5772. Тому наліпок потрібно трохи більше, ніж n · ln n.
Середня кількість покупок до повного альбому: кожен етап чекає на нову наліпку, і середні етапів додаються.
Hₙ — сума обернених чисел від 1 до n. Її зручно наближати через натуральний логарифм.
Для альбому на 50 місць.
Розкид навколо середнього: дисперсія і стандартне відхилення σ.
Етап k починається, коли в альбомі вже k−1 наліпок. Тоді кожна покупка нова з імовірністю (n−k+1)/n, і чекати такої покупки доводиться в середньому n/(n−k+1) спроб. Середні значення етапів просто додаються. Розкид великий: для 50 місць половина альбомів заповнюється за 214 наліпок або менше, а приблизно кожен двадцятий потребує понад 340.
Справжні альбоми бувають на сотні наліпок. Подивимося, скільки пакетиків знадобиться для них і що реально допомагає: пакетики без повторів, обмін із друзями чи купівля останніх наліпок напряму.
Цей розмір діє і для всіх блоків нижче.
Деякі видавці обіцяють, що в одному пакетику немає двох однакових наліпок. Скільки це заощаджує?
| Тип пакетиків | Пакетиків, точно | Симуляція |
|---|
Часто видавець дозволяє замовити кілька конкретних наліпок. Ви купуєте пакетики, поки не залишиться m порожніх місць, а решту замовляєте.
Частина наліпок трапляється рідше за інші. Скільки тоді коштує альбом?
Задачу розглядав ще Абрахам де Муавр у XVIII столітті, пізніше П'єр-Сімон Лаплас. У XX столітті до неї поверталися Дьордь Пойя, а також Пал Ердеш і Альфред Реньї, які описали, як саме результати розподілені навколо середнього.
Різниця між гармонічним числом Hₙ і ln n прямує до сталої γ ≈ 0,5772. Її знають уже кілька століть, але досі невідомо, чи вона ірраціональна.
Для альбому на 50 місць перша половина наліпок коштує в середньому 34 покупки, а друга 191. Тому колекції так довго «майже завершені»: останні кілька місць забирають більшу частину грошей.
В альбомі на 640 місць останню наліпку чекають у середньому 640 покупок. Це 128 пакетиків по 5 наліпок лише заради одного порожнього місця.
Якщо двоє друзів збирають альбоми на 50 місць разом і віддають одне одному дублікати, на двох потрібно в середньому 325 наліпок, а не 450. Цей варіант відомий як «задача про подвійний стаканчик Dixie» (double dixie cup problem).
Та сама оцінка з'являється, коли питають, скільки випадкових тестів потрібно, щоб хоч раз перевірити кожен із n випадків, або скільки випадкових кидків потрібно, щоб у кожному з n кошиків опинилося хоча б щось. Відповідь у всіх випадках близько n · ln n.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Поглиблено» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.