Проверка количества по двум крайним произведениям: условия и конструкция

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

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

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

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

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

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

  4. Ответ: да

    Сначала: Проверка количества по двум крайним произведениям

  5. Ответ: нет

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

  6. Минимальная сумма четырёх чисел

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

  7. Ответ

    Сначала: Минимальная сумма четырёх чисел

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

На доске написано несколько различных натуральных чисел, произведение любых двух из которых больше 45 и меньше 120.

а) Может ли на доске быть 5 чисел?

б) Может ли на доске быть 6 чисел?

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

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

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

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

Шаг 1. Упорядочим числа a1<…<aka_{1}<\ldots<ak. Условия для всех пар равносильны a1a2>La_{1}a_{2}>L и ak−1ak<Ua_{k-1}a_{k}<U. При фиксированном a1=xa_{1}=x наименьшее допустимое второе число y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right); остальные выбираем y+1, …, y+k−2y+1,\,\ldots,\,y+k-2. Это минимизирует наибольшее произведение, поэтому если даже оно не меньше UU, других наборов с таким xx нет. Достаточно 1≤x≤⌊U−1⌋1\leq x\leq\left\lfloor \sqrt{U-1}\right\rfloor, поскольку x2<a1a2<Ux^{2}<a_{1}a_{2}<U. В таблице указаны xx, yy и минимальное наибольшее произведение; подходящая строка даёт пример.
таблица=((1;46;2352);(2;23;650);(3;16;342);(4;12;210);(5;10;156);(6;8;110);(7;8;110);(8;9;132);(9;10;156);(10;11;182))\text{таблица}=\left(\left(1;46;2352\right);\left(2;23;650\right);\left(3;16;342\right);\left(4;12;210\right);\left(5;10;156\right);\left(6;8;110\right);\left(7;8;110\right);\left(8;9;132\right);\left(9;10;156\right);\left(10;11;182\right)\right)
Шаг 2. Упорядочим числа a1<…<aka_{1}<\ldots<ak. Условия для всех пар равносильны a1a2>La_{1}a_{2}>L и ak−1ak<Ua_{k-1}a_{k}<U. При фиксированном a1=xa_{1}=x наименьшее допустимое второе число y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right); остальные выбираем y+1, …, y+k−2y+1,\,\ldots,\,y+k-2. Это минимизирует наибольшее произведение, поэтому если даже оно не меньше UU, других наборов с таким xx нет. Достаточно 1≤x≤⌊U−1⌋1\leq x\leq\left\lfloor \sqrt{U-1}\right\rfloor, поскольку x2<a1a2<Ux^{2}<a_{1}a_{2}<U. В таблице указаны xx, yy и минимальное наибольшее произведение; подходящая строка даёт пример.
пример=(6;8;9;10;11)\text{пример}=\left(6;8;9;10;11\right)
Шаг 3. Да. Приведённый вариант удовлетворяет доказанным условиям.
Шаг 1. Упорядочим числа a1<…<aka_{1}<\ldots<ak. Условия для всех пар равносильны a1a2>La_{1}a_{2}>L и ak−1ak<Ua_{k-1}a_{k}<U. При фиксированном a1=xa_{1}=x наименьшее допустимое второе число y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right); остальные выбираем y+1, …, y+k−2y+1,\,\ldots,\,y+k-2. Это минимизирует наибольшее произведение, поэтому если даже оно не меньше UU, других наборов с таким xx нет. Достаточно 1≤x≤⌊U−1⌋1\leq x\leq\left\lfloor \sqrt{U-1}\right\rfloor, поскольку x2<a1a2<Ux^{2}<a_{1}a_{2}<U. В таблице указаны xx, yy и минимальное наибольшее произведение; подходящая строка даёт пример.
таблица=((1;46;2450);(2;23;702);(3;16;380);(4;12;240);(5;10;182);(6;8;132);(7;8;132);(8;9;156);(9;10;182);(10;11;210))\text{таблица}=\left(\left(1;46;2450\right);\left(2;23;702\right);\left(3;16;380\right);\left(4;12;240\right);\left(5;10;182\right);\left(6;8;132\right);\left(7;8;132\right);\left(8;9;156\right);\left(9;10;182\right);\left(10;11;210\right)\right)
Шаг 2. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. При фиксированном первом числе xx наименьшее второе равно y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right), а следующие не меньше y+1y+1 и y+2y+2. Поэтому минимальная сумма равна x+3y+3x+3y+3. Такой набор допустим тогда и только тогда, когда (y+1)(y+2)<U(y+1)(y+2)<U. Достаточно проверить xx от 1 до ⌊U−1⌋\left\lfloor \sqrt{U-1}\right\rfloor, как уже доказано. В таблице все допустимые кандидаты; выбираем наименьший.
таблица=((6;8;33);(7;8;34);(8;9;38))\text{таблица}=\left(\left(6;8;33\right);\left(7;8;34\right);\left(8;9;38\right)\right)
пример=(6;8;9;10)\text{пример}=\left(6;8;9;10\right)
Шаг 2. Записываем полученное значение.
3333

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

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