Задача 1 (Районная олимпиада 2010, 7 класс). Возможно ли подобрать 2010 целых чисел, произведение которых равно 2, а сумма равна нулю?

Вид материала

Задача

Содержание Мерцающий кадр (МК)

Подобный материал:

• Пояснительная записка Курс по выбору "Делимость целых чисел", 33.55kb.
• Районная олимпиада по литературному чтению, 60.07kb.
• Тесты по математике ( 4 класс), 95.09kb.
• Лицензия турагента: ав 157766 Донецкая обл г. Краматорск ул. Шкадинова,, 311.56kb.
• Киева каскад 4-6 (в период с 01. 04. 10-31. 10. 10), 280.34kb.
• Контрольная работа по алгебре №1 Тема «Алгебраические уравнения. Системы нелинейных, 13.42kb.
• "Скандинавская сказка"  Стоимость тура: 895 евро + виза + каюта (100 евро 4-местная;, 158.66kb.
• Математическое ожидание М(Х) и дисперсия D(Х). Найти закон распределения этой случайной, 114.94kb.
• Реферат автор: Чубрина Екатерина Валерьевна, 29.05kb.
• Физ величина, характе­ризующая интенсивность нормальных (перпендикулярных к поверхности), 2615.59kb.

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

Задача 1 (Районная олимпиада 2010, 7 класс). Возможно ли подобрать 2010 целых чисел, произведение которых равно 2, а сумма равна нулю?

Решение. Для того, чтобы получить в произведении 2010 целых чисел двойку, среди этих чисел должно быть ровно одно число ±2, а остальные 2009 чисел – это ±1. Но теперь ясно, что сумма подобного набора чисел всегда нечетна, поскольку в нее входят одно четное число и 2009 нечетных. Поскольку ноль – четное число, то отсюда и следует, что подобрать такие 2010 целых чисел невозможно.

Как видим, при использовании уже известных нам приемов при решении задач на четность, задачка районной олимпиады оказалась вполне решабельной. Обратим внимание на еще одну задачку районной олимпиады, похожую по условию на предыдущую.

Задача 2 (Районная олимпиада 2010, 8 класс). Возможно ли подобрать 2010 целых чисел, произведение которых равно 4, а сумма равна нулю?

Решение. Для того, чтобы получить в произведении 2010 целых чисел четверку, среди этих чисел должно быть либо одно число ±4 (остальные 2009 – это ±1), либо два числа ±2 (остальные 2008 –±1). Вариант с ±4 рассматривать бесполезно из соображений четности (см. Задачу 1). Следовательно, возможным может быть лишь вариант с ±2. Такой вариант уже подобрать несложно. К примеру, такие числа: 1002 числа 1, 1006 чисел –1, а также два числа 2.

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

Подведем промежуточный итог. Использование четности в смысле инварианта нередко помогает решить, на первый взгляд, не очень-то приятные задачи. Кроме того, соображения четности могут быть крайне полезны при решении задач с рассмотрением нескольких вариантов – часть из них могут быть моментально отсеяны.

Теперь же мы вернемся к нашим обычным задачкам. И, в качестве важнейшего утверждения, рассмотрим такую задачу.

Задача 3. Докажите, что простых чисел бесконечно много. (Либо, что то же самое – докажите, что множество простых чисел бесконечно.)

Решение. Доказательство будем проводить уже привычным для нас методом от противного. Предположим, что множество простых чисел конечно. То есть пусть p₁, p₂, …, p_n – все простые числа, какие только могут быть. Тогда построим число a = p₁p₂…p_n + 1. Заметим, что при делении на любое простое число, не превышающее его, оно будет давать остаток 1. Следовательно, оно будет делиться лишь на единицу и само себя, что и означает, что построенное нами число a – простое, причем отличное от p₁, p₂, …, p_n.

Авторство этому утверждению нередко приписывают Евклиду, одному из величайших математиков древности. Некоторые современные авторы, отдавая дань уважения Евклиду, называют его наблюдение теоремой Евклида.

Раз уж мы вспомнили о Евклиде, грех не вспомнить уже известное нам еще одно его творение – алгоритм Евклида для нахождения НОД двух чисел (см. Лекцию 8).

Задача 4. Докажите, что дробь – несократима ни при каком натуральном n.

Решение. Вспомним, что дробь называют несократимой, если НОД ее числителя и знаменателя равен единице. НОД (30n + 2, 12n + 1) = НОД (12n + 1, 6n) = НОД (6n, 1) = 1. Следовательно, данная дробь несократима.

А смогли бы Вы решить эту задачу без алгоритма Евклида? Попробуйте. Далее мы рассмотрим серию базовых задач на делимость.

Задача 5. Докажите, что произведение любых трех последовательных натуральных чисел делится на 6.

Указание. Среди этих трех чисел есть хотя бы одно четное число и одно число, делящееся на 3.

Задача 6. Докажите, что произведение любых пяти последовательных чисел делится а) на 30; б) на 120.

Решение. Среди этих чисел есть число, кратное 3, есть число, кратное 5, и есть два четных числа, одно из которых делится на 4.

Мерцающий кадр (МК)*. 56a = 65b. Докажите, что a + b – составное число.

Решение (Денискин Андрей). Поскольку числа 56 и 65 взаимно просты, то из уравнения следует, что a = 65k, b = 56k, где k – некоторое целое число. Тогда a + b = 65k + 56k = 121k. Очевидно, что число 121k для любого k будет составным, поскольку 121 = 11² – составное число.

Задача 7. p – простое число. Сколько существует натуральных чисел, меньших p и взаимно простых с ним?

Решение. Всего натуральных чисел, меньших p – ровно p – 1. Заметим, что все они будут взаимно просты с p, поскольку простое число p имеет всего два делителя – единицу и самого себя (а ни одно из чисел, меньших p, не может на него делиться).

Задача 8. Докажите, что число, имеющее нечетное число делителей – точный квадрат.

Решение. Заметим, что если d – некоторый делитель числа n, то n/d – также делитель n. Таким образом, все делители числа n можно разбить на пары, то есть их число должно быть четно. Но поскольку по условию число имеет нечетное число делителей, то наше разбиение на пары должно где-то нарушиться. А нарушиться оно может лишь в случае, когда делитель d и его «пара» n/d совпадают, то есть d = n/d, откуда n = d², что и требовалось доказать.