Есть идея! - страница 17

Теория диофантовых уравнений представляет собой обширный раздел теории чисел, имеющий бесчисленные применения во многих областях науки и техники. Одна из знаменитых задач на решение диофантовых уравнений известна под названием великой (или последней) теоремы Ферма. В ней требуется найти при любых целых положительных n > 2 решение в целых числах уравнения x^>n + y^>n = z^>n (при n = 2 эти решения называются пифагоровыми тройками; существует бесконечно много пифагоровых троек, начиная с 3² + 4² = 5²). Великая теорема Ферма — наиболее известная из нерешенных проблем теории чисел. До сих пор никому еще не удалось ни найти хотя бы одно решение уравнения x^>n + y^>n = z^>n в целых числах (при n > 2), ни доказать, что такого решения не существует.

Как-то раз в аптеку доставили 10 флаконов лекарства. В каждом флаконе по 1000 пилюль. Не успел провизор мистер Уайт расставить флаконы на полке, как почтальон принес телеграмму.

Мистер Уайт читает телеграмму управляющей аптекой мисс Блек.

Мистер Уайт. Срочно. Воздержитесь от продажи лекарства. По ошибке фармацевта в одном из флаконов каждая пилюля содержит на 10 мг лекарства больше допустимой дозы. Просьба незамедлительно вернуть флакон с повышенной дозой лекарства.

Мистер Уайт встревожился.

Мистер Уайт. Нечего сказать, повезло! Теперь мне придется брать по пилюле из каждого флакона и взвешивать. Веселенькое занятие!

Тяжело вздохнув, мистер Уайт хотел было приступить к неожиданно свалившейся на него работе, как мисс Блек остановила его.

Мисс Блек. Минуточку! Взвешивать 10 раз совсем не нужно! Достаточно произвести 1 взвешивание.

Каким образом при помощи 1 взвешивания можно установить, в каком флаконе пилюли содержат повышенную дозу лекарства?

Идея мисс Блек состояла в том, чтобы взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 3 пилюли из третьего флакона…, 10 пилюль из десятого флакона…

…положить 55 отобранных пилюль на одну чашу весов и взвесить их. Предположим, что пилюли весили бы 5510 мг, или на 10 мг больше, чем следует. Тогда мисс Блек заключила бы, что среди отобранных пилюль имеется 1 пилюля с повышенной дозой лекарства, а ровно 1 пилюля была извлечена из первого флакона.

Если бы вес 55 пилюль оказался на 20 мг больше нормы, то это означало бы, что среди отобранных пилюль имеются 2 пилюли с повышенной дозой лекарства. Их можно было извлечь только из второго флакона. Так мисс Блек сумела понизить число взвешиваний до 1. Меньше не бывает!

Через 6 месяцев в аптеку доставили еще 10 флаконов того же лекарства. И на этот раз не успели распаковать коробку с флаконами, как почтальон принес телеграмму с извещением о том, что на этот раз фармацевт допустил более серьезную ошибку.

В посылке могло оказаться от 1 до 10 флаконов с пилюлями, каждая из которых на 10 мг тяжелее нормы. Мистер Уайт был вне себя от ярости.

Мистер Уайт. Что делать, мисс Блек? Ваш метод, который позволил нам так блестяще выйти из затруднения в прошлый раз, неприменим!

Мисс Блек задумалась.

Мисс Блек. Вы правы, мистер Уайт. Но если слегка модифицировать мой метод, то при помощи 1 взвешивания и на этот раз можно определить, в каких флаконах пилюли содержат повышенную дозу лекарства.

Что имела в виду мисс Блек?

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

Чтобы решить вторую задачу, необходимо воспользоваться последовательностью, которая бы сопоставляла каждому флакону отличный от других номер и обладала бы еще одним дополнительным свойством: сумма членов любой ее подпоследовательности должна быть отличной от суммы членов любой другой ее подпоследовательности. Существуют ли такие последовательности? Да, существуют. Примером может служить хотя бы геометрическая прогрессия со знаменателем 2 и первым членом 1: 1, 2, 4, 8, 16… Все члены этой последовательности — степени числа 2, причем показатель возрастает от 0 с единичным шагом. Именно эта последовательность лежит в основе двоичной системы счисления.