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

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

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

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

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

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

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

  4. Ответ: да

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

  5. Ответ: нет

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

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

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

  7. Ответ

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

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

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

а) Может ли на доске быть 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;26;812);(2;13;240);(3;9;132);(4;7;90);(5;6;72);(6;7;90);(7;8;110);(8;9;132);(9;10;156))\text{таблица}=\left(\left(1;26;812\right);\left(2;13;240\right);\left(3;9;132\right);\left(4;7;90\right);\left(5;6;72\right);\left(6;7;90\right);\left(7;8;110\right);\left(8;9;132\right);\left(9;10;156\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 и минимальное наибольшее произведение; подходящая строка даёт пример.
пример=(5;6;7;8;9)\text{пример}=\left(5;6;7;8;9\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;26;870);(2;13;272);(3;9;156);(4;7;110);(5;6;90);(6;7;110);(7;8;132);(8;9;156);(9;10;182))\text{таблица}=\left(\left(1;26;870\right);\left(2;13;272\right);\left(3;9;156\right);\left(4;7;110\right);\left(5;6;90\right);\left(6;7;110\right);\left(7;8;132\right);\left(8;9;156\right);\left(9;10;182\right)\right)
Шаг 2. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. Обозначим третье число через zz. Тогда первые два не больше z−2z-2 и z−1z-1, четвёртое не больше ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor. Значит, сумма не превосходит 3z−3+⌊U−1z⌋3z-3+\left\lfloor \frac{U-1}{z}\right\rfloor. Если (z−2)(z−1)≤L(z-2)(z-1)\leq L, первые два вообще не смогут удовлетворить нижней границе; если z(z+1)≥Uz(z+1)\geq U, не найдётся четвёртого. Во всех остальных случаях набор z−2z-2, z−1z-1, zz, ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor допустим и достигает указанной суммы. Перебираем конечные zz от 3 до ⌊U−1⌋\left\lfloor \sqrt{U-1}\right\rfloor; таблица даёт все кандидаты максимума.
таблица=((7;12;30);(8;10;31))\text{таблица}=\left(\left(7;12;30\right);\left(8;10;31\right)\right)
пример=(6;7;8;10)\text{пример}=\left(6;7;8;10\right)
Шаг 2. Записываем полученное значение.
3131

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

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