5.14. Какое наибольшее количество натуральных чисел можно записать в строку так, чтобы сумма любых трех соседних чисел была четной, а сумма любых четырех соседних чисел – нечетной?
Решение.
Обозначим последовательные натуральные числа строки через а1, а2, а3и т. д.
По условию суммы
а1 + а2 + а3, а2 + а3 + а4, а3 + а4 + а5, а4 + а5 + а6
и другие четны. Вычитая из каждой суммы, начиная со второй, предыдущую получим, что разности
а4 - а1, а5 - а2, а6 - а3,…
четны, а следовательно, имеют одинаковую четность пары чисел
а4 и а1, а5и а2, а6и а3и т. д.
Выпишем нечетные суммы, состоящие из четырех соседних чисел: а1 + а2 + а3+ а4 = (а1 + а2 + а3)+ а4 ,
а2 + а3 + а4+ а5 = (а2 + а3 + а4)+ а5,
а3 + а4 + а5+ а6 = (а3 + а4 + а5)+ а6,…
Отсюда следует, что числа а4, а5, а6 и т. д. нечетны. Но тогда сумма а4 + а5 + а6 нечетна, а это противоречит условию.
Полученное противоречие возникает всякий раз, когда чисел не меньше шести. Попробуем взять пять чисел .
Рассуждая аналогично , устанавливаем, что числа а4, а5 нечётны, а следовательно , по предыдущему, нечетны и числа а1, а2 .Тогда, так как сумма а1 + а2 + а3 чётна , то число а3 чётно .
Сделаем ещё проверку и убедимся в том, что если взять пять чисел а1, а2, а3, а4, а5 , где число а3 чётно, а остальные нечётны, то каждая из сумм а1 + а2 + а3, а2 + а3 + а4, а3 + а4 + а5 чётна, а каждая из сумм а1 + а2 + а3 + а4 , а2 + а3 + а4 + а5 нечётна.
Ответ: 5.
5.15.Можно ли на клетчатой бумаге, закрасить 25 клеток так, чтобы у каждой из них было: а) четное, б) нечетное число закрашенных соседей? (клетки называются соседями, если у них общая сторона )
Решение.
Предположим, что удалось закрасить 25 клеток требуемым образом. Попробуем найти число общих сторон закрашенных клеток и придем к противоречию. Сосчитаем, сколько у каждой клетки общих сторон с соседями, сложим полученные числа и сумму разделим пополам (так как каждую общую сторону мы считали при этом дважды ). У каждой клетки – нечетное число соседей, и клеток 25. Сумма 25 нечетных чисел нечетна и поэтому нацело на 2 не делится.
Ответ: а) можно, б) нельзя.
Такое же рассуждение показывает, что при любом нечетном n, закрасить n клеток так, чтобы у каждой было нечетное число закрашенных соседей, невозможно. В случае любого четного n такая раскраска возможна.
5.16. Существует ли замкнутая ломаная, которая пересекает каждое свое звено ровно один раз и состоит из: а) 6 звеньев, б) 7 звеньев ?
Простые и составные числа
Натуральное число, большее 1, называется простым, если оно делится только на 1 и на само себя. Натуральное число называется составным, если оно имеет больше двух различных делителей.
Принято считать, что число 1 не относится ни к простым, ни к составным числам.
Отсюда следует, что множество натуральных чисел можно разбить на такие три подмножества: множество простых чисел, множество составных чисел и множество содержащее единственный элемент 1.
Справедлива следующая теорема.
Любое натуральное число, большее 1, можно и притом единственным образом представить в виде произведения простых чисел.
Это предложение называется основной теоремой арифметики натуральных чисел.
Среди простых делителей натурального числа могут быть равные, и их произведение можно записать в виде степени. Тогда разложение натурального числа а на простые множители можно представить в следующем виде:
a = p1k1p2k2 … pnkn,
где p1, p2,…, pn- различные простые числа, k1, k2,…, kn – натуральные.
Задачи
5.17.К двузначному числу приписали такое же число. Может ли полученное число быть простым?
5.18. К числу, являющемуся произведением двух последовательных натуральных чисел, приписали справа число 21. Докажите, что полученное число – составное.
5.19. Натуральные числа a и b таковы, что 31a = 54b. Докажите, что число a + b – составное.
Решение.
Так как число 31а делится на 54 и числа 31 и 54 – взаимно простые, то а делится на 54:a = 54n; где nÎN. Тогда
31 54n = 54b, b = 31n.
Отсюда a + b = 54n + 31n = 85n, а следовательно, число a + b является составным.
5.20. Натуральные числа a и b удовлетворяют условию 15a = 32b. Может ли число a – b быть простым? Если может – постройте пример; если не может – докажите.
5.21. Назовите все натуральные n, при которых число n4 + 4 –составное.
Решение.
Попробуем разложить выражение n4 + 4 на множители с целыми коэффициентами. Мы привыкли к тому, что сумма квадратов на множители с целыми коэффициентами не раскладывается. В данном случае это делается с помощью приема «плюс – минус» следующим образом:
n4 + 4 = (n4 + 4 + 4n2) - 4n2 = (n2 + 2)2 - 4n2 = (n2 + 2n + 2)( n2 - 2n + 2).
Очевидно, множитель n2 + 2n + 2 всегда больше 1. Второй множитель n2 - 2n + 2 может быть равным 1:
n2 - 2n + 2 = 1, n2 - 2n + 1 = 0, (n – 1)2 = 0, n = 1.
Так как при n = 1 множитель n2 + 2n + 2 принимает значение 5, являющееся простым числом, то значение n = 1 нужно отбросить.
Ответ: все n не равные 1.
5.22. Докажите, что любое число вида а = 101010…101 (n нулей, n + +1 единица, где n > 1) – составное.
Решение.
Преобразуем число а, учитывая, что всего у него 2n + 1 цифр, а следовательно, первая единица – разряда 2n:
a = 101010…101 = 102n + 102n-2 + 102n-4 +…+ 102 + 1 =
= (1/(102 -1))(102 – 1)(102n + 102n-2 +…+102 +1) =
= (1/99)(102n+2-1) = (1/99)((10n+1)2 – 1) = (1/99)(10n+1+1)( 10n+1-1).
Теперь рассмотрим два случая.
1) Пусть n четно.
Тогда сумма 10n+1+1 делится на 11, причем частное от такого деления больше 1, так как 10n+1+1 >11; разность 10n+1-1 делится на 9, причем частное также больше 1, так как 10n+1+1 >11; разность 10n+1-1 делится на 9, причем частное также больше 1. Получилось составное число
а = ((10n+1+1)/11) ((10n+1-1)/9).
2) Пусть n нечетно.
В этом случае разность 10n+1-1 делится на 102 – 1= 99 и частное больше 1, поскольку 10n+1-1 > 99.
5.23. Докажите, что все числа вида
10001,100010001,1000100010001,…
- составные.
5.24. Докажите, что число 8(35k+ 55n) – 5 при любых натуральных k и n является составным.
5.25. Какое наибольшее число простых чисел может быть среди 15 последовательных натуральных чисел, больших 2?
Решение.
Очевидно, простые числа нужно искать среди нечетных. Из 15 последовательных натуральных чисел имеется 7 или 8 нечетных. Среди любых трех последовательных натуральных чисел ровно одно делится на 3, поэтому среди 7 или 8 последовательных нечетных натуральных чисел имеется 2 или 3 числа, делящихся на 3. Если их отбросить, то останется 5 или 6 нечетных чисел.
Нужно еще убедиться, что такие 6 простых чисел возможны. Например, если взять такие 15 последовательных натуральных чисел: 3, 4, 5, 6,…, 17, то среди них – 6 простых. 3, 5, 7, 11, 13, 17.
О т в е т: 6.
5.26. Составьте из простых чисел все возможные арифметические прогрессии с разностью 6 и числом членов, большим 4.
5.27. Докажите, что все числа p, p + 2, p + 4 являются простыми только в случае, когда они образуют тройку 3, 5, 7.
Решение.
Рассмотрим несколько случаев, в зависимости от p.
При p = 2 число p +2 = 4 – составное, поэтому значение p = 2 отпадает.
При p = 3 получим тройку 3, 5, 7, о которой упоминается в условии задачи.
При p = 5 число p + 2 = 7 – простое, но число p + 4 = 9 – составное, значит, p = 5 нужно отбросить.
При p = 7 число p + 2 = 9 – составное.
При p = 11 число p + 4 = 15 – тоже составное.
Возникает предположение, что подходит только p = 3. Докажем его.
Нетрудно заметить, что значение p = 5, p = 7, p = 11 не подходили потому, что или p + 2 или p + 4 делятся на 3. Убедимся, что так будет всегда при простом p>3.
Простое число, большее 3, не делится на 3 и, следовательно, при делении на 3 может давать в остатке только 1 или 2. Рассмотрим оба случая.
1) Пусть p при делении на 3 дает в остатке 1: p = 3k + 1 (kÎN). Тогда число p + 2 = (3k + 1) + 2 = 3k = 3 делится на 3, причем частное от этого деления больше 1. Значит число p + 2 составное.
2) Пусть p = 3k + 2 (kÎN). Тогда число p + 4 = (3k + 2) + 4 = 3k + 6 – составное.
5.28. Найдите все такие p, что числа p, p + 10 и p + 20 – простые.
Задачи этого пункта – это, по существу, числовые ребусы. Своеобразие таких задач в том, что одна из двух компонент действия получается из другой путем перестановки или зачеркивания цифр.
Задачи на зачеркивание цифр в натуральном числе
5.29. Найдите все натуральные числа, которые при зачеркивании последней цифры уменьшаются в 14 раз.
Решение.
Обозначим искомое число через 10x + y, где x – количество десятков числа, y – его последняя цифра. Тогда
10x + y = 14x, y = 4x.
Так как y есть цифра, то и x – цифра, причем не превосходящая 2. Полагая x = 1, 2, находим, что соответственно y = 4, 8.