Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/02/19.pdf Дата изменения: Fri Dec 23 19:25:05 2005 Дата индексирования: Tue Oct 2 00:11:53 2012 Кодировка: Windows-1251 Поисковые слова: программы-планетарии

ЗАДАЧНИК 'КВАНТА'

Ответ: да, существуют. Скажем, что набор чисел удовлетворяет условию U, если произведение любых двух чисел набора делится нацело на квадрат их разности. Пусть набор N = a1 , K, an состоит из чисел, удовлетворяющих данному условию U . Тогда набор N1 = = b1 , K, bn , bn+1 , где b1 = a1 , ..., bn = an , bn +1 = 0, также удовлетворяет U. Прибавим к каждому bi число с = = 2 - b1 b3 - b2 b3 - b1 ... bn +1 - bn . Получим набор N2 , состоящий из натуральных чисел и также удовлетворяющий U, так как
2

m cb
i

r

m

r

после чего Вовочка выбирает лабиринт и помещает ладью на любое поле. Верно ли, что Марья Ивановна может написать такую программу, что ладья обойдет все доступные поля в лабиринте при любом выборе Вовочки? Ответ: верно. Чтобы написать такую универсальную программу, Марья Ивановна может рассуждать таким образом. Занумеруем возможные начальные положения, т.е. пары (лабиринт, положение ладьи). Их конечное число. Составим программу P1 обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение номер 2. Применим программу P1 . Если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу P2 . Применим программу P2 к ладье в третьем начальном положении, снова допишем программу и так далее. В.Уфнаровский, А.Шаповалов

hb
2 2

gc
2
j

h

2

c

h

2

eb

на 1 j Поэтому, взяв в качестве исходного набора N1 = {1, 2}, последовательным применением указанной процедуры мы сможем получить набор из 1998 натуральных чисел, удовлетворяющий условию U. Г.Гальперин что расстояние между любыми двумя вершинами первого не больше 1, расстояние между любыми двумя вершинами второго также не больше 1, а расстояние между любыми двумя вершинами разных многоугольников больше чем 1 2 . Докажите, что многоугольники не пересекаются.

j и cb + cheb + cj eb - b j .
-b
2 j i

= bb j + i

ecb + ch - eb + cjj = ceb + b + cj делится
i j j j

М1656. Даны два выпуклых многоугольника. Известно,

М1658. Обозначим через S(x) сумму цифр числа х.

Существуют ли такие натуральные числа a, b и с, что S(a + b) < 5, S(a + c) < 5 и S(b + c) < 5, но S(a + b + + c) >50?

Обозначим через F1 и F2 данные многоугольники. Предположим, что они имеют общую внутреннюю точку. Возможны два случая. 1) Один многоугольник содержится внутри другого, скажем, F1 лежит внутри F2 . Пусть А одна из вершин F1 . Тогда, как легко видеть, найдутся три вершины Р, Q, R многоугольника F2 такие, что треугольник PQR содержит А (случай, когда А лежит на стороне треугольника PQR, легко приводит к противоречию). При этом хотя бы один из углов PAQ, QAR, RAP больше 90њ. Пусть для определенности PAQ 90њ. Тогда имеем: 2 2 2 1 PQ AP + AQ . Получаем, что, вопреки условию, 1 один из отрезков АР и AQ не больше противоречие. 2 2) Сторона одного многоугольника пересекает сторону другого. Пусть, например, сторона АВ многоугольника F1 пересекает сторону PQ многоугольника F2 . Пусть APBQ выпуклый четырехугольник (случай, когда среди точек А, В, Р, Q найдутся три, лежащие на одной прямой, легко рассматривается). Хотя бы один из его углов, скажем PAQ , не меньше 90њ. Тогда 1 PQ 2 AP2 + AQ2 , следовательно, один из отрезков 1 . Получаем противоречие. АР и AQ не больше 2 В.Дольников

Подойдут, например, числа а = 5555554445, b = = 5554445555, с = 4445555555. Убедимся в этом: S(a + +b) = S(11110000000) = 4, S(a + c) = S(10001110000) = =4, S(b + c) = S(10000001110) = 4, S(a + b + c) = =S(15555555555) = 51 > 50. Как можно придумать такие числа? Заметим, что S(2(a + b + c)) = S((a + b) + (a + c) + (b + c)) S(a + +b) + S(a + c) + S(b + c) 12. Значит, число n = 2(a + + b + c) при делении на 2 должно резко увеличить свою сумму цифр. Такое возможно, если в числе много единиц, а в частном много пятерок. Возьмем, например, n = = 31111111110, тогда S(n) = 12 и S(n/2) = 51. Разложим n n на три слагаемых с суммой цифр 4 и меньших : 2 n = 11110000000 + 10001110000 + 10000001110, а затем решим систему уравнений a + b = 11110000000, a + c = = 10001110000, b + c = 10000001110. Получим искомый пример. С.Волченков, Л.Медников

М1659*. Фигура Ф, составленная из клеток 1 Ч 1, обладает следующим свойством: при любом заполнении клеток прямоугольника m Ч n числами, сумма которых положительна, фигуру Ф можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника под фигурой Ф была положительна (фигуру Ф можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой Ф в несколько слоев.
Пусть Ф1 , ..., Фk все возможные расположения фигуры Ф в прямоугольнике. Утверждение задачи можно переформулировать так: можно взять фигуры Фi такой толщины di , i = 1, ..., k ( di рационально, возможно di = = 0), что суммарная толщина всех фигур Фi над каждой клеткой прямоугольника будет равна 1. Возможность такой переформулировки усматривается из того, что найдется такое натуральное число N, что все Ndi станут целыми неотрицательными числами. Предположим, что переформулированное утверждение

М1657. Назовем лабиринтом шахматную доску 8 Ч 8, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Марья Ивановна пишет программу конечную последовательность указанных команд и дает ее Вовочке,
5*

'