Два изменения цифр двузначных чисел

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

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

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

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

  1. Изменение каждого числа
  2. Баланс двух операций

    Сначала: Изменение каждого числа

  3. Ответ: нет

    Сначала: Баланс двух операций

  4. Изменение каждого числа

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

  5. Равенство сумм

    Сначала: Изменение каждого числа

  6. Ответ: нет

    Сначала: Равенство сумм

  7. Изменение каждого числа

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

  8. Равенство сумм

    Сначала: Изменение каждого числа

  9. Граница исходной суммы

    Сначала: Равенство сумм

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

    Сначала: Граница исходной суммы

  11. Ответ

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

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

На доске написано некоторое количество двузначных натуральных чисел, среди которых могут быть одинаковые. С каждым из этих чисел проделывают одну из двух операций: либо увеличивают цифру в разряде десятков на 2 и уменьшают цифру в разряде единиц на 5, либо уменьшают цифру в разряде десятков на 2 и увеличивают цифру в разряде единиц на 2. Все числа, получившиеся в результате, оказались двузначными натуральными.

а) Может ли сумма исходных чисел оказаться на 128 меньше суммы получившихся чисел?

б) Может ли количество чисел на доске равняться 25, если сумма исходных чисел равна сумме получившихся чисел?

в) Какое наибольшее количество чисел может быть написано на доске, если сумма исходных чисел равна сумме получившихся чисел и меньше 1198?

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

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

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

Шаг 1. Изменение цифры десятков на pp меняет число на 10p10p, а изменение цифры единиц - на соответствующее число единиц. Поэтому два вида операций дают постоянные приращения d1d_{1} и d2d_{2}. Для каждого вида записываем полный конечный список допустимых исходных двузначных чисел, у которых обе новые цифры остаются в границах разрядов.
a=15a=15
b=−18b=-18
X1=(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79)X_1=\left(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79\right)
X2=(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97)X_2=\left(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97\right)
Шаг 2. Если операций двух видов uu и vv, суммарное изменение равно d1u+d2vd_{1}u+d_{2}v. Для заданного изменения DD необходимо, чтобы НОД(d1, −d2)\text{НОД}(d_{1},\,-d_{2}) делил DD. Это достаточно: из целого решения добавлением положительного решения однородного уравнения можно сделать оба количества неотрицательными.
D=128D=128
d=3d=3
Шаг 3. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Изменение цифры десятков на pp меняет число на 10p10p, а изменение цифры единиц - на соответствующее число единиц. Поэтому два вида операций дают постоянные приращения d1d_{1} и d2d_{2}. Для каждого вида записываем полный конечный список допустимых исходных двузначных чисел, у которых обе новые цифры остаются в границах разрядов.
a=15a=15
b=−18b=-18
X1=(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79)X_1=\left(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79\right)
X2=(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97)X_2=\left(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97\right)
Шаг 2. При нулевом суммарном изменении все количества имеют вид u=u0tu=u_{0}t, v=v0tv=v_{0}t, где u0=−d2gu_{0}=-\frac{d_{2}}{g}, v0=d1gv_{0}=\frac{d_{1}}{g} и gg - их НОД\text{НОД}. Поэтому количество чисел кратно u0+v0u_{0}+v_{0}. Любое такое положительное количество реализуется повторением допустимых исходных чисел.
u=6tu=6 t
v=5tv=5 t
N=11tN=11 t
Шаг 3. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Изменение цифры десятков на pp меняет число на 10p10p, а изменение цифры единиц - на соответствующее число единиц. Поэтому два вида операций дают постоянные приращения d1d_{1} и d2d_{2}. Для каждого вида записываем полный конечный список допустимых исходных двузначных чисел, у которых обе новые цифры остаются в границах разрядов.
a=15a=15
b=−18b=-18
X1=(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79)X_1=\left(15;16;17;18;19;25;26;27;28;29;35;36;37;38;39;45;46;47;48;49;55;56;57;58;59;65;66;67;68;69;75;76;77;78;79\right)
X2=(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97)X_2=\left(30;31;32;33;34;35;36;37;40;41;42;43;44;45;46;47;50;51;52;53;54;55;56;57;60;61;62;63;64;65;66;67;70;71;72;73;74;75;76;77;80;81;82;83;84;85;86;87;90;91;92;93;94;95;96;97\right)
Шаг 2. При нулевом суммарном изменении все количества имеют вид u=u0tu=u_{0}t, v=v0tv=v_{0}t, где u0=−d2gu_{0}=-\frac{d_{2}}{g}, v0=d1gv_{0}=\frac{d_{1}}{g} и gg - их НОД\text{НОД}. Поэтому количество чисел кратно u0+v0u_{0}+v_{0}. Любое такое положительное количество реализуется повторением допустимых исходных чисел.
u=6tu=6 t
v=5tv=5 t
Шаг 3. В каждом блоке из u0u_{0} операций первого вида и v0v_{0} второго исходная сумма лежит между суммой минимальных и суммой максимальных допустимых чисел. При максимизации количества под верхней границей берём минимальные исходные числа; при минимизации количества над нижней границей - максимальные. Целая граница для tt и указанное повторение чисел доказывают оптимальность.
L=240L=240
H=959H=959
T=1198T=1198
t=4t=4
Шаг 4. Указываем исходные числа, количества или распределение по дням. Пара значение–количество означает повторение числа. Прямой подсчёт проверяет суммы и границы; при распределении заданной суммы среди cc чисел начинаем с cc единиц и добавляем не больше M−1M-1 к каждой.
X1=((15;24);(30;20))X_1=\left(\left(15;24\right);\left(30;20\right)\right)
Sдо=960S_{\text{до}}=960
Sпосле=960S_{\text{после}}=960
Шаг 5. Записываем вычисленную достижимую границу.
4444

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

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