Математичні парадокси
Курс «Як проходити співбесіди із задачами» · розділ 13 з 18 →

Задача про збирача купонів Альбом на 50 наліпок. Скільки доведеться купити?Купити доведеться близько 225.

В альбомі 50 місць, а наліпки в пакетиках випадкові. Скільки наліпок у середньому потрібно купити, щоб заповнити весь альбом? Зафіксуйте свою відповідь, а потім перевірте її на власному альбомі, на симуляції та через п'ять пояснень.

Скільки наліпок потрібно купити, щоб зібрати альбом? Здається, що трохи більше, ніж місць в альбомі. Насправді для альбому на 50 наліпок у середньому потрібно 225, і більшість із них припадає на останні порожні місця. Перевірте це на власному альбомі, на симуляції та через п'ять пояснень.

Вгадати відповідь
225наліпок на альбом із 50
50покупок лише на останню наліпку
Умова задачі

Уявіть: новий альбом на 50 наліпок

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

  1. 1

    Альбом

    В альбомі 50 пронумерованих місць. Для кожного місця є своя наліпка.

  2. 2

    Наліпки

    Наліпки продаються в закритих пакетиках. Яка трапиться, невідомо: кожна з 50 однаково ймовірна, і кожна покупка не залежить від попередніх.

  3. 3

    Дублікати

    Якщо наліпка вже є в альбомі, вона стає дублікатом і йде в стос. Поки що обмінюватися ні з ким не можна.

  4. 4

    Питання

    Скільки наліпок у середньому треба купити, щоб заповнити весь альбом?

Інтуїція підказує

«Місць 50, отже, наліпок треба трохи більше, ну, може, 70»

Насправді в середньому потрібно 225 наліпок, у 4,5 раза більше, ніж місць. Перша половина альбому заповнюється швидко, а кожне наступне порожнє місце коштує дорожче за попереднє.

Припущення моделі

  • Усі 50 наліпок однаково поширені.
  • Покупки незалежні одна від одної.
  • Ні обміну, ні купівлі конкретних наліпок.

Обмін, рідкісні наліпки й купівлю останніх наліпок напряму розглянемо в раунді 5.

Раунд 1 · Вгадайте

Скільки наліпок на альбом із 50 місць?

Зафіксуйте свою відповідь, перш ніж читати далі. Так ви побачите, наскільки сильно інтуїція промахується.

Тут з'явиться порівняння вашої відповіді з правильною.

Підказки

Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.

Далі розв'язок

Далі пояснення, і в ньому спойлери

Наступні раунди показують, скільки наліпок іде на альбом: ви збираєте альбом, 10 000 альбомів і пояснення. Спершу відповісти в раунді 1 чи йти далі?

Ви обрали завжди показувати всі раунди.

Раунд 2 · Збирайте альбом

Відкривайте пакетики, поки альбом не заповниться

Кожен пакетик дає кілька випадкових наліпок. Нові займають своє місце, повтори йдуть у стос дублікатів. Стежте за графіком праворуч: спочатку альбом росте швидко, а наприкінці майже кожна наліпка виявляється дублікатом.

Куплено наліпок0
Пакетиків0
Дублікатів0
Бракує0

Число в кутку клітинки показує, скільки дублікатів цієї наліпки вже лежить у стосі.

Як заповнюється альбом

ваш альбом в середньому

Раунд 3 · Симуляція

10 000 альбомів за секунду

Комп'ютер заповнює тисячі альбомів і записує, скільки наліпок пішло на кожен. Стовпчики показують симуляцію, лінія показує точний розподіл.

симуляція точний розподіл
–
Теорія: n·Hₙ
–

Скільки наліпок для альбомів різного розміру

інтуїція: n n·ln n точно: n·Hₙ, точки з симуляції

Раунд 4 · П'ять пояснень

Чому останні наліпки такі дорогі

Ключ у тому, що шанс отримати нову наліпку весь час падає. Коли бракує лише однієї, підходить тільки одна покупка з 50. Ось п'ять способів це побачити.

На пальцяхкартинки, аналогії, маленькі числа

Шар «На пальцях» приховано на всіх задачах.

Остання наліпка

Половина альбому дешева, кінець дорогий

Перші 25 наліпок34покупки в середньому
Останні 10 наліпок146покупок у середньому

Коли бракує однієї наліпки, кожна покупка дає її з шансом 1/50. Такої події доводиться чекати в 50 спроб, стільки ж, скільки місць в альбомі. Лише ця одна наліпка коштує як увесь альбом за наївним підрахунком.

Звідки дублікати

Що повніший альбом, то більше повторів

Шанс, що наступна наліпка нова, дорівнює частці порожніх місць. Коли альбом заповнений на 90%, дев'ять покупок із десяти дають дублікати. Інтуїція рахує так, ніби майже кожна наліпка нова, тому й відповідає «трохи більше за 50». На 225 куплених наліпок у середньому припадає 175 дублікатів.

Строготаблиці, графіки, формули

