|
|
 |
Условие
По окружности выписаны n чисел x1, x2, ..., xn, каждое из которых равно 1 или –1, причём сумма произведений соседних чисел равна нулю и вообще для каждого k = 1, 2, ..., n – 1 сумма n произведений чисел, отстоящих друг от друга на k мест, равна нулю
(то есть x1x2 + x2x3 + ... + xnx1 = 0,
x1x3 + x2x4 + ... + xnx2 = 0, x1x4 + x2x5 + ... + xnx3 = 0 и так далее; например, для n = 4 можно взять одно из чисел равным –1, а три других – равными 1).
а) Докажите, что n – квадрат целого числа.
б)* Существует ли такой набор чисел для n = 16?
Решение
а)
В правой части этого равенства первое слагаемое равно n, а все остальные равны 0. Значит, n = (x1 + ... + xn)².
б) Предположим, что числа x1, ..., x16 удовлетворяют условию задачи. Можно считать, что x1 + ... + x16 ≥ 0 (иначе заменим все числа на противоположные). Как было показано, (x1 + ... + x16)² = 16, то есть x1 + ... + x16 = 4. Значит, 10 чисел равны 1, а 6 равны –1.
Запишем числа xi в вершинах правильного 16-угольника. Отметим звёздочками те вершины, где стоят минус единицы (всего 6 звёздочек). Обозначим 1/16 часть полного оборота (22,5°) через α. Пусть мы повернули всю картинку на угол kα (k = 1, 2, ..., 15). Докажем, что при этом ровно две звёздочки перейдут в вершины, где раньше были звёздочки.
Действительно, пусть r минус единиц перешли на места, где стояли единицы. Тогда в сумме x1xk+1 + x2xk+2 + ... + x16–k+1x1 будет r слагаемых вида (–)·1 и столько же слагаемых вида 1·(–1), то есть ровно 2r слагаемых, равных –1. Так как сумма равна 0, то 2r = 8, то есть r = 4. Следовательно, ровно две минус единицы попадают на места, где стояли минус единицы.
Теперь можно переформулировать нашу задачу следующим образом: можно ли в вершинах правильного 16-угольника расставить шесть звездочек так, чтобы две из них стояли в противоположных вершинах, и для любого числа k от 1 до 7 существовало бы ровно две пары звездочек таких, что расстояние между звездочками в одной паре равно k (расстоянием (XY) между двумя точками X и Y будем считать длину меньшей из дуг, их соединяющих; длина всей окружности принята за 16).
Обозначим через A и B диаметрально противоположные точки, отмеченные звездочкой, и через C, D, E, F – другие отмеченные точки. Подсчитаем сумму всех расстояний между точками A, B, C, D, E, F. Расстояние 8 встречается один раз, а расстояния от 1 до 7 по два раза – итого общая сумма 2(1 + 2 + 3 + 4 + 5 + 6 + 7) + 8 = 64.
Посмотрим, какие расстояния реализуются между точками C, D, E, F. Так как (AX) + (BX) = 8 для любой точки X, то сумма S всех расстояний между точками C, D, E, F равна 64 – (AB) – 4·8 = 24. Кроме того, если какое-то расстояние k реализуется между точками C, D, E, F, то это значит, что среди чисел (AC), (AD), (AE), (AF) и (BC), (BD), (BE), (BF) k встречается меньше двух раз; но тогда и 8 – k встречается меньше двух раз, то есть 8 – k тоже реализуется как расстояние между точками C, D, E, F. Посмотрим, как могут располагаться точки C, D, E, F. Легко проверить, что (с точностью до переобозначений) возможны только два случая.
1) Точки C, D, E образуют треугольник, содержащий центр окружности, а F лежит между C и D. Тогда (CD) + (DE) + (CE) = 16,
(CF) + (DF) = (CD), и, кроме того, (EF) больше (CE) или (DE). Так как и (CD) + (DE) > 8 и (CD) + (CE) > 8, то
24 = S = (CD) + (DE) + (CE) + (CF) + (DF) + (EF) = 16 + (CD) + (EF) > 24. Противоречие.
2) Точки C, D, E, F (расположенные в таком порядке) лежат с одной стороны от некоторого диаметра. Тогда (CD) + (DF) = (CF) и
(CE) + (EF) = (CF), поэтому 24 = S = 3(CF) + (DE). Так как (CF) > (DE), то (CF) = 7, (DE) = 3. Если (CD) = 1, то (DF) = 6; но при этом расстояние 2 = 8 – 6 не реализуется между точками C, D, E, F, что противоречит ранее доказанному. Если (CD) = 2, то хотя
(CF) = 7, расстояние 1 не реализуется. Если (CD) = 3, то (EF) = 1, а этот случай фактически разобран.
Итак, расставить звёздочки требуемым способом (а значит,
и подобрать числа xi) нельзя.
Замечания
Неизвестно, при каких n такой набор чисел существует, а при каких нет (хотя нетрудно показать, что n кратно 4, – см. задачу 73628). Есть предположение, что он существует только при n = 4.
