а) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать,
имеется ли в ней хотя бы один радиоактивный шар или нет (но нельзя узнать, сколько таких шаров в кучке).
Доказать, что за 8 проверок можно выделить оба радиоактивных шара.
б) Из 11 шаров 2 радиоактивны. Доказать, что менее чем за 7 проверок нельзя гарантировать
выделение обоих радиоактивных шаров.
Начнём с аналогичной, но более простой задачи. Пусть дано $n$ шаров,
среди которых один радиоактивен; за сколько
проверок его можно выделить? Легко указать способ, позволяющий за $k$
проверок выделить один из $n=2^k$ шаров: вначале делим все шары на две равные кучки по $2^{k-1}$ шаров в каждой, проверяем одну из них и тем самым
определяем, в какой из них находится радиоактивный шар, затем эту кучку из $2^{k-1}$ шаров снова делим пополам, проверяем одну из половин и т. д. — при каждой проверке число шаров уменьшается вдвое, и после $k$ проверок мы найдём радиоактивный шар. Ясно, что если $n\lt2^k$, то тоже достаточно $k$
проверок. Итак, для того чтобы выделить один радиоактивный шар из $n$,
достаточно проделать $f_1(n)$ проверок, где $f_1(n)$ — наименьшее целое
число $k$, для которого $n\le2^k$ (другими словами, $f_1(n)$ — наименьшее
целое число, большее или равное $\log_2n$). Ниже мы увидим, что меньшего
числа проверок заведомо недостаточно.
Теперь перейдем непосредственно к решению нашей задачи. Здесь уже не удаётся получить точный результат сразу для любого $n$, и мы выясним
сначала, за сколько проверок можно выделить 2 радиоактивных шаpa из $n$,
если $n$ — небольшое число.
Для $n=3$ достаточно двух проверок; после того, как мы проверим один за другим два шара, будет уже ясно, радиоактивен ли оставшийся третий шар.
Может, конечно случиться, что первый же проверенный шар не радиоактивен, и тогда дальнейшие проверки не нужны; но нас интересует, за какое число
проверок можно выделить радиоактивные шары наверняка, при любом, даже самом
невыгодном для нас варианте их расположения. Точно так же, проверяя шары
один за другим, можно выделить два шара из 4 за 3 проверки, из 5 — за 4, из 6 — за 5, из 7 — за 6 и т. д. Впрочем, для $n=7$ можно обойтись и пятью проверками. Прежде чем читать решение дальше, попробуйте это доказать,
т. е. найти соответствующий способ поиска радиоактивных шаров. Один такой
способ (их существует несколько) указан на рисунке 1.
Рис. 1. На этом рисунке представлен способ, позволяющий за 5 проверок выделить 2 радиоактивных шара из 7. Мы считаем, что шары занумерованы числами 1, 2, $\ldots$, 7, и в каждой клетке залисываем кучку шаров, которые подвергаются проверке (иногда кучка состоит из одного шара). Например, первой проверяется кучка из трёх шаров $\{1, 2, 3\}$. У каждой проверки возможны два исхода: «есть радиоактивность» — тогда нужно идти по красной стрелке, и «нет радиоактивности» тогда по чёрной стрелке. Если клетка заштрихована, значит, дальнейшие проверки не нужны. Для каждого пути, спускающегося по стрелкам сверху вниз, в результате всех проделанных на этом пути проверок можно установить, какая именно пара шаров радиоактивна (она указана под самой нижней стрелкой). Убедитесь в этом!
Этот рисунок помогает понять, что мы понимаем под словами «способ поиска
шаров»: чтобы задать какой-то способ, нужно указать кучку шаров, которая
проверяется первой, а также указать, какую кучку проверять после каждого из возможных исходов очередного испытания на радиоактивность; другими словами,
нужно начертить диаграмму из прямоугольных клеточек и стрелок — такую же, как на рисунке 1, только, если нужно, с другим числом $k$ проверок — и вписать в каждую клетку какие-то номера шаров.
Теперь постараемся ответить на два тесно связанных между собой вопроса:
как найти способ поиска двух шаров среди $n$, состоящий из $k$ проверок,
если такой способ существует; если его не существует, то как это доказать?
В принципе для любых конкретных $n$ и $k$ эти вопросы можно
решить «полным перебором»: перепробовать один за другим все возможные
способы заполнить клетки диаграммы, соответствующей $k$ проверкам,
подмножествами из $n$ шаров (ведь таких способов существует конечное число!)
и для каждого из этих способов проверить, позволяет ли он выделить
радиоактивные шары или нет (т. е. будут ли разным предположениям: какая
именно пара шаров радиоактивна — соответствовать разные пути по стрелочкам
сверху вниз). Но число таких способов даже при небольших $n$ и $k$ настолько
велико, что практически проделать «полный перебор» невозможно даже с помощью
вычислительной машины (например, при $n=11$ и $k=7$ заполнить клетки
диаграммы кучками можно более чем $10^{400}$ разными способами!). Мы покажем
сейчас, как можно этот перебор сильно сократить.
Вернёмся снова к рисунку 1. От самого нижнего ряда клеточек,
соответствующего последней, пятой проверке, отходит $2^5=32$ стрелки. В общем случае, для $k$ проверок, их будет $2^k$. Если способ поиска,
записанный на диаграмме, гарантирует выделение радиоактивных шаров, то каждой из этих стрелочек соответствует только один из возможных вариантов
ответа: какие именно два шара радиоактивны (но, может быть, разным
стрелочкам соответствует один и тот же вариант). Поэтому число различных
возможных вариантов ответа заведомо не больше числа стрелочек, т. е. не больше $2^k$.
Сформулируем это основное соображение так:
Если число возможных вариантов больше
$2^k$, то не существует способа, позволяющего за $k$ проверок выделить один
из этих вариантов.
То же самое можно сказать так:
Если существует способ, позволяющий за $k$
проверок выбрать один вариант из $N$ возможных, то $N\le2^k$.
(Последнее неравенство можно записать ещё и так: $k\ge f_1(N)$.)
Конечно, это правило применимо к любой задаче, где нужно выбрать один
вариант из $N$ по результатам нескольких проверок; важно лишь то, что каждая
проверка имеет два возможных исхода (в нашей задаче эти исходы таковы: «есть
радиоактивность» и «нет радиоактивности»). В частности, из этого правила
следует, что нельзя выделить один радиоактивный
шар из $n$ менее чем за $f_1(n)$ проверок: если $f_1(n)=k$, то $2^{k-1}\lt
n$, а различных вариантов в этой задаче существует $n$ (радиоактивен 1-й
шар, радиоактивен 2-й шар, ..., радиоактивен $n$-й шар).
Вернёмся снова к задаче, где имеется два радиоактивных шара. Сколько
здесь различных вариантов? На рисунке 1, где мы выбираем 2 шара из 7, число вариантов равно 21. В общем случае существует
$C_n^2=\dfrac{n(n-1)}2$ вариантов выбрать 2 шара из $n$. Из нашего
основного правила, напечатанного выше на розовом фоне, следует, что если
можно за $k$ проверок выделить 2 шара из $n$, то $\dfrac{n(n-1)}2\le2^k$. Условимся обозначать наименьшее число проверок,
необходимое для выделения 2 шаров из $n$, через $f_2(n)$. Тогда
последнее неравенство можно записать так:
$$
\begin{gather*}
f_2(n)\ge f_1\left(\dfrac{n(n-1)}2\right).\\[9pt]
\begin{array}{|c|cccccc|}
\hline\\[-8pt]
n&3&4&5&6&7&8\\\\[-8pt]
\hline\\[-8pt]
\dfrac{n(n-1)}2&3&6&10&15&21&28\\\\[-8pt]
\hline\\[-8pt]
f_1\left(\dfrac{n(n-1)}2\right)&2&3&4&4&5&5\\\\[-8pt]
\hline\\[-8pt]
f_2(n)&2&3&4&5&5&6\\\\[-8pt]
\hline
\end{array}
\end{gather*}
$$
Из таблицы видно, что при некоторых $n$ (например, при $n=6$, $n=8$)
здесь возможно и строгое неравенство. Действительно, для того чтобы за $k$
проверок можно было найти 2 радиоактивных шара среди $n$, мало того, чтобы
выполнялось неравенство $\dfrac{n(n-1)}2\le2^k$. Нужно ещё, чтобы таких
вариантов, для которых первая проверка дала результат «$+$» (есть
радиоактивность), было не больше $2^{k-1}$ и таких, для которых она дала
результат «$-$» (нет радиоактивности), тоже было бы не больше $2^{k-1}$, —
ведь иначе, согласно основному правилу, мы не сможем за $k-1$ проверок
выбрать из этих вариантов один! Точно так же каждому из исходов «${+}{+}$»
(1-я проверка «$+$», 2-я проверка «$+$»), «${+}{-}$», «${-}{+}$», «${-}{-}$»
должно соответствовать не более $2^{k-2}$ вариантов и т. д.
Мы вернёмся к решению этой задачи в следующем номере журнала.
(Продолжение решения, см. «Квант» № 3, стр. 33.)
Напомним, что через $f_1(n)$ мы сбозначили наименьшее целое число, большее
или равное $\log_2n$ (оно равно наименьшему числу проверок, за которое можно
выбрать один радиоактивный шар из $n$), через
$f_2(n)$ — наименьшее число проверок, за которое можно выбрать
два радиоактивных шара из $n$.
Рис. 1
На рисунке 1 приведён способ, позволяющий выделить
2 шара из 7 за 5 проверок.
Утверждение задачи М28а) состоит в том, что $f_2(19)\le8$ (верное
решение этой задачи прислал нам восьмиклассник В. Кривицкий из д. Клетное Минской обл.); М28б) эквивалентно тому, что $f_2(11)\ge7$. Ниже мы очень коротко докажем, что $f_2(6)\ge5$;
$f_2(8)\ge6$; $f_2(11)\ge7$; $f_2(10)\le6$; $f_2(15)\le7$; $f_2(21)\le8$.
Читатели, которые хотят убедиться в том, что все числа в нижней строке
таблицы
$$
\colsep{2pt}{
\begin{array}{|c|ccccccccccccccccccccccc|}
\hline\\[-8pt]
n&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25\\
\\[-8pt]\hline\\[-8pt]
\dfrac{n(n-1)}2&3&6&10&15&21&28&36&45&55&66&78&91&105&120&136&153&171&190&210&231&253&276&300\\
\\[-8pt]\hline\\[-8pt]
f_1(n)&2&2&3&3&3&3&4&4&4&4&4&4&4&4&5&5&5&5&5&5&5&5&5\\
\\[-8pt]\hline\\[-8pt]
f_1{\left(\dfrac{n(n{-}1)}2\right)}&2&3&4&4&5&5&6&6&6&7&7&7&7&7&8&8&8&8&8&8&8&9&9\\
\\[-8pt]\hline\\[-8pt]
f_2(n)&2&3&4&5&5&6&6&6&7&7&7&7&7&8&8&8&8&8&8&8&9&9&9\\
\\[-8pt]\hline
\end{array}}
$$
верны, должны будут доказать, кроме того, что $f_2(16)\ge8$; $f_2(22)\le8$;
$f_2(23)\ge9$; $f_2(25)\le9$ (действительно, ясно, что функция $f_2$
неубывающая, т. е. если $m\gt n$, то $f_2(m)\ge f_2(n)$, поэтому достаточно
правильно указать те значения $n$, для которых $f_2(n+1)$ строго больше
$f_2(n)$.
Прежде чем доказывать обещанные неравенства, заметим, что определение точного значения $f_2(n)$ для любого $n$ в этой задаче; как и во многих других похожих задачах, не слишком интересно. Дело в том, что соответствующий способ выделения шаров, по-видимому, очень сложен. С другой
стороны, легко указать совсем простые алгоритмы выделения шаров, требующие
лишь ненамного большего, чем $f_2(n)$, числа проверок. Например, если
сначала выбрать один радиоактивный шар, затем выбросить его и из оставшихся
выбрать другой, то на это уйдёт не более $f_1(n)+f_1(n-1)$ проверок, и, как нетрудно показать, разность $f_1(n)+f_1(n-1)-f_1(C_n^2)$ всегда не больше 2,
следовательно, разность $f_1(n)+f_1(n-1)-f_2(n)$ тоже не больше 2. В практических задачах, подобных этой, если само число проверок $k$ не слишком
мало, одна или две лишние проверки скорее всего не будут играть особой роли,
лишь бы способ проверки был попроще (скажем, для $n=15$ мы уже не можем
уместить на журнальной странице диаграмму, подобную рисунку 1, и разобраться в описании способа проверки становится нелегко).
Ниже мы используем такие обозначения: знак «$-$» обозначает,
что в проверяемой кучке нет радиоактивных шаров, а знак «$+$» — что они есть.
За 4 проверки нельзя выделить 2 шара из 6
Пусть первой проверяется кучка из $6-q$ шаров, где $q=2$, 3, 4 или 5.
Тогда исходу «$-$» соответствует $C_q^2$ вариантов (оба радиоактивных шара
среди $q$ остальных), исходу «$+$» — $(C_6^2-C_q^2)$ вариантов. Одно из этих
чисел больше $2^3=8$.
За 5 проверок нельзя выделить 2 шара из 8
Если $C_q^2\lt2^4=16$ и $C_8^2-C_q^2\lt16$, то $q$ может быть равно
только 6. Если исход «$-$», то при этом осталось выделить 2 шара из 6,
что невозможно за 4 проверки.
За 6 проверок нельзя выделить 2 шара из 11
Если $C_q^2\lt2^5=32$ и $C_{11}^2-C_q^2\lt32$, то $q=8$, но $f_2(8)\ge6$.
За 6 проверок можно выделить 2 шара из 10
Первая проверка — кучка из 4 шаров $\{\text{1—4}\}$. «$-$» за 5 проверок
2 шара из 6 $\{\text{5—10}\}$. «$+$» проверяем $\{\text{4—6}\}$. «${+}{-}$»
за 4 проверки 2 шара из 7 $\{\text{1—3}, \text{7—10}\}$, если известно, что $\{\text{1—3}\}$ дают «$+$» (см. левую половину рис. 1).
«${+}{+}$» проверяем $\{5, 6\}$. «${+}{+}{-}$» за 3 прοверки 1 шар из $\{\text{1—3}, \text{7—10}\}$. «${+}{+}{+}$» за 1 проверку 1 шар из $\{5, 6\}$ и за 2 — 1 из $\{\text{1—4}\}$.
За 7 проверок можно выделить 2 шара из 15
Первая проверка $\{\text{1—5}\}$. «$+$» проверяем $\{\text{5—9}\}$.
«${+}{-}$» за 5 проверок 2 шара из 10 $\{\text{1—4},\text{10—15}\}$, среди
которых $\{\text{1—4}\}$ дают «$+$» (см. 10 шаров, «$+$»). «${+}{+}$»
проверяем $\{5\}$. «${+}{+}{+}$» за 4 проверки 1 из $\{\text{1—4},\text{6—15}\}$. «${+}{+}{-}$» за 2 проверки 1 из $\{\text{1—4}\}$ и за 2 проверки 1 из $\{\text{6—9}\}$.
За 8 проверок можно выделить 2 шара из 21
Первая проверка $\{\text{1—6}\}$. Кроме обозначенных на рисунке и очевидных проверок, укажем такие. «${+}{-}$» за 6 проверок 2 из 15
$\{\text{1—5}, \text{12—21}\}$, среди которых $\{\text{1—5}\}$ дают «+» (см. 15 шаров, «$+$»). «${+}{+}{-}{-}$» за 2 проверки 1 из $\{\text{1—4}\}$ и за 2 проверки 1 из $\{\text{8—11}\}$.
