Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/04/29.pdf Дата изменения: Fri Dec 23 19:24:41 2005 Дата индексирования: Tue Oct 2 00:11:39 2012 Кодировка: Windows-1251 Поисковые слова: жбъпчщк хзпм

ЗАДАЧНИК

'КВАНТА'

29
l =b k
2- k l

0111 2 1001 2 , 1110 = 14. 2 1110 2

Конструкция первой из этих таблиц несложным образом обобщается: если А серебряная таблица n Ч n, то построим таблицу D размерами 2n Ч 2n так: D = AB = C A , где таблица В получена из А добавлением 2n к каждому ее элементу, а С получена из В заменой всех ее элементов, стоящих на главной диагонали, на 2n. Таблица D будет серебряной. Действительно, пусть i n (другой случай разбирается аналогично). Рассмотрим i-й крест таблицы D. Он состоит из i-го креста А, i-й строки В и i-го столбца С; i-й крест А содержит числа 1, 2, ..., 2n 1, а i-я строка В и i-й столбец С содержат числа 2n, 2n + 1, ..., 4n 1. Замечания 1. Серебряные таблицы существуют для всех четных n. 2. Приведем еще один способ построения серебряной таблицы 2n Ч 2n . Для целых неотрицательных чисел а и b обозначим через a b число, полученное следующим образом: запишем а и b в двоичной системе счисления, добавив, если это необходимо, слева нули так, чтобы число разрядов совпадало; затем сложим числа 'в столбик', но не учитывая переносов, т.е. поразрядно, а результат вновь запишем в десятичной системе. Например: 7 9 = 14, так как 7 = 1112 , 9 = 10012 ,

2-й случай. k 2l < 0. Из (2) получаем, что где 2
2l

,

FG H

IJ K

k > 0, т.е. k = 1. Тогда b = al , aa = aal , l a2l -1 = l, следовательно, l 22l -1 , что невозможно при l 2. Ответ: {(1, 1); (16, 2); (27, 3)}.

М1630. Для любого натурального числа n обозначим через f(n) число способов представления числа n в виде суммы целых неотрицательных степеней числа 2. Преставления, отличающиеся лишь порядком слагаемых, считаются одинаковыми. Например, f(4) = 4, так как число 4 может быть представлено следующими четырьмя способами: 4; 2 + 2; 2 + 1 + 1; 1 + 1 + + 1 + 1. Докажите, что для любого целого числа n 3 2 2 2n 4 < f 2n < 2n 2 . Если n = 2k + 1 любое нечетное число, большее 1, то каждое его представление в требуемом по условию задачи виде содержит 1 в качестве слагаемого. Убрав эту единицу, мы получим представление числа 2k. Верно, очевидно, и обратное. Следовательно,

di

f 2k + 1 = f 2k .

b

g bg

(1)

Занумеруем числами от 0 до 2n 1 строки и столбцы таблицы (сверху вниз и слева направо соответственно). Запишем в клетку, стоящую на пересечении i-й строки и j-го столбца число

aij =

R S T

i j + 1 при j i, i j + 2n при j > i.

Если n = 2k любое четное число, то каждое его представление в требуемом виде принадлежит к одному из двух типов: либо оно содержит слагаемое 1, либо не содержит таких слагаемых. В первом случае, убрав одно слагаемое 1, мы получим представление числа 2k 1. Как и выше, легко заметить, что есть взаимно однозначное соответствие между всеми представлениями числа 2k 1 и представлениями числа 2k первого типа. Во втором случае мы можем разделить все слагаемые на 2 и получить представление числа k. Это соответствие также взамно однозначно. Итак,
f 2k = f 2k - 1 + f k .

Полученная таблица будет серебряной. М1629. Найдите все пары (a, b) целых чисел а 1, b 1, удовлетворяющих уравнению

bg b

g bg

(2)

a

eb 2 j

= ba .

2 a 2 Из равенства ab = ba следует, что а = ba b . Пусть 2 b kl k b2 = , где (k, l) = 1. Тогда а = bk l , bk l = beb j , l

di
.

Обе полученные формулы выполнены для всех натуральных k 1 . Очевидно, что f(1) = 1. Пусть по определению f(0) = 1, тогда формула (1) выполнена и при k = 0. Заметим еще, что из (1) и (2) следует, что f(n) не убывает. Согласно (1), число f(2k 1) в (2) можно заменить на f(2k 2), откуда f(2k) f(2k 2) = f(k) для k = 1, 2, 3, ... Суммируя эти равенства от 1 до n, получаем, что f(2n) = f(0) + f(1) + ... + f(n), n = 1, 2, 3, ... (3) В правой части (3) каждое слагаемое не больше последнего, а так как 2 = f(2) f(n) для n 2 , то

b

kb2 l

=b

bk l

(1)

Если b = 1, то и а = 1. Если же b > 1, то из (1) вытеk2 кает, что b = bk l , т.е. l k = bk l - 2 . (2) l k 1-й случай: k - 2l 0 . Тогда из (2) следует, что l целое, поэтому l = 1 (так как (k, l) = 1), т.е. а = bk , k = bk - 2 . (3)

f 2n = 2 + f 2 + K + f n 2 + n - 1 f n
n = 2, 3, 4, ...

bg di

b gh b g b g cbg f bng + bn - 1gf bng = nf bng для di
-1

Следовательно,

Из неравенства bk - 2 2k - 2 > k при k 5 получаем, что (3) возможно лишь при k < 5. Перебором убеждаемся, что k = 4, b = 2, a = 16 или k = 3, b = 3, a = 27.
8 Квант ?4

f 2n 2n -1 f 2n

2n -1 2n

-2

f 2n

di
-2

K f 2 =2

... 2b

n -1 + n - 2 +...+1

gb g

bg

n n -1 2

bg

2.