Шрифт:
Корова стоит 10 долларов, свинья — 3 доллара, а овца — 50 центов. Фермер купил по крайней мере 1 корову, 1 свинью и 1 овцу, израсходовав на покупку всего 100 долларов. Сколько и каких животных он купил?
Пусть x — число коров, y — число свиней и z — число овец. Тогда условия задачи можно записать в виде двух уравнений:
10x + 3y + z/2 = 100,
x + y + z = 100.
Умножив правую и левую часть первого уравнения на 2, избавимся от двойки в знаменателе, после чего вычтем из первого уравнения второе. Тем самым мы исключим z и получим «укороченное» уравнение
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 доллара и овцы — по 1/3 доллара за голову. Сколько животных купил фермер на 100 долларов, если известно, что он купил по крайней мере 1 корову, 1 свинью и 1 овцу? Эта задача допускает 3 решения. А что можно сказать, если корова стоит 5 долларов, свинья — 2 доллара и овца — 50 центов? Оказывается, что в этом случае решения не существует.
Теория диофантовых уравнений представляет собой обширный раздел теории чисел, имеющий бесчисленные применения во многих областях науки и техники. Одна из знаменитых задач на решение диофантовых уравнений известна под названием великой (или последней) теоремы Ферма. В ней требуется найти при любых целых положительных n > 2 решение в целых числах уравнения xn + yn = zn (при n = 2 эти решения называются пифагоровыми тройками; существует бесконечно много пифагоровых троек, начиная с 3^2 + 4^2 = 5^2). Великая теорема Ферма — наиболее известная из нерешенных проблем теории чисел. До сих пор никому еще не удалось ни найти хотя бы одно решение уравнения xn + yn = zn в целых числах (при n > 2), ни доказать, что такого решения не существует.
Небольшой переполох в аптеке
Как-то раз в аптеку доставили 10 флаконов лекарства. В каждом флаконе по 1000 пилюль. Не успел провизор мистер Уайт расставить флаконы на полке, как почтальон принес телеграмму.
Мистер Уайт читает телеграмму управляющей аптекой мисс Блек.
Мистер Уайт. Срочно. Воздержитесь от продажи лекарства. По ошибке фармацевта в одном из флаконов каждая пилюля содержит на 10 мг лекарства больше допустимой дозы. Просьба незамедлительно вернуть флакон с повышенной дозой лекарства.
Мистер Уайт встревожился.
Мистер Уайт. Нечего сказать, повезло! Теперь мне придется брать по пилюле из каждого флакона и взвешивать. Веселенькое занятие!
Тяжело вздохнув, мистер Уайт хотел было приступить к неожиданно свалившейся на него работе, как мисс Блек остановила его.
Мисс Блек. Минуточку! Взвешивать 10 раз совсем не нужно! Достаточно произвести 1 взвешивание.
Каким образом при помощи 1 взвешивания можно установить, в каком флаконе пилюли содержат повышенную дозу лекарства?
Идея мисс Блек состояла в том, чтобы взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 3 пилюли из третьего флакона…, 10 пилюль из десятого флакона…
…положить 55 отобранных пилюль на одну чашу весов и взвесить их. Предположим, что пилюли весили бы 5510 мг, или на 10 мг больше, чем следует. Тогда мисс Блек заключила бы, что среди отобранных пилюль имеется 1 пилюля с повышенной дозой лекарства, а ровно 1 пилюля была извлечена из первого флакона.