Карточки с отметками делимости

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

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

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

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

  1. Четыре непересекающихся класса
  2. Вместимость классов до границы

    Сначала: Четыре непересекающихся класса

  3. Ответ

    Сначала: Вместимость классов до границы

  4. Четыре непересекающихся класса

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

  5. Вместимость классов до границы

    Сначала: Четыре непересекающихся класса

  6. Наименьшая верхняя граница

    Сначала: Вместимость классов до границы

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

    Сначала: Наименьшая верхняя граница

  8. Ответ

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

  9. Четыре непересекающихся класса

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

  10. Вместимость классов до границы

    Сначала: Четыре непересекающихся класса

  11. Наименьшая верхняя граница

    Сначала: Вместимость классов до границы

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

    Сначала: Наименьшая верхняя граница

  13. Ответ

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

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

Есть 60 карточек, на каждой из которых написано натуральное число больше 1. Все числа различные. На обратной стороне каждой карточки ставят цветовую отметку: если число делится на 3 — красную, если на 4 — синюю, если на 5 — зелёную. Получилось так, что на каждой карточке поставлено не менее двух цветовых отметок.

а) Какое наибольшее количество карточек может быть с числами меньше 200?

б) Получилось, что на kk карточках есть только синяя и зелёная отметки, на kk карточках — только синяя и красная, на kk карточках — только красная и зелёная. Найдите наименьшее возможное значение наибольшего числа среди чисел, указанных на карточках.

в) Карточек с двумя отметками, одна из которых синяя, получилось 37. Найдите наименьшее возможное значение наибольшего числа среди указанных на карточках.

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

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

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

Шаг 1. Числа с двумя или тремя отметками разбиваем на классы: делящиеся только на первую и вторую величины, только на первую и третью, только на вторую и третью и на все три. Класс полностью определяется остатком по общему кратному трёх делителей. В варианте ровно с двумя отметками четвёртый класс исключён.
T=((0;3);(1;4);(2;5))\mathcal T=\left(\left(0;3\right);\left(1;4\right);\left(2;5\right)\right)
Шаг 2. Для границы MM считаем количество доступных различных чисел каждого класса не больше MM. Выбрать нужное число карточек можно тогда и только тогда, когда вместимостей хватает для заданных количеств классов. Для равных количеств проверяем все 0≤k≤⌊N3⌋0\leq k\leq\left\lfloor \frac{N}{3}\right\rfloor, а остаток заполняем тройными отметками. Для заданного числа карточек с синей отметкой отдельно проверяем синюю и оставшуюся группы.
T=(13;10;6;3)\mathcal T=\left(13;10;6;3\right)
Шаг 3. Записываем найденное значение.
3232
Шаг 1. Числа с двумя или тремя отметками разбиваем на классы: делящиеся только на первую и вторую величины, только на первую и третью, только на вторую и третью и на все три. Класс полностью определяется остатком по общему кратному трёх делителей. В варианте ровно с двумя отметками четвёртый класс исключён.
Шаг 2. Для границы MM считаем количество доступных различных чисел каждого класса не больше MM. Выбрать нужное число карточек можно тогда и только тогда, когда вместимостей хватает для заданных количеств классов. Для равных количеств проверяем все 0≤k≤⌊N3⌋0\leq k\leq\left\lfloor \frac{N}{3}\right\rfloor, а остаток заполняем тройными отметками. Для заданного числа карточек с синей отметкой отдельно проверяем синюю и оставшуюся группы.
M=520M=520
T=(35;26;18;8)\mathcal T=\left(35;26;18;8\right)
Шаг 3. Увеличиваем MM от 2 до явной достаточной границы L(N+1)L(N+1), где L−НОКL-\text{НОК} трёх делителей: в рассматриваемых классах за каждый период LL встречается хотя бы одно число. Первая допустимая граница - минимум. В таблице её вместимости и выбранные количества; выписываем соответствующие наименьшие числа каждого класса.
T=(18;18;18;6)\mathcal T=\left(18;18;18;6\right)
Шаг 4. Выписываем значения, полученные из условия и доказанного конечного разбора.
T=((12;24;36;48;72;84;96;108;132;144;156;168;192;204;216;228;252;264);(15;30;45;75;90;105;135;150;165;195;210;225;255;270;285;315;330;345);(20;40;80;100;140;160;200;220;260;280;320;340;380;400;440;460;500;520);(60;120;180;240;300;360))\mathcal T=\left(\left(12;24;36;48;72;84;96;108;132;144;156;168;192;204;216;228;252;264\right);\left(15;30;45;75;90;105;135;150;165;195;210;225;255;270;285;315;330;345\right);\left(20;40;80;100;140;160;200;220;260;280;320;340;380;400;440;460;500;520\right);\left(60;120;180;240;300;360\right)\right)
Шаг 5. Записываем найденное значение.
520520
Шаг 1. Числа с двумя или тремя отметками разбиваем на классы: делящиеся только на первую и вторую величины, только на первую и третью, только на вторую и третью и на все три. Класс полностью определяется остатком по общему кратному трёх делителей. В варианте ровно с двумя отметками четвёртый класс исключён.
Шаг 2. Для границы MM считаем количество доступных различных чисел каждого класса не больше MM. Выбрать нужное число карточек можно тогда и только тогда, когда вместимостей хватает для заданных количеств классов. Для равных количеств проверяем все 0≤k≤⌊N3⌋0\leq k\leq\left\lfloor \frac{N}{3}\right\rfloor, а остаток заполняем тройными отметками. Для заданного числа карточек с синей отметкой отдельно проверяем синюю и оставшуюся группы.
M=372M=372
T=(25;18;12;6)\mathcal T=\left(25;18;12;6\right)
Шаг 3. Увеличиваем MM от 2 до явной достаточной границы L(N+1)L(N+1), где L−НОКL-\text{НОК} трёх делителей: в рассматриваемых классах за каждый период LL встречается хотя бы одно число. Первая допустимая граница - минимум. В таблице её вместимости и выбранные количества; выписываем соответствующие наименьшие числа каждого класса.
T=(25;18;12;5)\mathcal T=\left(25;18;12;5\right)
Шаг 4. Выписываем значения, полученные из условия и доказанного конечного разбора.
T=((12;24;36;48;72;84;96;108;132;144;156;168;192;204;216;228;252;264;276;288;312;324;336;348;372);(15;30;45;75;90;105;135;150;165;195;210;225;255;270;285;315;330;345);(20;40;80;100;140;160;200;220;260;280;320;340);(60;120;180;240;300))\mathcal T=\left(\left(12;24;36;48;72;84;96;108;132;144;156;168;192;204;216;228;252;264;276;288;312;324;336;348;372\right);\left(15;30;45;75;90;105;135;150;165;195;210;225;255;270;285;315;330;345\right);\left(20;40;80;100;140;160;200;220;260;280;320;340\right);\left(60;120;180;240;300\right)\right)
Шаг 5. Записываем найденное значение.
372372

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

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