Простая школьная задача

[sergey zhukov]

wrest в сообщении #1420884 писал(а):

Троек у нас 4=1+1+2 ("сидят" в 3,6,9) -- на три кучки не раскладывается, так что выкидываем 3,6,9

Я бы на этом этапе выкинул только тройку и четверку. И осталось бы три тройки и шесть двоек в составе 1, 2, 6, 8, 9. Это уже формально нужно проверять. В предыдущем примере я ошибся, правда.

[wrest]

sergey zhukov в сообщении #1420890 писал(а):

И осталось бы три тройки и шесть двоек в составе 1, 2, 6, 8, 9. Это уже формально нужно проверять.

Проверять не нужно, потому что тройки $1+1+2$ не раскладываются по трём кучкам.
То есть метод такой, что сначала вы отметаете точно неподходящее, а только потом проверяете оставшееся.

А вот вам задачка на подумать: как найти наименьший набор натуральных чисел (то есть тот в котором числа не повторяются, а максимальное число в наборе, равное $k$, считаем "величиной набора"), который можно разложить на $n$ кучек так, что произведение чисел в каждой кучке будет одно и то же, а чисел в каждой кучке будет больше одного?

Например, чему равно $k$ для $n=7$, а для $n=8$?

[Munin]

wrest в сообщении #1420916 писал(а):

а чисел в каждой кучке будет больше одного?

Можно и не накладывать это условие, задача всё равно нетривиальная.

[sergey zhukov]

Думаю, можно так рассуждать.

Возьмем набор минимальных простых чисел, количество разбиений которого на две разные группы (с точностью до перестановок групп) достигает 7. Если ограничится пятью числами, то это 2, 2, 2, 3, 5. Перемножение внутри разбиений дают 7 пар разных чисел с одинаковым произведением. Величина набора равна 2х2х3х5 $=$ 60.

Если ограничится четырьмя простыми числами, то это 2, 3, 5, 7. Но здесь величина набора равна 3х5х7$=$105.

Для разбиения на восемь групп нужно взять набор простых чисел на ступеньку выше: 2, 2, 3, 3, 5. У него девять разбиений, если откинуть самое большое число 2х3х3х5, то величина набора тоже равна 2х2х3х5 $=$ 60.

Принцип наименьшего количества наименьших простых чисел, которые дают заданное количество разбиений, вроде верный. Но вот минимальное количество сомножителей (два) в каждой кучке - это не кажется очевидным.

[wrest]

sergey zhukov в сообщении #1420989 писал(а):

Если ограничится пятью числами, то это 2, 2, 2, 3, 5. Перемножение внутри разбиений дают 7 пар разных чисел с одинаковым произведением. Величина набора равна 2х2х3х5 $=$ 60.

Одну двойку забыли: $2\cdot 2 \cdot 2 \cdot 3 \cdot 5=120$
Или вы что-то другое имели в виду?

-- 15.10.2019, 22:08 --

sergey zhukov в сообщении #1420989 писал(а):

Принцип наименьшего количества наименьших простых чисел, которые дают заданное количество разбиений, вроде верный.

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

[Pphantom]

sergey zhukov, пожалуйста, набирайте формулы правильно. Один раз я поправил их за вас, но делать это постоянно мне совершенно не хочется.

[sergey zhukov]

wrest в сообщении #1420995 писал(а):

Одну двойку забыли: $2\cdot 2 \cdot 2 \cdot 3 \cdot 5=120$
Или вы что-то другое имели в виду?

Нет, я каждую кучку представляю в виде произведения двух чисел. То произведение, в котором будет максимальное число набора для $n=7$, есть $2 \cdot 2 \cdot 2 \cdot 3 \cdot 5=60 \cdot 2$, т.е это $60$.

Для $n=8$ я ошибся. Для чисел $2, 2, 3, 3, 5$ как раз восемь разбиений на произведение двух разных чисел, а не девять. Так что величина набора в этом случае $2 \cdot 3 \cdot 3 \cdot 5=90$.

Получаются такие наборы:
для $n=8: 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90$
для $n=7: 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60$
Числа нужно перемножать по два, начиная с противоположных сторон.

Что я делаю: задаюсь минимальным количеством сомножителей в каждой кучке. Это $2$ сомножителя. Почему минимальным? Не знаю.
Теперь задаемся числом кучек. Это $7$.
Берем минимальный набор самых маленьких простых чисел. Скажем $2, 2, 3$. Это дает два варианта разложения $(2 \cdot 2) \cdot 3 = 2 \cdot (2 \cdot 3)$ или $4 \cdot 3 = 6 \cdot 2$. Нам нужно семь вариантов такого разложения, поэтому нужно добавить простых чисел в набор. Если добавлять самые минимальные, то они начнут повторяться и число комбинаций будет расти медленно. Например, если брать одни только двойки, то для семи комбинаций нужен набор из 14 двоек, а величина этого набора будет $2^{13}$. Если же брать все простые числа по порядку, то их произведение будет быстро расти. Например, для $2, 3, 5, 7$ существует семь разбиений, но порядок набора оказывается большим $3 \cdot 4 \cdot 5 = 105$. Нужно найти минимальный набор минимальных чисел. Количество наборов, которое нужно проверит, невелико. Из всего, что я попробовал, подходит то, что указано в решении.

