|
Название: Согласие в думе Отправлено: fortpost от Февраль 20, 2012, 23:28:58 Каждый депутат Думы поссорился ровно с тремя другими депутатами. Президент обязал спикера разбить депутатов на n фракций так, чтобы внутри одной фракции царило согласие. При каком наименьшем n это всегда возможно? (Это значит, что на n фракций депутатов можно было разбить всегда, а на (n — 1) фракцию — уже не всегда.)
Название: Re: Согласие в думе Отправлено: монЯрхъ от Февраль 21, 2012, 07:24:29 Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 07:40:18 Название: Re: Согласие в думе Отправлено: Валерий от Февраль 21, 2012, 08:06:17 Название: Re: Согласие в думе Отправлено: монЯрхъ от Февраль 21, 2012, 08:12:34 Доказательство: Показать скрытый текст
Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 08:43:47 Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 08:47:18 Одолевают смутные сомнения... Как будто чтой-то в вашем доказательстве не так, но что именно... Чуть позже выдам авторское решение и сравним.
Название: Re: Согласие в думе Отправлено: Валерий от Февраль 21, 2012, 08:51:37 Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно.
Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 09:55:22 Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно. Наверное, неважно. Главное, чтобы №1 и №2 оказались в разных фракциях. Название: Re: Согласие в думе Отправлено: Валерий от Февраль 21, 2012, 10:31:59 Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно. Наверное, неважно. Главное, чтобы №1 и №2 оказались в разных фракциях. Название: Re: Согласие в думе Отправлено: монЯрхъ от Февраль 21, 2012, 11:54:59 Дело даже не в числе депутатов. Просто в условии не сказано, что те трое депутатов с кем спорить 4-й - спорят между собой. Поэтому процедура отбора такая.
- берет депутата: помещаем его в Первую фракцию, тех троих с кем он спорит в Буфер. - и так пока депутаты не кончаться - потом рассматривает депутатов из Буфера, в нем, следовательно, любой депутат будет иметь одного спорящего в Первой фракции и еще двоих. - этого депутата помещаем во Вторую фракцию, его двоих спорящих во 2-ой буфер, и так всех - потом разбрасываем депутатов из 2-ого буфера между Третьей и Четвертой фракцией. Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 12:42:46 Дело даже не в числе депутатов. Просто в условии не сказано, что те трое депутатов с кем спорить 4-й - спорят между собой. Поэтому процедура отбора такая. Вроде все логично. Но почему же авторский ответ не такой? Значит, выдам авторское решение, и посмотрим, в чем дело.- берет депутата: помещаем его в Первую фракцию, тех троих с кем он спорит в Буфер. - и так пока депутаты не кончаться - потом рассматривает депутатов из Буфера, в нем, следовательно, любой депутат будет иметь одного спорящего в Первой фракции и еще двоих. - этого депутата помещаем во Вторую фракцию, его двоих спорящих во 2-ой буфер, и так всех - потом разбрасываем депутатов из 2-ого буфера между Третьей и Четвертой фракцией. Название: Re: Согласие в думе Отправлено: пестерь от Февраль 21, 2012, 13:20:06 Так, а число депутатов не обезательно должно быть равным во всех фракциях?
Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 13:22:17 Название: Re: Согласие в думе Отправлено: fortpost от Февраль 21, 2012, 13:23:19 Так, а число депутатов не обезательно должно быть равным во всех фракциях? Нет, конечно.Название: Re: Согласие в думе Отправлено: moonlight от Февраль 22, 2012, 00:12:45 Не понятно каким образом можно перессорить 7 депутатов так чтобы каждый имел ровно трёх врагов. Это возможно только для чётного числа. Показать скрытый текст Название: Re: Согласие в думе Отправлено: монЯрхъ от Февраль 22, 2012, 07:33:19 Мне понятны причины использования метода индукции автором, но не ясно почему за n он принимает 7. Почему не 1,2 или 3 - понятно, при таком коилчестве фракций неизбежно в одной из фракций будет как минимум 2 спорящих между собой. Но почему отвергает 4...
Перефразирую любимый персонаж: "Это неправильный автор, он делает не правильный мёд!" (рука не поднялась искаверкать фразу целиком). Название: Re: Согласие в думе Отправлено: Димыч от Февраль 22, 2012, 07:53:02 Да вы на стрелки посмотрите на картинке. Отношение ссоры считается здесь несимметричным.
Название: Re: Согласие в думе Отправлено: moonlight от Февраль 22, 2012, 08:31:04 То что ссоры могут быть несимметричными в условии не сказано. В таком случае проще было сказать что каждый депутат может иметь не менее 3 и не более 6 врагов.
Название: Re: Согласие в думе Отправлено: Валерий от Февраль 22, 2012, 08:40:35 Мне понятны причины использования метода индукции автором, но не ясно почему за n он принимает 7. Почему не 1,2 или 3 - понятно, при таком коилчестве фракций неизбежно в одной из фракций будет как минимум 2 спорящих между собой. Но почему отвергает 4... Я задал себе вопрос: а если найдутся 5 паршивцев, когда каждый каждому враг, то 4 уже мало. А если 6 или 7.Видимо автор доказал, что максимально возможная система, когда каждый каждому враг состоит из 7 депутатов, тогда и 7 фракций хватает. Название: Re: Согласие в думе Отправлено: Валерий от Февраль 22, 2012, 08:45:47 На картинке не нарисованы стрелки спора №7 с №№2 и 3
Название: Re: Согласие в думе Отправлено: fortpost от Февраль 22, 2012, 11:17:26 То что ссоры могут быть несимметричными в условии не сказано. В таком случае проще было сказать что каждый депутат может иметь не менее 3 и не более 6 врагов. Ваша правда, недоглядел. >:( Лучше, разумеется, "ссорящихся" заменить на "врагов". А то ссора автоматически воспринимается, как двунаправленная связь. |