Условие (стр. 2 )

100*(количество голосов, набранных ПЛМ)/(количество голосов, набранных всеми партиями, прошедшими в парламент)=
=100*(количество голосов, набранных ПЛМ)/((общее количество избирателей)-(количество голосов, набранных всеми партиями, не прошедшими в парламент))

Отсюда видно, что наибольшее число мест ПЛМ получит в том случае, если общее количество голосов, отданных за непрошедшие партии, максимально. Если бы в парламент не прошли 11 партий, они вместе набрали бы не более 55% голосов, но 55%+25%<100%. Значит не прошли в парламент максимум 10 партий, и они набрали в сумме не более 50% голосов. Поэтому ПЛМ получит в парламенте не более 50 мест.

Условие

Из колоды вынули 7 карт, показали всем, перетасовали и раздали Грише и Лёше по 3 карты, а оставшуюся карту
а) спрятали;
б) отдали Коле.
Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят открытым текстом.)

Решение

а) Пусть Гриша скажет: "У меня либо {называет свои карты}, либо {называет три карты, которых у него нет}". После этого Лёша должен сказать: "У меня либо {называет свои карты}, либо {называет три карты Гриши, если второй из наборов, названных Гришей, не совпадает с его набором, и любые другие три карты, которых у него нет, иначе}". После этого каждый из них, очевидно, знает весь расклад. Коле же ничего не ясно. Действительно, названо три набора карт: A, B и C. Наборы B и C пересекаются по двум картам, Гриша сказал: "У меня либо A, либо B", Лёша сказал: "У меня либо A, либо C". Это означает, что либо у Гриши набор A, а у Лёши - C, либо у Гриши - B, а у Лёши - A. Конечно, эти расклады различны, и даже закрытую карту определить нельзя. б) Заметим, что предыдущий способ не работает: зная закрытую карту, Коля может всё определить. Занумеруем карты числами от 0 до 6. Пусть Гриша и Лёша по очереди назовут остатки от деления суммы номеров своих карт на 7. Тогда они узнают расклад: каждый из них должен лишь прибавить к своей сумме сумму другого и найти остаток, противоположный этой общей сумме по модулю 7 (т. е. такой, который при прибавлении к этой сумме даёт число, делящееся на 7). Это и будет номер закрытой карты. После этого восстановление расклада не составляет труда. Проверим, что Коля ничего не узнал. Рассмотрим карту с номером s. Покажем, что она могла попасть к Грише, если он назвал сумму a. Для этого надо дополнить эту карту двумя другими с суммой номеров a-s. Легко видеть, что существует три различные пары номеров, дающие в сумме a-s. Из них две, возможно, испорчены тем, что туда входит карта с номером s или закрытая карта, но как минимум одна пара остаётся. Ей мы и дополним набор Гриши. Такие же рассуждения показывают, что любая карта могла оказаться и у Лёши.

Условие

В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если это кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся.
На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре k-е место по числу голосов. Определите наибольшее возможное значение k, если Остап Бендер был избран
а) в 1002-м туре;
б) в 1001-м туре.

Решение

а) Остап не мог занять последнее, 2002-е место в первом туре, поскольку иначе он сразу же выбыл бы из числа кандидатов. Поэтому k<2001.

Пусть все кандидаты в первом туре набрали почти поровну, Остап занял предпоследнее место и в каждом следующем туре получал все голоса выбывшего кандидата. Тогда Остап победит в тот момент, когда количество выбывших кандидатов достигнет половины. Это случится как раз в 1002-м туре.

Выполним точный подсчёт в случае, когда кандидаты в первом туре набрали 106, 106+1, ..., 106+2001 голос. Тогда в 1001-м туре у Остапа ещё меньше половины голосов, а именно: голоса всех кандидатов, занявших последние 1001 место в первом туре. Однако в 1002-м туре у него уже более половины всех голосов. Действительно, у Остапа
106+(106+1)+...+(106+1001)=
=1002*106+(1001*1002)/2=
=1002*106+1001*501=1002501501
голосов, а всего избирателей
106+(106+1)+...+(106+2001)=
=2002*106+(2001*2002)/2=
=2002*106+2001*1001=2004003001.
Нетрудно проверить, что это меньше удвоенного числа голосов Остапа.

