Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2008_2009/8mat_0809/spec/list_13_china_theorem.pdf Дата изменения: Sun Sep 2 20:56:17 2012 Дата индексирования: Tue Feb 5 08:00:27 2013 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п

Гимназия 1543, 8 класс, 2008-2009.

В этом листке все числа по-прежнему целые. 1) Найдите 5 последовательных натуральных чисел, первое из которых делится на 2, второе | на 3, третье | на 5, четвертое | на 7, пятое | на 11. Эту задачу удобно решать пошагово: найти сначала множество натуральных чисел, делящихся на 2 :=), из него выбрать множество пар соседних чисел, из которых первое делится на 2, а второе | на 3 и.т.д. Условие задачи можно было записать в виде системы сравнений. Ее разрешимость следует из китайской теоремы об остатках (КТО). К сожалению, предложенное на предыдущем занятии доказательство этой теоремы неконструктивно: оно убеждает в существовании решения, но не помогает его найти. Конструктивно КТО можно доказать по индукции, аналогично решению задачи 1). Аналогичный алгоритм помогает решать и системы сравнений по модулям, не являющимся попарно взаимно простыми. Но в этом случае может и не найтись чисел, удовлетворяющих системе. 2) В маленькую коро бку помещается 6 пирожных, в среднюю | 8, а в большую | 15. Если кондитер разложит все имеющиеся пирожные в маленькие коро бки, то останется 4 лишних, если в большие, то 7, а если в средние, то лишних пирожных не останется. Сколько пирожных может быть у кондитера, если известно, что их не больше 300?
3) Найдите все трехзначные числа, дающие при делении на 37 остаток 2, а при делении на 11 | остаток 5. 4) Решите a a а) a a систему 1 (mod 2 (mod 3 (mod 4 (mod сравнений: 7) 9) 10) 11)


Теория и разминка

Китайская теорема о б остатках. Системы сравнений

Листок 3.4, 1 декабря

б)

a 5 (mod 6) a 2 (mod 9) a 7 (mod 10)

в)



a 1 (mod 5) a 7 (mod 8) a 5 (mod 12)

5) При каких целых n число n2 + 3n + 1 кратно 55? Указание. Конечно, задачу можно решить, рассмотрев все возможные остатки по модулю 55. Подумайте, как сократить пере бор. 6) Генерал хочет построить для парада своих солдат в одинаковые квадратные каре (конечно, в каре должно быть более одного человека), но он не знает сколько солдат (от 0 до 4) находится в лазарете. Докажите, что у генерала может быть такое количество солдат, что он, независимо от заполнения лазарета, сумеет выполнить свое намерение. Например, войско из 9 человек можно поставить в виде квадрата 3 в 3, а если один человек болен, то в виде двух квадратов 2 в 2. Замечание. В исходной формулировке в лазарете могло находиться от 1 до 37 человек. Математически это не меняет задачу. А как согласуется такая формулировка с реальностью? 7) В китайской натурфилософии выделяются пять первоэлементов природы - дерево, огонь, металл, вода и земля, которым соответствуют пять цветов - синий (или зеленый), красный, белый, черный и желтый. В восточном календаре с древних времен используется 12-летний животный цикл так, что каждому из 12 лет в цикле соответствует одно из животных. Кроме того, каждый год проходит под покровительством одной из стихий и окрашивается в один из цветов: годы, оканчивающиеся на 0 и 1 - годы металла (цвет белый); годы, оканчивающиеся на 2 и 3 - это годы воды (цвет черный); годы, оканчивающиеся на 4 и 5 - годы дерева (цвет синий); годы, оканчивающиеся на 6 и 7 - годы огня (цвет красный); годы, оканчивающиеся на 8 и 9 - годы земли (цвет желтый). В 60-летнем календарном цикле каждое животное возникает 5 раз. С помощью китайской теоремы о б остатках о бъясните, почему оно все 5 раз бывает разного цвета.