Различные кратные двух цветов

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

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

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

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

  1. Наименьшая сумма при заданных количествах
  2. Возможные увеличения суммы

    Сначала: Наименьшая сумма при заданных количествах

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

    Сначала: Возможные увеличения суммы

  4. Ответ: да

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

  5. Наименьшая сумма при заданных количествах

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

  6. Возможные увеличения суммы

    Сначала: Наименьшая сумма при заданных количествах

  7. Все возможные количества

    Сначала: Возможные увеличения суммы

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

    Сначала: Все возможные количества

  9. Ответ: нет

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

  10. Наименьшая сумма при заданных количествах

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

  11. Возможные увеличения суммы

    Сначала: Наименьшая сумма при заданных количествах

  12. Все возможные количества

    Сначала: Возможные увеличения суммы

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

    Сначала: Все возможные количества

  14. Ответ

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

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

На доске написано 3030 натуральных чисел (числа могут повторяться), каждое из которых либо зелёного, либо красного цвета. Каждое зелёное число кратно 33, а каждое красное число кратно 77. При этом все зелёные числа различны и все красные различны (какое-то зелёное число может равняться какому-то красному числу).

а) Может ли сумма написанных чисел быть меньше 1395=3+6+…+901395=3+6+\ldots+90, если все числа на доске кратны 33?

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

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

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

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

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

Шаг 1. При kk числах второго класса и N−kN-k числах первого минимальную сумму дают наименьшие различные числа каждого класса. Суммируем соответствующие арифметические прогрессии. Все остальные наборы получаются неотрицательными увеличениями членов на шаг своего класса.
N=30N=30
S=1067S=1067
A=3A=3
B=7B=7
Шаг 2. Пусть DD - разность между заданной и минимальной суммами. Она должна представляться как uu, умноженное на шаг первого класса, плюс vv, умноженное на шаг второго класса, где uu, vv - неотрицательные целые. Если класс непуст, такое увеличение можно целиком прибавить к его наибольшему числу; различность сохранится. Для пустого класса соответствующее увеличение равно нулю. Поэтому условие необходимо и достаточно.
Шаг 3. Выписываем значения, полученные из условия и доказанного конечного разбора.
T=((3;6;9;12;15;18;21;24;27;30;33;36;39;42;45;48;51;54;57;60;63;66;69;72;75;78;81;84;87);(21))\mathcal T=\left(\left(3;6;9;12;15;18;21;24;27;30;33;36;39;42;45;48;51;54;57;60;63;66;69;72;75;78;81;84;87\right);\left(21\right)\right)
Шаг 4. Да. Приведённая конструкция удовлетворяет всем требованиям.
Шаг 1. При kk числах второго класса и N−kN-k числах первого минимальную сумму дают наименьшие различные числа каждого класса. Суммируем соответствующие арифметические прогрессии. Все остальные наборы получаются неотрицательными увеличениями членов на шаг своего класса.
N=30N=30
S=1067S=1067
A=3A=3
B=7B=7
Шаг 2. Пусть DD - разность между заданной и минимальной суммами. Она должна представляться как uu, умноженное на шаг первого класса, плюс vv, умноженное на шаг второго класса, где uu, vv - неотрицательные целые. Если класс непуст, такое увеличение можно целиком прибавить к его наибольшему числу; различность сохранится. Для пустого класса соответствующее увеличение равно нулю. Поэтому условие необходимо и достаточно.
Шаг 3. Количество kk находится между 0 и NN. Для каждого kk проверяем минимальную сумму и представимость её разности с заданной суммой. В таблице перечислены все допустимые kk. Приведённые два списка показывают конструкцию для требуемого количества или для минимального допустимого.
T=(6;7;8;9;10;11)\mathcal T=\left(6;7;8;9;10;11\right)
Шаг 4. Выписываем значения, полученные из условия и доказанного конечного разбора.
T={}\mathcal T=\left\{\right\}
Шаг 5. Нет. Необходимое и достаточное условие либо полная конечная область исключает такой случай.
Шаг 1. При kk числах второго класса и N−kN-k числах первого минимальную сумму дают наименьшие различные числа каждого класса. Суммируем соответствующие арифметические прогрессии. Все остальные наборы получаются неотрицательными увеличениями членов на шаг своего класса.
N=30N=30
S=1067S=1067
A=3A=3
B=7B=7
Шаг 2. Пусть DD - разность между заданной и минимальной суммами. Она должна представляться как uu, умноженное на шаг первого класса, плюс vv, умноженное на шаг второго класса, где uu, vv - неотрицательные целые. Если класс непуст, такое увеличение можно целиком прибавить к его наибольшему числу; различность сохранится. Для пустого класса соответствующее увеличение равно нулю. Поэтому условие необходимо и достаточно.
Шаг 3. Количество kk находится между 0 и NN. Для каждого kk проверяем минимальную сумму и представимость её разности с заданной суммой. В таблице перечислены все допустимые kk. Приведённые два списка показывают конструкцию для требуемого количества или для минимального допустимого.
T=(6;7;8;9;10;11)\mathcal T=\left(6;7;8;9;10;11\right)
Шаг 4. Выписываем значения, полученные из условия и доказанного конечного разбора.
T=((3;6;9;12;15;18;21;24;27;30;33;36;39;42;45;48;51;54;57;60;63;66;69;78);(7;14;21;28;35;56))\mathcal T=\left(\left(3;6;9;12;15;18;21;24;27;30;33;36;39;42;45;48;51;54;57;60;63;66;69;78\right);\left(7;14;21;28;35;56\right)\right)
Шаг 5. Записываем найденное значение.
66

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

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