|
|
 |
Условие
Пусть X – некоторое множество целых чисел, которое можно разбить на N непересекающихся возрастающих арифметических прогрессий (бесконечных в обе стороны), а меньше чем на N – нельзя. Для любого ли такого X такое разбиение на N прогрессий единственно, если а) N = 2; б) N = 3?
(Возрастающая арифметическая прогрессия – это последовательность, в которой каждое число больше своего соседа слева на одну и ту же положительную величину.)
Решение
а) Предположим противное – есть четыре арифметические прогрессии A, B, C и D, причём A и B не пересекаются и дают в объединении X, и C и D – тоже. Можно считать, что у прогрессии A разность a не больше, чем у каждой из остальных.Ясно, что A не совпадает ни с C, ни с D – иначе разбиения совпадают. Тогда A и не содержится целиком ни в C, ни в D (так как у A наименьшая разность). Значит, A пересекается и с C, и с D.
Пусть число x лежит в пересечении A и C, тогда ни одно из чисел x-a и x+a не лежит в C (иначе A совпадает с C). Значит, они оба лежат в D, а разность прогрессии D – делитель числа 2a=(x+a)-(x-a), причём не меньший a, то есть это 2a или a. Последнее невозможно, поскольку A не совпадает с D. Аналогично получаем, что разность прогрессии C равна 2a. Тогда прогрессии C и D в объединении дают A, а прогрессия B отсутствует – противоречие.
б) Пусть X – все целые числа, дающие остатки 0, 3, 4, 6, 8 или 9 при делении на 12. Первое разбиение: все числа, кратные 3; все числа с остатком 4 от деления на 12; все числа с остатком 8 от деления на 12. Второе разбиение: все числа, кратные 4; все числа с остатком 3 от деления на 6; все числа с остатком 6 от деления на 12.
Докажем, что на две прогрессии разбить X нельзя. Предположим противное. Заметим, что тогда минимум четыре числа из 0, 3, 4, 6, 8, 9, 12 принадлежат одной прогрессии. Тогда минимум два из них лежат «с одной стороны» от 6, и поэтому разность этой прогрессии – либо 1, либо 2, либо 3, либо 4. Первые два случая невозможны (возникнут лишние числа), а в остальных двух случаях оставшееся множество – не прогрессия.
