Попробуем изменить вопрос задачи А (постановка исходного варианта этой задачи была предложена А. Шаповаловым, см. "КвШ" № 2, 1998) и решить следующую задачу: Задача В. Банкир узнал, что среди одинаковых на вид монет одна – фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую монету за s взвешиваний? А теперь нужно сделать самое трудное в решении этой задачи: угадать еще одну переменную. Сравним задачи В и 9 (постановка задачи 9 приведена в "КвШ" № 3, 1998). В задаче В каждую монету можно использовать не более двух раз, а в задаче 9 – сколько хочешь. Но можно ограничить условия и каждую монету использовать не более пяти или 10 раз. Значит, число k, обозначающее верхний предел использования каждой монеты и есть этот другой параметр. Итак, Задача С. Пусть f(s,k) – наибольшее число монет, из которых можно за s взвешиваний найти фальшивую более легкую, если разрешается каждую использовать не более k раз. Какие свойства этих чисел мы знаем? · Во-первых, f(s,s) – это наибольшее число монет, из которых можно за s взвешиваний найти фальшивую более легкую, если разрешается каждую использовать не более s раз. Но если использовать s раз и взвешиваний s, то это все равно что задача 9. Следовательно, f(s,s)= 3s · Во-вторых, если k>s, то f(s,k)=f(s,s)= 3s. Равенство k>s означает, что каждую монету использовать можно больше раз, чем взвешивать · В-третьих, рассмотрим маленькие k. Возьмем k=0(!).. Мы и ввели переменную k числа 2 переменную k чтобы рассмотреть задачу при k=0 и 1. Тогда f(s,0) - это наибольшее число монет, из которых можно за s взвешиваний найти фальшивую (более легкую). Если разрешается каждую использовать не более 0 раз, т. е. совсем нельзя использовать. Теперь ясно, что f(s,0)=1. Будем считать, что f(0,0)=1. Действительно, за 0 взвешиваний фальшивую монету можно определить, имея только одну монету.
Сведем все эти данные в таблицу (см. таблицу 1).
Теперь попробуем заполнить столбец k=1.
Число f(s,1) – это наибольшее число монет, их которых можно за s взвешиваний найти фальшивую более легкую, если разрешается каждую использовать не более одного раза. Зададим себе такой вопрос: "Если мы можем каждую монету взвешивать не более одного раза, сколько монет можно класть на чашу весов во время взвешивания?" Ясно, что класть можно только по одной. Если мы положим хотя бы по две монеты, и среди них окажется фальшивая (чашка с фальшивой пойдет вверх): то уже среди этих двух монет определить фальшивую монету никак не удастся. Мы уже использовали для монет в более легкой чашке одну попытку. Следовательно, за s попыток на весах перебывает 2s монет, и одна монета может оставаться на столе. Получаем, что
f(s,1)=2s+1.
На наши предыдущие рассуждения можно интерпретировать еще и так. Проводим одно взвешивание. Число взвешиваний уменьшилось на одно, т. е. число монет, оставшееся на столе равно f(s-1,1), а на чашечки весов можно было положить по f(s-1,0) монет (у этих монет s,k уменьшилось на единицу).
Следовательно, f(s,1)=2f(s-1,1)+f(s-1,0).
Откуда, учитывая, что f(s-1,0)=1 и f(0,0)=1, получаем ту же формулу f(s,1)=2s+1. Допишем нашу таблицу (см. таблицу 2).
Попробуйте заполнить таблицу самостоятельно.
А можно эти же рассуждения провести для k=2, т. е. вычислить f(s,2).
Проводим одно взвешивание. Число взвешиваний уменьшилось на одно. Следовательно, на столе осталось не более f(s-1,2) монет. А так как речь идет о максимальном числе монет n = f(s, 2), то число монет, оставшихся на столе, равно f(s-1,2), а на чаши весов можно было положить самое большее по f(s-1,1) монет. Следовательно,