Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Олимпиады




 Страница 1 из 1 [ Сообщений: 7 ] 



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

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


Вернуться наверх 
 Заголовок сообщения: Re: Разбиение множества
 Сообщение Добавлено: 24 мар 2015, 20:49 
Не в сети
Аватар пользователя

Зарегистрирован: 31 янв 2011, 17:37
Сообщений: 4974
Откуда: Санкт-Петербург
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`.
Как-то так, если не ошибся.

_________________
Сопротивление бесполезно.


Вернуться наверх 
 Заголовок сообщения: Re: Разбиение множества
 Сообщение Добавлено: 24 мар 2015, 21:27 
Не в сети

Зарегистрирован: 10 сен 2011, 23:41
Сообщений: 968
Откуда: Казань
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`.
Кто больше? :)


Вернуться наверх 
 Заголовок сообщения: Re: Разбиение множества
 Сообщение Добавлено: 24 мар 2015, 21:51 
Не в сети
Аватар пользователя

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

Согласен.

_________________
Сопротивление бесполезно.


Вернуться наверх 
 Заголовок сообщения: Разбиение множества
 Сообщение Добавлено: 24 мар 2015, 22:47 
Не в сети

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


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


Вернуться наверх 
 Заголовок сообщения: Re: Разбиение множества
 Сообщение Добавлено: 24 мар 2015, 23:52 
Не в сети
Аватар пользователя

Зарегистрирован: 31 янв 2011, 17:37
Сообщений: 4974
Откуда: Санкт-Петербург
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 -четное.

_________________
Сопротивление бесполезно.


Вернуться наверх 
 Заголовок сообщения: Re: Разбиение множества
 Сообщение Добавлено: 25 мар 2015, 11:59 
Не в сети

Зарегистрирован: 20 дек 2013, 17:51
Сообщений: 118
Откуда: Занзибар
Очень благодарен Вам vyv2!


Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 1 из 1 [ Сообщений: 7 ] 





Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: