Задача 2. На чудо-яблоне садовник вырастил 25 бананов и 30 апельсинов. Каждый день он срывает два плода и на их месте вырастает новый, причем если он срывает два одинаковых фрукта, то вырастает апельсин, а если два разных, то вырастает банан. Каким может оказаться последний фрукт на этом дереве?
Задача 3. Обычный комплект домино содержит 28 костей. Если бы количество очков на костях изменялось бы не от 0 до 6, а от 0 до 4, то количество костей было бы лишь 15. (Проверьте.) А сколько костей содержит комплект домино, количество очков у которого меняется от 0 до 12?
Задача 4. Отец и сын наблюдали солнечное затмение, и поэтому темой их разговора были Солнце и Луна. «Папа, - спросил мальчик, - а во сколько раз Солнце дальше от нас, чем Луна?»
«Насколько я помню,- отвечал отец,- в 387 раз».
«Тогда я могу посчитать, во сколько раз объем Солнца больше объема Луны».
«Пожалуй, ты прав»,- подумав, ответил отец.
Во сколько же раз объем Солнца больше объема Луны?
Задача 5. Взяв у сестренки-первоклассницы по одной карточке с цифрами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Гена разложил их по две на столе и вдруг увидел, что полученные числа относятся как 1:2:3:4:5. Когда вечером он захотел показать этот интересный результат отцу, то обнаружил, что отсутствует карточка с цифрой 0. Однако, подумав, он из оставшихся карточек сложил пять чисел, отношение которых вновь было 1:2:3:4:5. Как он раскладывал карточки в первый и во второй раз?
ДЕЛИМОСТЬ
Делимость – одно из основных понятий, изучаемых в теории чисел (см. Чисел теория). Говорят, что целое число a делится на целое b≠0, если частное a/b является целым, т. е. существует такое целое число c, что a = bc. Например, 54 делится на 6, так как 54 = 6·9; 273 делится на 21, так как 273 = 21·13. Из определения делимости следует, что число 0 делится на любое число, отличное от нуля.
Часто утверждение о делимости числа a на число b выражают другими равнозначными словами: a кратно b, b - делитель a или же b делит a.
Всякое целое число a делится по крайней мере на четыре числа a, -a, 1, -1. Натуральное число a называется простым, если никаких других делителей оно не имеет.
Приведем несколько свойств делимости:
а) если числа a и b делятся на c, то и числа a+b, a-b делятся на c;
б) если a делится на b и c - произвольное целое число, то ac делится на bc;
в) если a делится на b и b - на c, то a делится на c.
Зная разложения чисел a и b на простые множители, можно легко выяснить, делится ли a на b. Для того чтобы число a делилось на число b, необходимо и достаточно, чтобы каждый простой множитель, входящий в разложение числа b, входил и в разложение числа a; причем если простой множитель встречается k раз в разложении числа b, то он должен встретиться не менее k раз и в разложении числа a.
Если целые числа a и b заданы своими записями в десятичной системе счисления, то, разделив «в столбик» первое число на второе, мы найдем их частное, а значит, сможем ответить на вопрос, делится ли a на b.
Уже давно были найдены признаки делимости чисел, которые позволяют в некоторых случаях быстро установить делимость одного числа на другое, не прибегая к непосредственному делению «в столбик». Среди этих признаков практически наиболее удобны следующие (связанные с записью числа в десятичной системе):
а) для делимости на 2 нужно, чтобы последняя цифра числа делилась на 2;
б) для делимости на 3 нужно, чтобы сумма цифр числа делилась на 3;
в) для делимости на 4 нужно, чтобы число, записанное двумя последними цифрами, делилось на 4;
г) для делимости на 5 нужно, чтобы последняя цифра была 0 или 5;
д) для делимости на 8 нужно, чтобы число, записанное тремя последними цифрами, делилось на 8;
е) для делимости на 9 нужно, чтобы сумма цифр делилась на 9;
ж) для делимости на 10 нужно, чтобы последняя цифра была 0;
з) для делимости на 11 нужно, чтобы разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11.
Развитие идеи делимости привело к понятию сравнения, использование которого позволило перенести в теорию чисел алгебраические методы и с их помощью получить большое количество интересных результатов.
ДИОФАНТОВЫ УРАВНЕНИЯ
Диофантовыми уравнениями называют алгебраические уравнения или системы алгебраических уравнений с целыми коэффициентами, для которых надо найти целые или рациональные решения. При этом число неизвестных в уравнениях должно быть не менее двух (если не ограничиваться только целыми числами). Диофантовы уравнения имеют, как правило, много решений, поэтому их называют неопределенными уравнениями. Это, например, уравнения:
3x + 5y = 7;
x2 + y2 = z2
3x3 = 4y3 = 5z3
Названы они по имени греческого математика Диофанта, жившего в III в. Его книга «Арифметика» содержала большое количество интересных задач, ее изучали математики всех поколений. Книга сохранилась до наших дней, ее можно найти в русском переводе в библиотеке.
Задачи поиска целочисленных и рациональных решений обычно тесно связаны между собой. Легко сообразить, какая связь есть между целочисленными решениями уравнения 3x3 + 4y3 = 5z3 и рациональными решениями уравнения 3/5 u3 + 4/5 v3 ( u = x/z, v = y/z).
К диофантовым уравнениям приводят задачи, по смыслу которых неизвестные значения величин могут быть только целыми числами.
Решение уравнений в целых числах – очень увлекательная задача. С древнейших времен накопилось много способов решения конкретных диофантовых уравнений, однако только в нашем веке появились общие приемы их исследования. Правда, линейные диофантовы уравнения и диофантовы уравнения 2-й степени научились решать давно.
Так, легко доказать, что по формулам x=4+5t, y = -1-3t (t - любое целое число) находятся все целочисленные решения уравнения 3x + 5y = 7. Формулы для нахождения целочисленных сторон прямоугольного треугольника (т.е. для решения уравнения x2 + y2 = z2) были известны еще древним индийцам: x = 2uv, y = u2 - v2, z = u2 + v2 (u и v - целые числа, u>v).
Решения диофантовых уравнений более высоких степеней, а также систем уравнений давались с большим трудом. Знаменитое уравнение П. Ферма, которое более трехсот лет назад он написал на полях «Арифметики» Диофанта, xn + yn = zn(n>2) не решено до сих пор (см. Ферма великая теорема).
Даже при n = 3 диофантовы уравнения поддаются решению с большим трудом, причем ответы могут быть совершенно разными. Так, уравнение 3x3 + 4y3 = 5z3 совсем не имеет решений в целых числах, кроме нулевого. Уравнение x3+y3=2z3 имеет конечное число решений в целых числах, которые легко найти. Уравнение x3+y3=9z3 имеет бесконечно много целочисленных решений, однако написать для них формулы далеко не просто.
Правда, оказалось, что кубические уравнения стоят в некотором смысле особняком. В 20-е гг. нашего века английский математик Е. И. Морделл высказал гипотезу, что уравнение более высокой степени, чем 3, должно иметь, как правило, конечное число целочисленных решений. Эта гипотеза была в 1983 г. доказана голландским математиком Г. Фалтингсом. Тем самым подтвердилось, что уравнение Ферма xn + yn = zn при всяком n>2 имеет лишь конечное число решений в целых числах (без общих множителей). Однако пока нет способа найти эти решения.
Долгое время надеялись отыскать общий способ решения любого диофантова уравнения. Однако в 1970 г. ленинградский математик Ю. В. Матиясевич доказал, что такого общего способа быть не может.
Решение уравнений в целых числах – один из самых красивых разделов математики. Ни один крупный математик не прошел мимо теории диофантовых уравнений. Ферма, Эйлер и Лагранж, Дирихле и Гаусс, Чебышев и Риман оставили неизгладимый след в этой интереснейшей теории.
ДИРИХЛЕ ПРИНЦИП
Этот принцип утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N > n, то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика П. Г. Л. Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.
По традиции в популярной литературе принцип Дирихле объясняют на примере «зайцев и клеток»: если N зайцев сидят в n клетках и N > n, то хотя бы в одной клетке сидит более одного зайца. Часто применяют обобщение принципа Дирихле: если зайцев N > nk, то хотя бы в одной клетке сидит более k зайцев. Самая популярная задача на прямое применение принципа Дирихле такова: на Земле живет 3 млрд. человек, у каждого на голове – не более миллиона волос (цифры условные). Нужно доказать, что обязательно найдутся два человека с одинаковым числом волос. А какое число людей с одинаковым числом волос можно гарантировать?
На той же идее основано доказательство того, что при обращении обыкновенной дроби p/q, p < q, q > 0 в десятичную получается или конечная, или бесконечная периодическая десятичная дробь, причем длина периода не превосходит q - 1. Будем делить p на q «уголком» и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то не позже, чем на (q - 1)-м шагу начнут повторяться остатки, а вслед за этим – и цифры в частном.