Когда счастливый жетон гарантирован

Чтобы получить гарантию, рассмотрите самый неудачный порядок: сначала выходят все несчастливые жетоны.

Посчитайте отдельно кратные $11$ и кратные $48$. Какие номера попадут в оба подсчёта и что с ними нужно сделать?

1. Считаем счастливые номера

Гарантия появляется после того, как исчерпаны все несчастливые жетоны. Сначала посчитаем счастливые, вычтем их число из 1500, а к числу оставшихся прибавим один.

Кратных $11$ ровно $136$, а кратных $48$ ровно $31$. Проверим последние подходящие и первые неподходящие номера:

$$\begin{aligned} 11\cdot136&=1496\le1500,\\ 11\cdot137&=1507>1500,\\[4pt] 48\cdot31&=1488\le1500,\\ 48\cdot32&=1536>1500. \end{aligned}$$

Числа $11$ и $48$ взаимно просты, поэтому общие кратные делятся на $11\cdot48=528$. Среди наших номеров их два: $528$ и $1056$; следующее, $1584$, уже больше $1500$.

2. Убираем повторный подсчёт

Каждый из двух общих кратных попал в оба подсчёта. Чтобы учесть каждый счастливый жетон один раз, вычтем пересечение:

$$136+31-2=165.$$

Тот же итог виден по областям рисунка, а в модели — на последнем шаге. Только на $11$, но не на $48$, делятся $136-2=134$ номеров. Только на $48$, но не на $11$, делятся $31-2=29$ номеров; ещё $2$ номера общие:

$$134+2+29=165.$$

Во всём левом круге $134+2=136$ жетонов, во всём правом — $29+2=31$.

Круги ЭйлераУвидеть, откуда берётся двойной счёт

Считаем одни и те же жетоны с номерами от 1 до 1500. Каждый круг содержит все номера, делящиеся на указанное число.

Несчастливые жетоны находятся вне обоих кругов. Их число:

$$1500-165=1335.$$

3. Доказываем минимум

Можно сначала вытащить все $1335$ несчастливых жетонов — такое вытаскивание ещё не гарантирует успеха. После $1336$ вытаскиваний все жетоны не могут быть несчастливыми, потому что их всего $1335$. Значит, хотя бы один счастливый обязательно найдётся.

$1336$

Гарантия появляется на один шаг позже, чем заканчивается самый длинный возможный неудачный исход.

Вопрос «сколько нужно взять, чтобы наверняка» предлагает сначала посчитать, сколько можно взять без нужного свойства.

Сложить $136$ и $31$ без вычитания пересечения: жетоны $528$ и $1056$ тогда окажутся посчитаны дважды.

В других задачах на гарантированный выбор отделяйте две части: покажите неудачный выбор на один объект меньше и докажите, что следующий объект уже вынужден иметь нужное свойство.

Проверены все номера 1–1500; счастливых 165. Нижняя граница подтверждена выбором всех 1335 несчастливых, верхняя — невозможностью взять 1336 несчастливых.