Математика. Подготовка к ЕГЭ. Решение задач.
https://alexlarin.com/

Разбиение множества
https://alexlarin.com/viewtopic.php?f=671&t=11836
Страница 1 из 1

Автор:  atakga [ 24 мар 2015, 08:50 ]
Заголовок сообщения:  Разбиение множества

Подскажите пожалуйста идею решения этой задачи:
Найти количество способов разбиения множества `{1,2,.......,2006}` на три не пустых подмножества, в каждом из которых нет двух последовательных чисел.
Спасибо заранее!

Автор:  vyv2 [ 24 мар 2015, 20:49 ]
Заголовок сообщения:  Re: Разбиение множества

atakga писал(а):
Подскажите пожалуйста идею решения этой задачи:
Найти количество способов разбиения множества `{1,2,.......,2006}` на три не пустых подмножества, в каждом из которых нет двух последовательных чисел.
Спасибо заранее!

Обозначим число способов разбиения множества `{1,2,.......,n}` при `n>=3`, отвечающих условию задачи, `S_n`.
Каждое разбиение из n элементов при добавлении n+1 -го элемента увеличивается в два раза, т.к. только одно из трех подмножеств содержит число n , а два других подмножества допускают добавление n+1 -го элемента, не нарушая условия образования подмножеств. Значит `S_(n+1)=2S_n`.
При n=3 `S_3=1`. По индукции `S_n=2^(n-3)` и `S_2006=2^2003`.
Как-то так, если не ошибся.

Автор:  Иваныч [ 24 мар 2015, 21:27 ]
Заголовок сообщения:  Re: Разбиение множества

vyv2 писал(а):
Обозначим число способов разбиения множества `{1,2,.......,n}` при `n>=3`, отвечающих условию задачи, `S_n`.
Каждое разбиение из n элементов при добавлении n+1 -го элемента увеличивается в два раза, т.к. только одно из трех подмножеств содержит число n , а два других подмножества допускают добавление n+1 -го элемента, не нарушая условия образования подмножеств.

Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`.
Кто больше? :)

Автор:  vyv2 [ 24 мар 2015, 21:51 ]
Заголовок сообщения:  Re: Разбиение множества

Иваныч писал(а):
Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`.
Кто больше? :)

Согласен.

Автор:  atakga [ 24 мар 2015, 22:47 ]
Заголовок сообщения:  Разбиение множества

Подробности:
Иваныч писал(а):
Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`.
Кто больше? :)


Спасибо vy2 и Иваныч! Иваныч можно ли подробно написать Ваше решение. Как-то я не понял Вашу идею решения.

Автор:  vyv2 [ 24 мар 2015, 23:52 ]
Заголовок сообщения:  Re: Разбиение множества

atakga писал(а):
Подробности:
Иваныч писал(а):
Еще вариант: `(n+1)`-й элемент помещаем "в карантин" - отдельную клетку, а элементы с `1`-го по `n`-й разбрасываем в две оставшиеся клетки (единственным способом). В итоге `S_(n+1)=2S_n +1` и `S_n = 2^(n-2)-1`.
Кто больше? :)


Спасибо vy2 и Иваныч! Иваныч можно ли подробно написать Ваше решение. Как-то я не понял Вашу идею решения.

Иваныч помимо моего способа увеличения числа способов разбиений из n элементов на три подмножества за счет добавления п+1-го числа, которое увеличивает число способов разбиений в два раза, добавил еще одно разбиение, состоящее в одном подмножестве из одного элемента {n+1} и двух других подмножеств {1,3,...,n}, если n - нечетное, и {2,4,...,n), если n -четное.

Автор:  atakga [ 25 мар 2015, 11:59 ]
Заголовок сообщения:  Re: Разбиение множества

Очень благодарен Вам vyv2!

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/