Количество карточек и максимумы: условия и конструкция

Выводим целочисленную модель, доказываем полноту области и получаем ответ с конструкцией достижимости.

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

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

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

  1. Целые числа и необходимые условия
  2. Граница и достижимость
  3. Количество карточек и максимумы

    Сначала: Целые числа и необходимые условия, Граница и достижимость

  4. Число доступных кратных

    Сначала: Количество карточек и максимумы

  5. Конечные верхние границы

    Сначала: Число доступных кратных

  6. Условие пункта

    Сначала: Конечные верхние границы

  7. Подходящая пара и конструкция

    Сначала: Условие пункта

  8. Ответ: да

    Сначала: Подходящая пара и конструкция

  9. Отсутствие подходящих пар

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

  10. Ответ: нет

    Сначала: Отсутствие подходящих пар

  11. Достижимость максимума

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

  12. Ответ

    Сначала: Достижимость максимума

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

На столе лежит некоторое количество карточек, часть из которых синего цвета, а остальные красного (есть хотя бы по одной карточке каждого цвета). На каждой карточке написано целое число. На карточках синего цвета написаны различные числа, делящиеся на 3, а на карточках красного цвета написаны различные чётные числа (при этом некоторые числа могут быть написаны дважды: один раз на синей карточке и один раз на красной карточке). Все числа на карточках не меньше −36-36. Оказалось, что наибольшее число, написанное на красной карточке, равно удвоенному количеству синих карточек, а наибольшее число, написанное на синей карточке, равно количеству красных карточек.

а) Может ли на столе лежать ровно одна синяя карточка?

б) Может ли на столе лежать ровно 50 синих карточек?

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

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

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

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

