Просто красивая математико-логическая задачка, напечатанная вроде в Кванте 1970 года выпуска. Выборам в США посвящается;) ( Демократические выборы?.. )
ну... по логике ставить в группу "своих" больше, чем (X+1)/2, смысла нет, всё равно уже выиграешь. (X нечётное). меньше, чем (X+1)/2, но не 0 ставить тоже смысла нет, всё равно проиграешь. значит в группу надо ставить ровно (X+1)/2. количество шагов тоже жёстко зависит от X... отсюда находим X. я даже порешал, в итоге сводится к неравенству типа 2*x^a-x-1 > 0, где a = log_N (2n), N - общее число граждан, n - число "своих".
э. хм. поправь если что, но всё таки: пусть Х=3 - очевидно нечётное, ну и маленькое, да. Обозначим + правильного избирателя - тех, кто шакалит у посольств ;) на первом шаге нам нужно (++-) 2/3 голосов на втором (++-)(++-)(---) 4/9 выбор объяснить просто - для решения нам нужно минимальное численное превосходство, тратить же сторонников на заведомо проигрышные секции глупо. третий шаг (++-)(++-)(---) (++-)(++-)(---) (---)(---)(---) 8/27. т.е мы имеем (2/3)^n - необходимое для победы при такой стратегии число преданных товарищей к общему числу оных, назовем его КПИ - коэффициент правильных избирателей
очевидненько, что при n=12 кпи уже меньше 1%, при том, что общее население чуть больше полумиллиона Чем больше n, тем всё ещё эффективнее. победа нашему герою гарантирована.
дальше хуже. Так же мы можем оперировать с любым! нечетным числом, только КПИ_0 будет не 2/3 а (х+1)/2х.
Бинго!=) Там при большем размере группы основание степени поменьше будет, правда, так что там считать надо, но вроде все так. В Штатах вроде несколько более извращенная система, так что про 25% не уверен, но в принципе да, их система согласно этим рассуждениям куда более интересна для манипуляций, чем обычное прямое голосование.
Кажется, это задачка оу- мы что-то такое решали на праке в прошлом году только с трубами и заводами и загрязнением. я полагаю, что в одни кучки надо пихать только оппозицию - в другие - 51% солдат, вот только размер x я пока не придумала:)
ну чего непонятно-то. я вроде всё правильно решил :-) X нечётное. в группу ставим либо 0 своих, либо (X+1)/2 своих. причём так, чтобы на каждом шаге в уже выбранных группах получалось снова либо 0 своих, либо (X+1)/2 своих. это будет, так сказать, "наиболее оптимальное использование ресурса". при заданном X никакое другое распределение "своих" по группам лучше не сделает. остаётся определить X. всего народу N, "своих" n. на каждом шаге количество народа всего уменьшается в X раз, а число "своих" уменьшается только в (X+1)/2 раз. число шагов известно - оно жёстко зависит от X - это k = (-1 + log_X (N)). Получается неравенство: (своих на k-ом шаге > половины группы): n*(2/(X+1))^k > N/(X^k)/2, это ((X+1)/2)^(log_X (N)) < n, берём логарифм по основанию N, получаем log_X ((X+1)/2) < log_N (n), правая часть - константа = a, (X+1)/2 < X^a => получаем то неравенство, что я сказал: 2*X^a - X - 1 > 0, где a = log_N (n)...
Comments 12
Reply
Reply
пусть Х=3 - очевидно нечётное, ну и маленькое, да.
Обозначим + правильного избирателя - тех, кто шакалит у посольств ;)
на первом шаге нам нужно
(++-) 2/3 голосов
на втором
(++-)(++-)(---) 4/9
выбор объяснить просто - для решения нам нужно минимальное численное превосходство, тратить же сторонников на заведомо проигрышные секции глупо.
третий шаг
(++-)(++-)(---) (++-)(++-)(---) (---)(---)(---) 8/27.
т.е мы имеем (2/3)^n - необходимое для победы при такой стратегии число преданных товарищей к общему числу оных, назовем его КПИ - коэффициент правильных избирателей
очевидненько, что при n=12 кпи уже меньше 1%, при том, что общее население чуть больше полумиллиона
Чем больше n, тем всё ещё эффективнее. победа нашему герою гарантирована.
дальше хуже. Так же мы можем оперировать с любым! нечетным числом, только КПИ_0 будет не 2/3 а
(х+1)/2х.
имеем задачу в общем виде:
((х+1)/2х)^n <= 0.01 при ( ... )
Reply
Reply
Reply
Reply
X нечётное.
в группу ставим либо 0 своих, либо (X+1)/2 своих.
причём так, чтобы на каждом шаге в уже выбранных группах получалось снова либо 0 своих, либо (X+1)/2 своих.
это будет, так сказать, "наиболее оптимальное использование ресурса". при заданном X никакое другое распределение "своих" по группам лучше не сделает.
остаётся определить X. всего народу N, "своих" n. на каждом шаге количество народа всего уменьшается в X раз, а число "своих" уменьшается только в (X+1)/2 раз. число шагов известно - оно жёстко зависит от X - это k = (-1 + log_X (N)). Получается неравенство: (своих на k-ом шаге > половины группы): n*(2/(X+1))^k > N/(X^k)/2, это ((X+1)/2)^(log_X (N)) < n, берём логарифм по основанию N, получаем log_X ((X+1)/2) < log_N (n), правая часть - константа = a, (X+1)/2 < X^a => получаем то неравенство, что я сказал: 2*X^a - X - 1 > 0, где a = log_N (n)...
Reply
Reply
Reply
Leave a comment