б) Предположим, что k>1. Кандидата, занявшего первое место в первом туре, назовём фаворитом. Тех, кто выбыл в первой тысяче туров, назовём аутсайдерами, а всех остальных кандидатов, кроме Остапа, - лидерами. Поскольку число аутсайдеров 1000, а лидеров 1001, то один из лидеров не получал голосов аутсайдеров. В первом туре (и позже) он имел больше голосов, чем любой аутсайдер (так как в конечном счёте выбыл аутсайдер, а не этот лидер). Поэтому фаворит, набравший в первом туре наибольшее число голосов, не входит в число аутсайдеров.

Максимальное число голосов, которое мог собрать Остап к 1001-му туру, - это все голоса аутсайдеров на момент вылета каждого из них и голоса первоначальных избирателей Остапа. Любой из лидеров в любом из первой тысячи туров (а тем более в 1001-м) имеет больше голосов, чем аутсайдер этого тура. Фаворит заведомо имеет больше, чем имел Остап в первом туре. Поэтому лидеры в сумме имеют в 1001-м туре больше голосов, чем Остап, и он не может стать победителем.

Дополнительный вопрос (в условие предлагавшейся на олимпиаде задачи не входит): изменится ли ответ в задаче, если голоса выбывшего кандидата произвольно делятся между оставшимися?

Ответ

k=2001;
б) k=1.

Условие

В тюрьму поместили 100 узников. Надзиратель сказал им:
"Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.

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

Придумайте стратегию, гарантирующую узникам освобождение.

Решение

Узники выбирают одного определённого человека (будем называть его "счётчиком"), который будет считать узников по такой системе: если, приходя в комнату, он обнаруживает, что свет включён, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из оставшихся узников действует по такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, "счётчик" говорит, что все узники уже побывали в комнате.

Действительно, каждый узник, кроме "счётчика", включит свет в комнате не более одного раза. Когда "счётчик" насчитает 99, он может быть уверен, что все остальные узники уже побывали в комнате хотя бы раз, кроме того он сам уже побывал в комнате. Получается, что к этому моменту все узники заведомо побывали в комнате хоть раз.

Остаётся доказать, что каждый из 99 узников включит свет. Предположим, что это не так - свет будет включён менее 99 раз. Тогда, начиная с некоторого дня n, свет включаться не будет. Так как никакой заход в комнату не будет для счётчика последним, он побывает в комнате после этого дня (например, на m-й день, m>n). Если свет при этом горел, он его выключит. Значит, начиная с (m+1)-го дня свет будет всё время выключен. Рассмотрим узника, который свет ещё ни разу не зажигал. Так как и для него никакой заход в комнату не последний, он побывает в комнате после m-го дня. Но тогда он должен включить свет - противоречие.

Условие

К берегу Нила подошла компания из шести человек: три бедуина, каждый со своей женой. У берега находится лодка с вёслами, которая выдерживает только двух человек. Бедуин не может допустить, чтобы его жена находилась без него в обществе другого мужчины. Может ли вся компания переправиться на другой берег?

Решение

Переправу можно осуществить следующим образом.

Ответ

Да, может.

Условие

За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые любого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что любые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.

Решение

Заметим, что если у человека есть знакомые, сидящие рядом друг с другом (в частности, если он знаком со своим соседом), то этот человек знаком со всеми. Докажем, что такой гость найдется. Пусть A и B — двое соседей. Если они не знакомы между собой, то их общий знакомый C знаком со всеми, так как его знакомые сидят без промежутков. В противном случае со всеми знаком человек A (по той же причине).