Разбиение множества на неравные части

[николай москвитин]

Вот моя задача по теории множеств, довольно старая.

Условие: некоторое множество разбито на неравные части. Всего в нём n элементов. Каково максимальное возможное число частей (выразить через n )?

[Nadir Zaitov]

Всего в нём n элементов.Элементы равные?
Если да, то решается весьма просто:

Максимум {k: k*(k+1)/2 <= n }

[JH]

Элементы равные?
Если да, то решается весьма просто:

Максимум {k: k*(k+1)/2 <= n }
А свести нельзя к формуле?
Я дошел до
k^2+k>2n
k^2-k<2n
и остановился

[николай москвитин]

А свести нельзя к формуле?
Есть формула! Только в ней не обошлось без квадратных скобок. :)

[Nadir Zaitov]

Есть формула! Только в ней не обошлось без квадратных скобок.Ясен пень - нужна целая часть.

А свести нельзя к формуле?

http://latex.codecogs.com/gif.latex?\left&space;[\frac&space;{\sqrt{8N&plus;1}-1}&space;2&space;\right&space;]

ЦУ. Просто решить квадратное уравнение и откинуть дробную часть

[Наташа]

Может быть попробуем сначала на примере какого нибудь множества решить?:)
и станет все сразу яснее?:)
Например множество
{1,2}
Какие у этого множества существуют подмножества?

ЗЫ Множества называются равными если состоят из тех же элементов:)

[Nadir Zaitov]

ЗЫ Множества называются равными если состоят из тех же элементовРавные или эквивалентные? У нас тут об эквивалентности речь. Или нет?

[Наташа]

Равные или эквивалентные? У нас тут об эквивалентности речь. Или нет? Да, Вы правы, мне теперь тоже стало совершенно непонятно поскольку здесь идет речь о каких то "частях" а не "подмножествах"

[николай москвитин]

идет речь о каких то "частях" а не "подмножествах" Ну, я просто немного неправильно сформулировал. Понятно, что имеются в виду подмножества. Формула получена верно!

[Наташа]

Ну, я просто немного неправильно сформулировал. Понятно, что имеются в виду подмножества. Формула получена верно! Так сколько же по Вашей формуле получается различных подмножеств? скажем например для множества состоящего из 4х элементов:{1,2,3,4}?:)

[Nadir Zaitov]

Так сколько же по Вашей формуле получается различных подмножеств? скажем например для множества состоящего из 4х элементов:Его можно разбить только на 2 различных (по числу элементов, как это предполагалось в условии) подмножества.

[Наташа]

Так сколько же по Вашей формуле получается различных подмножеств? скажем например для множества состоящего из 4х элементов:Его можно разбить только на 2 различных (по числу элементов, как это предполагалось в условии) подмножества.

Его можно разбить только на 2 различных (по числу элементов, как это предполагалось в условии) подмножества.
1 {1}
2 {1,2}
3 {1,2,3}
4 {1,2,3,4}
5 {Ø} -пустое множество
Это, например, множества с разным числом элементов, а есть еще и другие ИМХО не равные друг другу множества:
{3}
{4}
{1,3}
....

[николай москвитин]

например для множества состоящего из 4х элементов А Вы подставьте и вычислите как можно точнее. Например: [(scrt(8*4+1)-1)/2]=[(scrt33-1)/2]прибл.равно [(5,76-1)/2]=[2,38]=2. Теперь логически: если элементов по два, подмножества равны, следовательно, элементов в подмножествах 1 и 3, частей 2.

[николай москвитин]

есть еще и другие ИМХО не равные друг другу множества:Там строго доказано именно для максимального числа частей. Сказать? Выбираются треугольные числа. Они содержат k различных подмножеств с одним, двумя, тремя, и.т.д. элементами. Если их число увеличится, то даже при минимальном значении элементов в сумме они будут больше или равны следующему треугольному числу. Из этого выводится, что целая часть от соответствующего выражения будет равна именно ближайшему нижнему треугольному числу. Поскольку указанный в формуле квадратный трёхчлен принимает целые значения только в треугольных числах.

[Nadir Zaitov]

1 {1}
2 {1,2}
3 {1,2,3}
4 {1,2,3,4}
5 {Ø} -пустое множество
Это, например, множества с разным числом элементов, а есть еще и другие ИМХО не равные друг другу множества:
{3}
{4}
{1,3}
....Вам не подмножества предлагали перечислить, а подсчитать число элементов в самом большом разбиении данного множества на не пересекающиеся подмножества различной мощности. При этом элементами такого разбиения являются подмножества, а не элементы множества - это на всякий случай, чтоб опять не запутать вас с условием задачи :)

[Наташа]

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

Там строго доказано именно для максимального числа частей. Сказать? Выбираются треугольные числа. Они содержат k различных подмножеств с одним, двумя, тремя, и.т.д. элементами. Если их число увеличится, то даже при минимальном значении элементов в сумме они будут больше или равны следующему треугольному числу. Из этого выводится, что целая часть от соответствующего выражения будет равна именно ближайшему нижнему треугольному числу. Поскольку указанный в формуле квадратный трёхчлен принимает целые значения только в треугольных числах. Ваше условие как мне кажется после замены слова "часть" на "подмножество" все же в точности совпадает с теоремой о Булеане, прочитать подробнее с доказательством можете прямо здесь:8): (http://ru.wikipedia.org/wiki/%D0%91%D1%83%D0%BB%D0%B5%D0%B0%D0%BD)

[николай москвитин]

Ваше условие как мне кажется после замены слова "часть" на "подмножество" все же в точности совпадает с теоремой о Булеане

Спасибо за очень интересную ссылку. И всё же имел в виду я то, что сказал Nadir. Задумался о связи теоремы о Булеане и вопроса о разбиении натурального числа на сумму меньших чисел. Кстати, кем и когда она была сформулирована?