Остатки чисел по кругу

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Периодичность остатков
  2. Два ненулевых остатка

    Сначала: Периодичность остатков

  3. Достаточность и количество

    Сначала: Два ненулевых остатка

  4. Ответ: нет

    Сначала: Достаточность и количество

  5. Периодичность остатков

    Сначала: Ответ: нет

  6. Два ненулевых остатка

    Сначала: Периодичность остатков

  7. Достаточность и количество

    Сначала: Два ненулевых остатка

  8. Ответ: нет

    Сначала: Достаточность и количество

  9. Периодичность остатков

    Сначала: Ответ: нет

  10. Два ненулевых остатка

    Сначала: Периодичность остатков

  11. Достаточность и количество

    Сначала: Два ненулевых остатка

  12. Конструкция

    Сначала: Достаточность и количество

  13. Ответ

    Сначала: Конструкция

Разобранный пример

По кругу расставлено NN различных натуральных чисел, каждое из которых не превосходит 340. Сумма любых трёх идущих подряд чисел не делится на 3, а сумма любых четырёх идущих подряд чисел делится на 3.

а) Может ли NN быть равным 240?

б) Может ли NN быть равным 129?

в) Найдите наибольшее значение NN.

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Вычитая суммы двух соседних блоков из четырёх чисел, получаем: числа через четыре позиции имеют одинаковые остатки по заданному модулю. При нечётном NN обход круга с шагом четыре проходит все позиции, поэтому все остатки одинаковы; при чётном NN возможны чередующиеся остатки.
M=340M=340
m=3m=3
Шаг 2. Сумма блока из четырёх делится на 3, а сумма трёх не делится, поэтому оставшееся число в этом блоке не делится на 3. Все остатки равны 1 или 2. При нечётном NN все они одинаковы, но сумма четырёх тогда не делится на 3 - невозможно. В периоде два либо четыре сумма четырёх делится на 3 только при равном количестве остатков 1 и 2. Значит, NN чётно и оба класса использованы поровну.
Шаг 3. Считаем доступные числа в каждом разрешённом классе остатков. При использовании одного класса берём нужное число его элементов. Для равных количеств двух классов ставим их поочерёдно; при замыкании чётного круга все условия сумм сохраняются. Так получаем и необходимую границу, и явную конструкцию.
T=((1;114);(2;113))\mathcal T=\left(\left(1;114\right);\left(2;113\right)\right)
Шаг 4. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Вычитая суммы двух соседних блоков из четырёх чисел, получаем: числа через четыре позиции имеют одинаковые остатки по заданному модулю. При нечётном NN обход круга с шагом четыре проходит все позиции, поэтому все остатки одинаковы; при чётном NN возможны чередующиеся остатки.
M=340M=340
m=3m=3
Шаг 2. Сумма блока из четырёх делится на 3, а сумма трёх не делится, поэтому оставшееся число в этом блоке не делится на 3. Все остатки равны 1 или 2. При нечётном NN все они одинаковы, но сумма четырёх тогда не делится на 3 - невозможно. В периоде два либо четыре сумма четырёх делится на 3 только при равном количестве остатков 1 и 2. Значит, NN чётно и оба класса использованы поровну.
Шаг 3. Считаем доступные числа в каждом разрешённом классе остатков. При использовании одного класса берём нужное число его элементов. Для равных количеств двух классов ставим их поочерёдно; при замыкании чётного круга все условия сумм сохраняются. Так получаем и необходимую границу, и явную конструкцию.
T=((1;114);(2;113))\mathcal T=\left(\left(1;114\right);\left(2;113\right)\right)
Шаг 4. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Вычитая суммы двух соседних блоков из четырёх чисел, получаем: числа через четыре позиции имеют одинаковые остатки по заданному модулю. При нечётном NN обход круга с шагом четыре проходит все позиции, поэтому все остатки одинаковы; при чётном NN возможны чередующиеся остатки.
M=340M=340
m=3m=3
Шаг 2. Сумма блока из четырёх делится на 3, а сумма трёх не делится, поэтому оставшееся число в этом блоке не делится на 3. Все остатки равны 1 или 2. При нечётном NN все они одинаковы, но сумма четырёх тогда не делится на 3 - невозможно. В периоде два либо четыре сумма четырёх делится на 3 только при равном количестве остатков 1 и 2. Значит, NN чётно и оба класса использованы поровну.
Шаг 3. Считаем доступные числа в каждом разрешённом классе остатков. При использовании одного класса берём нужное число его элементов. Для равных количеств двух классов ставим их поочерёдно; при замыкании чётного круга все условия сумм сохраняются. Так получаем и необходимую границу, и явную конструкцию.
T=((1;114);(2;113))\mathcal T=\left(\left(1;114\right);\left(2;113\right)\right)
Шаг 4. Указываем исходные числа, количества или распределение по дням. Пара значение–количество означает повторение числа. Прямой подсчёт проверяет суммы и границы; при распределении заданной суммы среди cc чисел начинаем с cc единиц и добавляем не больше M−1M-1 к каждой.
X1=(1;2;4;5;7;8;10;11;13;14;16;17;19;20;22;23;25;26;28;29;31;32;34;35;37;38;40;41;43;44;46;47;49;50;52;53;55;56;58;59;61;62;64;65;67;68;70;71;73;74;76;77;79;80;82;83;85;86;88;89;91;92;94;95;97;98;100;101;103;104;106;107;109;110;112;113;115;116;118;119;121;122;124;125;127;128;130;131;133;134;136;137;139;140;142;143;145;146;148;149;151;152;154;155;157;158;160;161;163;164;166;167;169;170;172;173;175;176;178;179;181;182;184;185;187;188;190;191;193;194;196;197;199;200;202;203;205;206;208;209;211;212;214;215;217;218;220;221;223;224;226;227;229;230;232;233;235;236;238;239;241;242;244;245;247;248;250;251;253;254;256;257;259;260;262;263;265;266;268;269;271;272;274;275;277;278;280;281;283;284;286;287;289;290;292;293;295;296;298;299;301;302;304;305;307;308;310;311;313;314;316;317;319;320;322;323;325;326;328;329;331;332;334;335;337;338)X_1=\left(1;2;4;5;7;8;10;11;13;14;16;17;19;20;22;23;25;26;28;29;31;32;34;35;37;38;40;41;43;44;46;47;49;50;52;53;55;56;58;59;61;62;64;65;67;68;70;71;73;74;76;77;79;80;82;83;85;86;88;89;91;92;94;95;97;98;100;101;103;104;106;107;109;110;112;113;115;116;118;119;121;122;124;125;127;128;130;131;133;134;136;137;139;140;142;143;145;146;148;149;151;152;154;155;157;158;160;161;163;164;166;167;169;170;172;173;175;176;178;179;181;182;184;185;187;188;190;191;193;194;196;197;199;200;202;203;205;206;208;209;211;212;214;215;217;218;220;221;223;224;226;227;229;230;232;233;235;236;238;239;241;242;244;245;247;248;250;251;253;254;256;257;259;260;262;263;265;266;268;269;271;272;274;275;277;278;280;281;283;284;286;287;289;290;292;293;295;296;298;299;301;302;304;305;307;308;310;311;313;314;316;317;319;320;322;323;325;326;328;329;331;332;334;335;337;338\right)
Шаг 5. Записываем вычисленную достижимую границу.
226226

Открыть задачу целиком

Попробовать самостоятельно