Математика. Подготовка к ЕГЭ. Решение задач. 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/ |