Раз уж такое затишье, рискну предложить следующую задачку. Я ее давно не решался выложить, т.к. не знаю изящного решения.

Выборы проводятся по общепринятой формуле:
Если ни один кандидат не набирает в первом туре больше 50% голосов, то назначается второй тур, в котрый выходят два кандидата набравшие больше всего голосов в первом туре. Во втором туре побеждает набравший простое большинство.

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

Дополнительное условие:
Предпочтения каждого отдельного избирателя считать строго упорядоченными.
То есть:
1. Из любой пары кандидатов избиратель всегда выбирает одного.
2. Предпочтения транзитивны. Если избиратель из пары a,b выбирает a, а из пары b,c выбирает b, то из пары a,c он выберет a.

Обзавем кандидатов А, В, С, "нашего" — А
будем пользоваться такой записью:
40 ABC означает: у 40% избирателей на первом месте А потом В, потом С.

Решение задачи:
до агитации
37 АBC
30 ВСА
2 BАС
31 CАВ

2-й тур:
68 А
32 В

после агитации
39 АВС
30 ВСА
31 САВ

2-й тур:
39 А
61 С

Здравствуйте, MichaelP, Вы писали:

MP>Накануне выборов штаб одного из кандидатов провел тщательное и достоверное исследование. По итогам исследования выяснилось, что их кандидат побеждает. Но они решили подстраховаться и усилили агитацию. В результате часть избирателей изменила свое мнение в пользу этого кандидата, у других мнение не ухудшилось. Относительное мнение о других кандидатах (т.е. предпочтения избирателей без учета этого кандидата) не изменились. После чего кандидат проиграл выборы...
MP>Вопрос: Возможно ли такое?

Ответ да.

Пусть до и после агитации у Чубайса, Зюганова и Грызлова было столько строронников

    До  После
СПС 11   13  
КП  11    9 
ЕР  10   10

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

До агитации во второй круг выходили СПС и Компартия.
Электорат Единой России голосовал во втором туре за СПС,
так как очень боялся коммунистов.
Поэтому выигрывал выборы Чубайс.

После агитации во второй круг вышли СПС и Единая Россия.
Коммунисты Чубайса ненавидят,
поэтому проголосовали дружно против него.
Выиграл выборы Грызлов.

Здравствуйте, Les, Вы писали:

Les>Обзавем кандидатов А, В, С, "нашего" — А
Les>будем пользоваться такой записью:
Les>40 ABC означает: у 40% избирателей на первом месте А потом В, потом С.

Les>Решение задачи:
...
Возникает следующий интересный вопрос:
Какой максимальный процент изменивших мнение избирателей, чтобы условие оставалось в силе?

Ответа на этот вопрос я не знаю.

Такого типа задачи решаются на стандартном предмете факультета кибернетики Киевского университета "Теория принимания решений". Еще в этом курсе показывается, что ни один из существующих на практике методов подсчета голосов и выбора кандидата не есть оптимальным. То есть, всегда можно показать расклад, когда побеждает не лучший кандидат. В некоторых случаях — самый худший.

Примеры могу посмотреть, но на память не помню.

Здравствуйте, King Oleg, Вы писали:

KO>Такого типа задачи решаются на стандартном предмете факультета кибернетики Киевского университета "Теория принимания решений". Еще в этом курсе показывается, что ни один из существующих на практике методов подсчета голосов и выбора кандидата не есть оптимальным. То есть, всегда можно показать расклад, когда побеждает не лучший кандидат. В некоторых случаях — самый худший.

Здесь большой вопрос, что считать оптимальным выборам. Существует много систем выборов удовлетворяющих достаточно разумным критериям. Например, то свойство, которое нарушается в моем примере называется монотонностью и соблюдается во многих системах.
Насколько я помню, самые серьезные ограничения дает принцип "Независимость от постронних альтернатив". Грубо говоря, это принцип требует, чтобы даже тогда, когда избирателю известны предпочтения других избирателей, ему было бы все равно выгодно голосовать за своего кандидата. Т.е. "отсекает" следующую логику: "Все равно мой кандидат не проходит, т.ч. буду голосовать за более проходного"

Как доказал Эрроу, одного этого принципа достаточно для того, чтобы при числе кандидатов больше двух, единственным возможным правилом голосования являлось диктаторское, т.е. когда в расчет принимается мнение только одного избирателя. Сам "диктатор" при этом может определяться случайно. Кстати, за эти работы Эрроу получил нобелевскую премию.

Здравствуйте, MichaelP, Вы писали:

MP>Возникает следующий интересный вопрос:
MP>Какой максимальный процент изменивших мнение избирателей, чтобы условие оставалось в силе?

MP>Ответа на этот вопрос я не знаю.

25+0.02 ABC
25 BCA
25-0.03 BAC <-- передумывают
25+0.01 CAB

Доказать сложнее.
Схема:
1) Показать, что решение единственное
2) Решать задачу линейного программирования симплекс-методом