Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/04/35.pdf Дата изменения: Fri Dec 23 19:27:32 2005 Дата индексирования: Tue Oct 2 00:32:19 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п

'КВАНТ'

ДЛЯ

'МЛАДШИХ'

ШКОЛЬНИКОВ

35

(Начало см. на с.29) С трудом удалось его успокоить и заставить продолжать: Да! Так о чем я? А? Никто не помнит? Столько ослов вокруг, и никто не помнит, о чем я говорил? Что? О фертингах? Да, верно о четырех фертингах, провалиться им на месте! Когда этот бандит Жадинг затребовал с меня такие немыслимые деньги за пользование весами, я стал думать, как выделить фальшивую монету (если она есть) за наименьшее число взвешиваний. И сколько это взвешиваний, по-вашему? Ну, трех, видимо, хватит... стал рассуждать Скрягинс. Сначала сравнить первую монету со второй, потом вторую с третьей, потом третью с четвертой... Ну и все! Трех взвешиваний точно хватит. Значит, три взвешивания? А почему именно три? Может, хватит двух? Или одного? Одного-то уж точно не хватает! заявил Скрягинс. Почему вы так считаете? Ну... Вот видите не знаете! А я знаю! И помогла мне это узнать математика! И скажите мне теперь, что она бесполезная вещь! Как же она могла помочь? А вот послушайте. У меня 4 монеты. Пронумеруем их. Первая может быть легче или тяжелее остальных. Обозначим эти случаи так: 1Л и 1T. To же самое возможно и для каждой из остальных монет еще 6 случаев: 2Л, 2Т и так далее. Наконец, возможен и вариант, когда все монеты настоящие; обозначим его буквой Н. Таким образом, имеется всего 9 случаев: 1Л, 1T, 2Л, 2Т, ЗЛ, ЗТ, 4Л, 4Т и Н. Это понятно? Хорошо. Вот я сделал первое взвешивание (любым способом распределив монеты по чашкам весов). Здесь могут быть 3 исхода: или левая чашка перевесила, или правая, или равновесие. Понятно, что каждый из 9 случаев соответствует одному из исходов. И непременно найдется исход, которому соответствуют не меньше трех случаев. Почему это вдруг непременно найдется? Эх, голова вы садовая! Да если такого исхода не будет, то, значит, каждому исходу соответствуют не больше двух случаев, и всего случаев не больше Ч ! . А у нас-то их больше целых 9! Понятно? То-то же! Когда-нибудь я обобщу этот метод рассуждений и назову его 'принципом Скуперфильда'3. Звучит? Ладно, пойдем дальше. Так как найдется исход, которому соответствуют не меньше трех случаев, то, если он наступит, я не смогу различить эти случаи между собой результат-то взвешиваний для них всех один и тот же! Значит, одного взвешивания и вправду не хватит. Но, может быть, хватит двух? А вот здесь-то надо
3 На Земле этот метод уже обобщили и называют 'принципом Дирихле'. Он формулируется так: если N исходам соответствуют не меньше NK + 1 случаев, то найдется исход, которому соответствуют не меньше K + 1 случаев. Принцип Дирихле легко доказывается 'от противного', что и сделал Скуперфильд.