Да, кстати, оказывается, я не знаю, как подсчитать число сочетаний из $n$ элементов по $m$, если среди этих элементов есть, скажем, $k$ одинаковых. Какая тут формула?

[wrest]

sergey zhukov
Практически нечего добавить, мне кажется все верно у вас.
Хотя, для $n=8$ есть и меньший набор, $k=72$ ($5 \cdot 72=6 \cdot 60 = 360$ и т.п.)

sergey zhukov в сообщении #1421024 писал(а):

Да, кстати, оказывается, я не знаю, как подсчитать число сочетаний из $n$ элементов по $m$, если среди этих элементов есть, скажем, $k$ одинаковых. Какая тут формула?

Тут надо почетче сформулировать, но вообще гляньте вот сюда: «Комбинаторное двенадцатизадачие: раскладываем шары по урнам»

[sergey zhukov]

wrest в сообщении #1421047 писал(а):

Хотя, для $n=8$ есть и меньший набор, $k=72$

Значит, $2, 2, 2, 3, 3, 5$. Я бы не подумал, ведь $2, 2, 3, 3, 5$ дает как раз восемь комбинаций, а $2, 2, 2, 3, 3, 5$ дает уже 10 комбинаций, т.е. тут уже больше чисел, чем нужно.

Насчет числа комбинаций: вот, например, как найти число разных сочетаний по два элемента для множества $2, 2, 2, 3, 3, 5$? В обсуждаемой задаче нужно подсчитывать число возможных разбиений этого множества на два. Я это подсчитал вручную (10 комбинаций). Если речь идет, скажем, о $2, 3, 5, 7, 9, 11$ - то нет проблем. Но если немного усложнить набор, включив повторяющиеся элементы, то число сочетаний сокращается. Но формулу я что-то не могу сообразить.

[wrest]

sergey zhukov в сообщении #1421074 писал(а):

Насчет числа комбинаций: вот, например, как найти число разных сочетаний по два элемента для множества $2, 2, 2, 3, 3, 5$? В обсуждаемой задаче нужно подсчитывать число возможных разбиений этого множества на два. Я это подсчитал вручную (10 комбинаций).

Вообще-то их $11$ :)
2 22335
3 22235
22 2335
5 22233
23 2235
222 335
33 2225
25 2233
223 235
35 2223
233 225
Формула тут простая.
Нужное вам количество равно

$$Q=\dfrac{\prod \limits_{i=1}^{r}\left( a_i+1\right) -2}{2}$$

где $a_i$ -- количество каждого простого числа. $r$ - количество разных простых чисел. Для случая $222335$ имеем $3$ двойки, $2$ тройки и $1$ пятерку, т.е. $a_1=3;a_2=2;a_3=1$ и соответственно, $r=3$
Подставляем: $Q=\dfrac{(3+1)(2+1)(1+1)-2}{2}=\dfrac{4\cdot 3 \cdot 2 - 2}{2}=\dfrac{24-2}{2}=11$
Правда, эта формула не работает если все $a_i$ четные, этот случай надо отслеживать и из числителя вычитать не двойку, а тройку.

[sergey zhukov]

А, эта формула сразу дает число всех возможных разных разбиений множества элементов с повторениями на две разные группы. В этой задаче как раз то, что надо.
Но часто бывает, что нужно получить именно количество сочетаний из $n$ элементов (с повторениями) по $m$. Например, все разные сочетания трех элементов из множества $2, 2, 2, 3, 3, 5$ будут такими:

$2, 2, 2$
$2, 2, 3$
$2, 2, 5$
$2, 3, 3$
$2, 3, 5$
$3, 3, 5$

Как получить их количество?

[wrest]

sergey zhukov в сообщении #1421103 писал(а):

Как получить их количество?

Что-то с наскока не пришло в голову. Думать надо. Может, откроете новую тему? :)

[wrest]

sergey zhukov
В общем, как тут говорят, задача нетривиальная.
Я, во всяком случае, очень удивлюсь, если найдется волшебная формула.
Смотрите: если добавить одну двойку в набор, искомое количество не изменится.
Если добавить одну тройку, искомое количество увеличится на единицу.
Вы взяли количество разных чисел равное количеству элементов в сочетании (три).
В общем, подобавляйте-поудаляйте элементов к исходному набору, может это натолкнёт вас на мысли и собственные попытки решения...