Шаг 1. Обозначим количества синих и красных карточек через xx и yy. Синие числа кратны dd и их максимум равен yy; красные числа кратны ee и их максимум равен kxkx. Все числа строго больше LL. Поэтому yy должно делиться на dd, а kxkx - на ee. Числа одного цвета различны.
d=3d=3
e=2e=2
k=2k=2
L=−37L=-37
Шаг 2. Число кратных dd в интервале (L, y](L,\,y] равно ⌊yd⌋−⌊Ld⌋\left\lfloor \frac{y}{d}\right\rfloor -\left\lfloor \frac{L}{d}\right\rfloor, а число кратных ee в (L, kx](L,\,kx] равно ⌊kxe⌋−⌊Le⌋\left\lfloor \frac{kx}{e}\right\rfloor -\left\lfloor \frac{L}{e}\right\rfloor. Эти количества должны быть не меньше xx и yy соответственно. Условия достаточны: выбираем нужное количество различных кратных из каждого интервала, обязательно включая его правый конец.
A=13A=13
B=19B=19
Шаг 3. Положим A=−⌊Ld⌋A=-\left\lfloor \frac{L}{d}\right\rfloor, B=−⌊Le⌋B=-\left\lfloor \frac{L}{e}\right\rfloor. Из условий количества следует x≤yd+Ax\leq\frac{y}{d}+A и y≤kxe+By\leq\frac{kx}{e}+B. Подставляя первое неравенство во второе и используя de>kde>k, получаем y≤d(kA+eB)de−ky\leq\frac{d(kA+eB)}{de-k}. Затем x≤⌊ymax⁡d⌋+Ax\leq\left\lfloor \frac{y\max}{d}\right\rfloor +A. Итак, проверка целых пар в указанных границах охватывает все возможные случаи.
ymax⁡=48y_{\max}=48
xmax⁡=29x_{\max}=29
Шаг 4. К найденным необходимым и достаточным условиям добавляем равенство из вопроса: фиксированное число синих, красных, общее количество или разность количеств. Проверяем все целые пары в доказанной конечной области.
q=1q=1
K=6K=6
Шаг 5. Полученная пара xx, yy удовлетворяет всем условиям. Берём xx различных кратных dd из (L, y](L,\,y], включая yy, и yy различных кратных ee из (L, kx](L,\,kx], включая kxkx. Так получаем требуемые карточки. Ниже проверены количества доступных кратных.
x=1x=1
y=3y=3
C=14C=14
D=20D=20
Шаг 6. Да. Приведённая конструкция удовлетворяет условиям.
Шаг 1. Обозначим количества синих и красных карточек через xx и yy. Синие числа кратны dd и их максимум равен yy; красные числа кратны ee и их максимум равен kxkx. Все числа строго больше LL. Поэтому yy должно делиться на dd, а kxkx - на ee. Числа одного цвета различны.
d=3d=3
e=2e=2
k=2k=2
L=−37L=-37
Шаг 2. Число кратных dd в интервале (L, y](L,\,y] равно ⌊yd⌋−⌊Ld⌋\left\lfloor \frac{y}{d}\right\rfloor -\left\lfloor \frac{L}{d}\right\rfloor, а число кратных ee в (L, kx](L,\,kx] равно ⌊kxe⌋−⌊Le⌋\left\lfloor \frac{kx}{e}\right\rfloor -\left\lfloor \frac{L}{e}\right\rfloor. Эти количества должны быть не меньше xx и yy соответственно. Условия достаточны: выбираем нужное количество различных кратных из каждого интервала, обязательно включая его правый конец.
A=13A=13
B=19B=19
Шаг 3. Положим A=−⌊Ld⌋A=-\left\lfloor \frac{L}{d}\right\rfloor, B=−⌊Le⌋B=-\left\lfloor \frac{L}{e}\right\rfloor. Из условий количества следует x≤yd+Ax\leq\frac{y}{d}+A и y≤kxe+By\leq\frac{kx}{e}+B. Подставляя первое неравенство во второе и используя de>kde>k, получаем y≤d(kA+eB)de−ky\leq\frac{d(kA+eB)}{de-k}. Затем x≤⌊ymax⁡d⌋+Ax\leq\left\lfloor \frac{y\max}{d}\right\rfloor +A. Итак, проверка целых пар в указанных границах охватывает все возможные случаи.
ymax⁡=48y_{\max}=48
xmax⁡=29x_{\max}=29
Шаг 4. К найденным необходимым и достаточным условиям добавляем равенство из вопроса: фиксированное число синих, красных, общее количество или разность количеств. Проверяем все целые пары в доказанной конечной области.
q=50q=50
K=0K=0
Шаг 5. В доказанной конечной области нет целой пары, удовлетворяющей одновременно условию вопроса, делимости максимумов и двум ограничениям на число доступных кратных. Поэтому ответ отрицательный.
Шаг 6. Нет. Необходимые условия или полный конечный разбор исключают требуемый случай.
Шаг 1. Обозначим количества синих и красных карточек через xx и yy. Синие числа кратны dd и их максимум равен yy; красные числа кратны ee и их максимум равен kxkx. Все числа строго больше LL. Поэтому yy должно делиться на dd, а kxkx - на ee. Числа одного цвета различны.
d=3d=3
e=2e=2
k=2k=2
L=−37L=-37
Шаг 2. Число кратных dd в интервале (L, y](L,\,y] равно ⌊yd⌋−⌊Ld⌋\left\lfloor \frac{y}{d}\right\rfloor -\left\lfloor \frac{L}{d}\right\rfloor, а число кратных ee в (L, kx](L,\,kx] равно ⌊kxe⌋−⌊Le⌋\left\lfloor \frac{kx}{e}\right\rfloor -\left\lfloor \frac{L}{e}\right\rfloor. Эти количества должны быть не меньше xx и yy соответственно. Условия достаточны: выбираем нужное количество различных кратных из каждого интервала, обязательно включая его правый конец.
A=13A=13
B=19B=19
Шаг 3. Положим A=−⌊Ld⌋A=-\left\lfloor \frac{L}{d}\right\rfloor, B=−⌊Le⌋B=-\left\lfloor \frac{L}{e}\right\rfloor. Из условий количества следует x≤yd+Ax\leq\frac{y}{d}+A и y≤kxe+By\leq\frac{kx}{e}+B. Подставляя первое неравенство во второе и используя de>kde>k, получаем y≤d(kA+eB)de−ky\leq\frac{d(kA+eB)}{de-k}. Затем x≤⌊ymax⁡d⌋+Ax\leq\left\lfloor \frac{y\max}{d}\right\rfloor +A. Итак, проверка целых пар в указанных границах охватывает все возможные случаи.
ymax⁡=48y_{\max}=48
xmax⁡=29x_{\max}=29
Шаг 4. Сравниваем искомое количество по всем допустимым целым парам в доказанных границах. Ни одна пара не даёт большего значения. Для максимизирующей пары применяем конструкцию выбора кратных, поэтому верхняя граница достигается.
Kвсе=199K_{\text{все}}=199
Rиск=29R_{\text{иск}}=29
Шаг 5. Полученная пара xx, yy удовлетворяет всем условиям. Берём xx различных кратных dd из (L, y](L,\,y], включая yy, и yy различных кратных ee из (L, kx](L,\,kx], включая kxkx. Так получаем требуемые карточки. Ниже проверены количества доступных кратных.
x=29x=29
y=48y=48
C=29C=29
D=48D=48
Шаг 6. Записываем полученное значение.
2929

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

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