Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/04/23.pdf Дата изменения: Fri Dec 23 19:27:32 2005 Дата индексирования: Tue Oct 2 00:32:12 2012 Кодировка: Windows-1251 Поисковые слова: deep sky

ЗАДАЧНИК

'КВАНТА'

23

М1851. Нарисованы координатные оси Ох, Оу и 1 график функции y = . Масштаб не указан. Пользу8x ясь только циркулем, постройте точку (1; 1).
Пусть окружность с центром О пересекает тельную ветвь гиперболы в точках M 1 N ; a . Тогда 8a 2 2 1 1 1 MN 2 = a - + - a = 2 a2 + 8a 8a 64a Эта же окружность пересекает оси 1 M a2 + ;0 и N 0; a2 + 2 64a 1 M N 2 = 2 a 2 + и M N 64a 2 положи1 и a; 8a

после применения обеих операций в любой последовательности и в любом количестве наше число будет сравнимо по модулю 13 с некоторой степенью числа 3. Однако степени тройки дают при делении на 13 только остатки 3, 9 и 1 и не дают остатка 4, а 82 4 (mod 13 ) . Следовательно, число 82 не может быть получено с помощью указанных операций. К.Кохась М1854*. Пусть f x многочлен степени m ? 2 с целыми коэффициентами. Докажите, что множество значений многочлена f x в целых точках содержит бесконечную геометрическую прогрессию m тогда и только тогда, когда f x = a bx + c (где a, b, c целые числа, a ? 0 , b ? 0 ). Сначала убедимся в том, что множество значений многочлена m f ( x ) = a (bx + c ) (а, b, c целые числа, a 0 , b 0 ) в целых точках содержит некоторую бесконечную геометрическую прогрессию. Мы можем считать, что НОД (b, c ) = 1 . Выберем целое число x0 так, чтобы d = bx0 + c > 1 . Ясно, что НОД ( d, b ) = 1 . Пусть е какое-нибудь натуральное число, для которого de при делении на b дает в остатке 1. Поскольку НОД ( d, b ) = 1 , то такое число обязательно существует: можно, например, взять e = (b ) , где (b ) функция Эйлера (см. статью В.Сендерова и А.Спивака 'Малая теорема Ферма' в 'Кванте' ?1 за 2000 год). Положим d den - 1 . xn = x0 + b Так как d e - 1 делится на b, то для любого n = 0, 1, число xn целое. Имеем

2

1 - . 2

координат в точках 1 , откуда 64a2

2 - M N 2 =

1 . 2

Итак, мы можем построить две точки, которые служат 1 концами отрезка длины . После чего легко постро2 ить точку (1; 1), опять-таки пользуясь только циркулем. С.Токарев М1852. Дано натуральное число n. В интервале n2; n2 + n выбраны различные натуральные числа а и b. Докажите, что в этом интервале нет натуральных делителей числа ab, отличных от а и b.

(

)

(

)

Пусть d натуральный делитель числа ab из интервала n2; n2 + n . Так как ab делится на d, то число (a - d ) (b - d ) тоже делится на d. Поскольку а, b и d лежат в интервале длины n, имеют место неравенства a - d < n и b - d < n , откуда можно заключить, что

(

)

f (x

n

)

= a (bxn + c

)m

= Aq n ,

Итак, число ( a - d ) (b - d ) делится на d и по модулю меньше d, следовательно, оно равно нулю. Значит, d = =a или d = b. С.Иванов

(

a - d ) (b - d ) < n2 < d .

где A = adm , q = dem . Тем самым указанное свойство установлено. Пусть теперь

f ( x ) = am x m + am -1x

m -1

+ K + a1x + a0

М1853. С числом разрешается производить следующие операции: 1) возвести в любую натуральную степень; 2) отрезать последние две цифры, умножить образованное ими число на 3 и прибавить к числу, образованному остальными цифрами. Можно ли с помощью таких операций из числа 81 получить число 82?
Рассмотрим число n = 100а + b, где b образованное последними двумя цифрами Вторая операция переводит число n в число n1 Заметим, что 3n - n1 = 2 99a делится на 13. тельно,
n1 3n

многочлен степени m 2 с целыми коэффициентами, множество значений которого в целых точках содержит некоторую бесконечную геометрическую прогрессию. Рассмотрим многочлен

число, числа n. = a + 3b . Следова-

am ym + g ( y ) , m y - am -1 f1 ( y ) = (mam ) f = mam где g ( y ) многочлен с целыми коэффициентами, g ( y ) = 0 либо deg g ( y ) m - 2 . Множество значений многочлена f1 ( y ) в целых точках также содержит бесконечную геометрическую прогрессию (это следует m из равенства f1 ( y ) = (mam ) f (x ) , где y = am -1 + + mam x ). Покажем, что тогда многочлен g ( y ) обязан быть нулевым. Допустим, что g ( y ) 0, а для некоторой последовательности целых чисел yn и целых чисел А и q имеем
при этом A 0 , q > 1 . Очевидно, что yn (n ) . Далее мы будем считать, что числа am , А и q положительны (остальные случаи сводятся к этому).

(

m o d 13 ) ,

f1 ( y

n

)

= Aq

n

(

n = 0,1,K) ,

т.е. вторая операция по модулю 13 это умножение числа на 3. Поскольку исходное число равно 81 = 34 , то