Парламентская комбинаторика

[Xenia1996]

В парламенте страны Люсопакан 120 депутатов. Каждый из депутатов может состоять либо в коалиции, либо в оппозиции.
На каждом заседании парламента происходит следующее: либо ровно один депутат переходит из коалиции в оппозицию, либо ровно один депутат переходит из оппозиции в коалицию. По закону этой страны, в коалиции не должно быть менее четырёх депутатов. Также закон запрещает возвращаться к какому-либо из прежних составов коалиции. В один прекрасный день депутат Миберлан вышел на трибуну и заявил, что все возможные варианты состава коалиции уже реализованы. В ответ на это, депутатесса Химаэли обвинила Миберлана во лжи.
А как Вы думаете, кто на самом деле лжец?

[Хорхе]

А где задача?

[Xenia1996]

Хорхе в сообщении #436462 писал(а):

А где задача?

Могут ли слова Миберлана быть правдой?

[Хорхе]

Ну вот, другое дело.

Ну вообще это смотря, как понимать слова Миберлана. Скажем, вот сейчас в коалиции 60 депутатов, но все наборы по 59 и по 61 исчерпаны (а только эти наборы и являются на данный момент "возможными").

[age]

Если вопрос в том, конечно ли возможное число коалиций, то ответ. Да.

[Xenia1996]

Хорхе в сообщении #436478 писал(а):

Ну вот, другое дело.

Ну вообще это смотря, как понимать слова Миберлана. Скажем, вот сейчас в коалиции 60 депутатов, но все наборы по 59 и по 61 исчерпаны (а только эти наборы и являются на данный момент "возможными").

Ну, это частный случай. Я просто по-детски сформулировала задачу. Надо было так:

Возможно ли в принципе реализовать все законные составы коалиции?

Так понятнее? Если нет, переформулирую снова.

-- Пн апр 18, 2011 23:06:05 --

age в сообщении #436480 писал(а):

Если вопрос в том, конечно ли возможное число коалиций, то ответ. Да.

То, что оно конечно, это и первоклашке понятно.

[venco]

В задаче не требуется реализовать все законные составы, а только все доступные из текущего состава. Так вот, эта ситуация возможна, и реализуема в течение одного года.
А вот насчёт вообще всех возможных составов...

[Xenia1996]

venco в сообщении #436483 писал(а):

В задаче не требуется реализовать все законные составы, а только все доступные из текущего состава. Так вот, эта ситуация возможна, и реализуема в течение одного года.
А вот насчёт вообще всех возможных составов...

А вот насчёт вообще всех возможных составов - это как раз легко! И именно это я имела в виду, просто не умею формулировать задачи.

[age]

Xenia1996 в сообщении #436485 писал(а):

И именно это я имела в виду, просто не умею формулировать задачи.

А вот от этого зависит 50% интереса к задаче.

-- Вт апр 19, 2011 00:19:27 --

Честно говоря, не вижу смысла "додумывать" условие за автора задачи. Чтобы догадаться, так что же на самом деле имел в виду автор?

[Xenia1996]

age в сообщении #436488 писал(а):

А вот от этого зависит 50% интереса к задаче.

-- Вт апр 19, 2011 00:19:27 --

Честно говоря, не вижу смысла "додумывать" условие за автора задачи. Чтобы догадаться, так что же на самом деле имел в виду автор?

Вы абсолютно правы, но не в данном случае, ибо красота задачи с лихвой компенсирует тупо...ость авторши.

[MrDindows]

Депутат Миберлан наглым образом врёт.
Из каждой коалиции с чётным коаличеством людей можно получить только коалицию с нечётным количеством людей и наоборот. Поэтому, для того чтоб получить все возможные коалиции, суммарные количества чётных и нечётных коалиций должны отличатся не более чем на 1. А в нашем случае разница равна:
$120-\frac{120!}{2!\cdot118!}+\frac{120!}{3!\cdot117!}>1$

[Xenia1996]

В целом, Ваше решение верно. Но при чём здесь 197? Вы, наверно, имели в виду 117?

[MrDindows]

Да, конечно) Очепятался...

Кстати, условие задачи сформулировано вполне четко:
"...реализованы ВСЕ ВОЗМОЖНЫЕ варианты состава коалиции."
Эти слова должны трактоваться только так, как сказала Ксения. Тут вовсе не спрашивается про конечность этого числа и вовсе нету слов "возможные НА ДАННЫЙ МОМЕНТ".
И додумывать никто не заставляет, главное внимательно прочитать и правильно понять)

А задача сама по себе понравилась. Сначала в голову лезут всякие графы, потом идут попытки построить способ получения всех вариантов коалиции...
Ну и ещё, по-моему, надо доказать, что в разложении бинома
$(x+1)^n $, сумма коэффициентов где икс в чётной степени равна сумме коэффициентов нечётной степени. Тоесть, что если бы не было ограничения на 4 человека в коалиции, суммы вариантов были бы равны.

[Xenia1996]

MrDindows в сообщении #436512 писал(а):

Ну и ещё, по-моему, надо доказать, что в разложении бинома
$(x+1)^n $, сумма коэффициентов где икс в чётной степени равна сумме коэффициентов нечётной степени. Тоесть, что если бы не было ограничения на 4 человека в коалиции, суммы вариантов были бы равны.

Какой бином, какие кроссовки?
Число подмножеств с чётным числом элементов равно числу подмножеств с нечётным числом элементов. Доказывается построением взаимооднозначного соответствия.

[Хорхе]

MrDindows в сообщении #436512 писал(а):

Кстати, условие задачи сформулировано вполне четко:
"...реализованы ВСЕ ВОЗМОЖНЫЕ варианты состава коалиции."
Эти слова должны трактоваться только так, как сказала Ксения. Тут вовсе не спрашивается про конечность этого числа и вовсе нету слов "возможные НА ДАННЫЙ МОМЕНТ".
И додумывать никто не заставляет, главное внимательно прочитать и правильно понять)

Это сказала не Xenia1996, а депутат. Я не знаю, как ваши депутаты, а наши -- чрезвычайно косноязычные. Так что вполне возможна такая ситуация: Миберлан рано утром встал и понял, что коалицию-то не сформировать! К выступлению он толком не подготовился, так что сообщил об этом как смог.

А если серьезно, то перечитайте условие, которое написала Xenia1996. Там действительно не так очевидно. В один прекрасный день депутат Миберлан вышел на трибуну и заявил, что все возможные варианты состава коалиции уже реализованы. Учитывая, что коалиция формируется каждый день и что вот сегодня ее надо сформировать из того, что имеем, трактовка, приведенная в предыдущем абзаце, вполне возможна. В конце концов, чтобы парламент продолжил работу, необходимо, чтобы...