Различные значения произведений

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

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

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

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

  1. Границы исходных множителей
  2. Полное восстановление произведений

    Сначала: Границы исходных множителей

  3. Исходные числа

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

  4. Ответ

    Сначала: Исходные числа

  5. Границы исходных множителей

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

  6. Полное восстановление произведений

    Сначала: Границы исходных множителей

  7. Исходные числа

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

  8. Ответ: нет

    Сначала: Исходные числа

  9. Все наборы заданной длины

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

  10. Исходные числа

    Сначала: Все наборы заданной длины

  11. Ответ

    Сначала: Исходные числа

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

Задумано несколько натуральных чисел (не обязательно различных). Эти числа и все их возможные произведения (по 2 числа, по 3 числа и т. д.) выписывают на доску. Если какое-⁠то число nn, выписанное на доску, повторяется несколько раз, то на доске оставляют одно такое число nn, а остальные числа, равные nn, стирают. Например, если задуманы числа 1, 3, 3, 4, то на доске будет записан набор 1, 3, 4, 9, 12, 36.

а) Приведите пример задуманных чисел, для которых на доске будет записан набор 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90.

б) Существует ли пример таких задуманных чисел, для которых на доске будет записан набор 3, 5, 7, 9, 15, 21, 35, 45, 105, 315, 945?

в) Приведите все примеры шести задуманных чисел, для которых на доске будет записан набор, наибольшее число в котором равно 82.

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

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

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

Шаг 1. Наибольшее произведение MM равно произведению всех задуманных чисел. Если в записанном наборе нет 1, все исходные множители не меньше 2, каждый принадлежит набору и делит MM. Значит, их не больше ⌊log⁡2M⌋\left\lfloor \log_{2}M\right\rfloor. Упорядочиваем множители неубывающе и проверяем только этот конечный набор кандидатов.
M=90M=90
Шаг 2. Начинаем с пустого произведения 1. При добавлении vv каждое старое произведение pp даёт также pvpv. Все новые непустые произведения должны принадлежать данному набору. Остаток общего произведения MM должен делиться на vv. Продолжаем до общего произведения MM и проверяем точное равенство множества всех непустых произведений. Это все возможные исходные наборы.
Шаг 3. В таблице перечислены все найденные исходные наборы. Их суммы или произведения непосредственно дают требуемый записанный набор. Если таблица пуста, полное восстановление доказывает невозможность.
T=((2;3;3;5))\mathcal T=\left(\left(2;3;3;5\right)\right)
Шаг 4. Записываем найденные значения.
(2;3;3;5)\left(2;3;3;5\right)
Шаг 1. Наибольшее произведение MM равно произведению всех задуманных чисел. Если в записанном наборе нет 1, все исходные множители не меньше 2, каждый принадлежит набору и делит MM. Значит, их не больше ⌊log⁡2M⌋\left\lfloor \log_{2}M\right\rfloor. Упорядочиваем множители неубывающе и проверяем только этот конечный набор кандидатов.
M=945M=945
Шаг 2. Начинаем с пустого произведения 1. При добавлении vv каждое старое произведение pp даёт также pvpv. Все новые непустые произведения должны принадлежать данному набору. Остаток общего произведения MM должен делиться на vv. Продолжаем до общего произведения MM и проверяем точное равенство множества всех непустых произведений. Это все возможные исходные наборы.
Шаг 3. В таблице перечислены все найденные исходные наборы. Их суммы или произведения непосредственно дают требуемый записанный набор. Если таблица пуста, полное восстановление доказывает невозможность.
T={}\mathcal T=\left\{\right\}
Шаг 4. Нет. Полная конечная область или доказанное необходимое условие исключает возможность.
Шаг 1. Для заданной длины NN и наибольшего произведения MM ищем все неубывающие разложения MM на NN натуральных множителей. Выбираем очередной множитель из делителей оставшегося произведения, не меньше предыдущего; единицы разрешены. Последний множитель определяется однозначно. Эти условия дают полную конечную область.
M=82M=82
N=6N=6
Шаг 2. В таблице перечислены все найденные исходные наборы. Их суммы или произведения непосредственно дают требуемый записанный набор. Если таблица пуста, полное восстановление доказывает невозможность.
T=((1;1;1;1;1;82);(1;1;1;1;2;41))\mathcal T=\left(\left(1;1;1;1;1;82\right);\left(1;1;1;1;2;41\right)\right)
Шаг 3. Записываем найденные значения.
((1;1;1;1;1;82);(1;1;1;1;2;41))\left(\left(1;1;1;1;1;82\right);\left(1;1;1;1;2;41\right)\right)

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

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