Шар «Строго» приховано на всіх задачах.

Розбиваємо на етапи

Кожна нова наліпка дорожча за попередню

Гармонічні числа

Сума 1 + 1/2 + … + 1/n росте як логарифм

nHₙln n + 0,5772n·Hₙ

Якщо скласти всі етапи, вийде n · (1/n + 1/(n−1) + … + 1/1) = n · Hₙ. Число Hₙ називають гармонічним. Воно росте дуже повільно, приблизно як ln n + 0,5772. Тому наліпок потрібно трохи більше, ніж n · ln n.

Для тих, хто любить формули

Точна формула, наближення і розкид

Середня кількість покупок до повного альбому: кожен етап чекає на нову наліпку, і середні етапів додаються.

E[T]=nn+nn−1+nn−2+…+n1 =n·Hn

Hₙ — сума обернених чисел від 1 до n. Її зручно наближати через натуральний .

Hn=1+12+13+…+1n ≈ln⁡n+γ+12n,γ≈0,5772

Для альбому на 50 місць.

n=50:50·H50=50·4,4992=224,96

Розкид навколо середнього: і стандартне відхилення σ.

Var[T]=n2·(1+14+…+1n2)−n·Hn n=50:σ≈62

Етап k починається, коли в альбомі вже k−1 наліпок. Тоді кожна покупка нова з імовірністю (n−k+1)/n, і чекати такої покупки доводиться в середньому n/(n−k+1) спроб. Середні значення етапів просто додаються. Розкид великий: для 50 місць половина альбомів заповнюється за 214 наліпок або менше, а приблизно кожен двадцятий потребує понад 340.

Раунд 5 · Ускладнюємо

Великі альбоми, обмін і рідкісні наліпки

Справжні альбоми бувають на сотні наліпок. Подивимося, скільки пакетиків знадобиться для них і що реально допомагає: пакетики без повторів, обмін із друзями чи купівля останніх наліпок напряму.

Розмір альбому, пакетики по 5 наліпок

Наліпок у середньому
Пакетиків
Дублікатів

Цей розмір діє і для всіх блоків нижче.

Скільки пакетиків до кожного рівня

Варіант 1

Пакетики без повторів усередині

Деякі видавці обіцяють, що в одному пакетику немає двох однакових наліпок. Скільки це заощаджує?

Тип пакетиківПакетиків, точноСимуляція

Варіант 2

Обмін дублікатами з друзями

Варіант 3

Останні наліпки купити напряму

Часто видавець дозволяє замовити кілька конкретних наліпок. Ви купуєте пакетики, поки не залишиться m порожніх місць, а решту замовляєте.

Наліпок із пакетиків
Економія

Варіант 4

Рідкісні наліпки

Частина наліпок трапляється рідше за інші. Скільки тоді коштує альбом?

Наліпок у середньому
Усі однаково часті

Бонус · Цікаві факти

Що розповісти друзям

XVIII ст.

Стара задача

Задачу розглядав ще Абрахам де Муавр у XVIII столітті, пізніше П'єр-Сімон Лаплас. У XX столітті до неї поверталися Дьордь Пойя, а також Пал Ердеш і Альфред Реньї, які описали, як саме результати розподілені навколо середнього.

0,5772

Стала Ейлера–Маскероні

Різниця між гармонічним числом Hₙ і ln n прямує до сталої γ ≈ 0,5772. Її знають уже кілька століть, але досі невідомо, чи вона ірраціональна.

34 / 191

«Майже зібрав»

Для альбому на 50 місць перша половина наліпок коштує в середньому 34 покупки, а друга 191. Тому колекції так довго «майже завершені»: останні кілька місць забирають більшу частину грошей.

128

Остання наліпка у великому альбомі

В альбомі на 640 місць останню наліпку чекають у середньому 640 покупок. Це 128 пакетиків по 5 наліпок лише заради одного порожнього місця.

325

Два альбоми не вдвічі дорожчі

Якщо двоє друзів збирають альбоми на 50 місць разом і віддають одне одному дублікати, на двох потрібно в середньому 325 наліпок, а не 450. Цей варіант відомий як «задача про подвійний стаканчик Dixie» (double dixie cup problem).

n ln n

Задача в інформатиці

Та сама оцінка з'являється, коли питають, скільки випадкових тестів потрібно, щоб хоч раз перевірити кожен із n випадків, або скільки випадкових кидків потрібно, щоб у кожному з n кошиків опинилося хоча б щось. Відповідь у всіх випадках близько n · ln n.

Fifty Challenging Problems in Probability

Фредерік Мостеллер

1965, англійською · задача 14

Understanding Probability

Генк Теймс

2004, англійською · розділ 3.2

Усі книжки →
Обговорення

Що ви думаєте?

Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.

Рівень «Поглиблено» відповідає задачі?

Дякуємо! Це допоможе точніше ставити рівні.

Розсилка

Нові задачі, пояснення й обговорення

Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.

Форма підписки з'явиться тут найближчим часом.