Стара задача
Задачу розглядав ще Абрахам де Муавр у XVIII столітті, пізніше П'єр-Сімон Лаплас. У XX столітті до неї поверталися Дьордь Пойя, а також Пал Ердеш і Альфред Реньї, які описали, як саме розкидаються результати навколо середнього.
Скільки наліпок потрібно купити, щоб зібрати альбом? Здається, що трохи більше, ніж місць в альбомі. Насправді для альбому на 50 наліпок у середньому потрібно 225, і більшість із них припадає на останні порожні місця. Перевірте це на власному альбомі, на симуляції та через п'ять пояснень.
У теорії ймовірностей це задача про збирача купонів. Її знають у багатьох формах: наліпки до альбому, іграшки з шоколадних яєць, картки в пачках жуйки. Відповідь завжди однакова: кінець колекції дається найдорожче.
В альбомі 50 пронумерованих місць. Для кожного місця є своя наліпка.
Наліпки продаються в закритих пакетиках. Яка трапиться, невідомо: кожна з 50 однаково ймовірна, і кожна покупка не залежить від попередніх.
Якщо наліпка вже є в альбомі, вона стає дублікатом і йде в стос. Поки що обмінюватися ні з ким не можна.
Скільки наліпок у середньому треба купити, щоб заповнити весь альбом?
«Місць 50, отже, наліпок треба трохи більше, ну, може, 70»
Насправді в середньому потрібно 225 наліпок, у 4,5 раза більше, ніж місць. Перша половина альбому заповнюється швидко, а кожна наступна порожня клітинка коштує дедалі дорожче.
Обмін, рідкісні наліпки й купівлю останніх наліпок напряму розглянемо в раунді 5.
Зафіксуйте свою відповідь, перш ніж читати далі. Так ви побачите, наскільки сильно інтуїція промахується.
Тут з'явиться порівняння вашої відповіді з правильною.
Кожен пакетик дає кілька випадкових наліпок. Нові займають своє місце, повтори йдуть у стос дублікатів. Стежте за графіком праворуч: спочатку альбом росте швидко, а наприкінці майже кожна наліпка виявляється дублікатом.
Число в кутку клітинки показує, скільки дублікатів цієї наліпки вже лежить у стосі.
Комп'ютер заповнює тисячі альбомів і записує, скільки наліпок пішло на кожен. Стовпчики показують симуляцію, лінія показує точний розподіл.
Ключ у тому, що шанс отримати нову наліпку весь час падає. Коли бракує лише однієї, нею виявляється одна покупка з 50. Ось п'ять способів це побачити.
Коли бракує однієї наліпки, кожна покупка дає її з шансом 1/50. Такої події доводиться чекати в середньому 50 спроб, стільки ж, скільки місць в альбомі. Лише ця одна наліпка коштує як увесь альбом за наївним підрахунком.
| 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.
Шанс, що наступна наліпка нова, дорівнює частці порожніх місць. Коли альбом заповнений на 90%, дев'ять покупок із десяти дають дублікати. Інтуїція рахує так, ніби кожна наліпка нова, тому й відповідає «близько 50». На 225 куплених наліпок у середньому припадає 175 дублікатів.
Етап 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, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.