Есть идея!

19x + 5y = 100.

Какие целочисленные значения могут принимать x и y? Один из способов получить ответ на этот вопрос состоит в том, чтобы преобразовать уравнение, оставив в левой части только член с наименьшим коэффициентом при неизвестном: 5y = 100 − 19x. Разделив обе части уравнения на 5, получим у = (100 − 19x)/5. Разделим теперь 100 и 19x на 5, выделив заведомо целую часть и дробный остаток (если он существует):

y = 20 − Зx − 4x/5.

Ясно, что выражение 4x/5 должно принимать целочисленные значения. Следовательно, x должен быть кратен 5. Наименьшее кратное 5 равно 5, что соответствует y = 1 и (если вернуться к любому из двух исходных уравнений) z = 94. При остальных значениях x, кратных 5 (и больших 5), у принимает отрицательные значения. Значит, наша задача допускает единственное решение: фермер купил 5 коров, 1 свинью и 94 овцы.

Варьируя цены на коров, свиней и овец, можно самостоятельно открыть многие премудрости элементарной теории диофантовых уравнений. Предположим, например, что коровы продаются по 4 доллара, свиньи — по 2 доллара и овцы — по ⅓ доллара за голову. Сколько животных купил фермер на 100 долларов, если известно, что он купил по крайней мере 1 корову, 1 свинью и 1 овцу? Эта задача допускает 3 решения. А что можно сказать, если корова стоит 5 долларов, свинья — 2 доллара и овца — 50 центов? Оказывается, что в этом случае решения не существует.

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

Решение задачи состоит в том, чтобы, выстроив флаконы в ряд, взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 4 пилюли из третьего флакона и т. д., затем собрать все отобранные пилюли и взвесить. Предположим, что пилюли оказались на 270 мг тяжелее, чем нужно. Так как каждая пилюля с повышенной дозой лекарства тяжелее нормальной на 10 мг, то, разделив 270 на 10, мы получим 27 — число более тяжелых пилюль.

Запишем число 27 в двоичной системе: 11011. Двоичные разряды, в которых стоят единицы, говорят нам, какие степени числа 2 в сумме дают двоичное число 11011 (или десятичное число 27): 1, 2, 8 и 16. Единицы стоят в первом, втором, четвертом и пятом двоичных разрядах. Следовательно, непригодные пилюли с повышенным содержанием лекарства находятся в первом, втором, четвертом и пятом флаконах.

Двоичная система счисления находит столь широкое применение именно потому, что каждое положительное целое число можно представить в виде суммы степеней числа 2 единственным способом. Без двоичной системы счисления в наши дни немыслима работа ЭВМ. Немалую роль двоичная система играет во многих областях прикладной математики. Почетное место отведено двоичной системе и в занимательной математике.