В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 000 000 избирателей, из которых только один процент (регулярная армия Анчурии) поддерживает Мирафлореса. Он хочет быть демократически избранным.

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

можно я буду рассматривать 200 населения и 2 человека армия?

Прям как в США, там тоже выборщики.

(0) можно
(1) можно, но ответ тогда будет "нельзя"

делим сначала на 25 групп по 800,000, нам нужны голоса только 13 групп, поэтому остается 13 групп по 800,000 = 10,400,000
потом делим опять каждую группу на 25, уже по 32,000
потом опять по 25
потом по 25 уже не делится, делим по 13, потом еще раз по 13 и остается меньше миллиона тех, чьи голоса нужны, т.е. армии хватит

Где-то у меня были конспекты по "Теории игр"...

*(3) ответ похоже всё-таки нельзя. При населении 25 млн было бы можно.
И такой ответ (входные условия) как-то обесценивает задачу в контексте данной ветки)

(4) "делим по 13" это невозможно, по условию группы равные

(7) они будут равные

(1)  при этом раскладе нельзя,

при дроблении и многоступечнатых выборах в 10 этапов можно
\

,

(8) 20 000 000 не делится на 13

(4) 25 - подбором взял?

(11) делить надо на 5, тогда для победы надо
3 из 5,
9 из 25,
27 из 125,
81 / 625,
243 / 3125,
729 / 1562
...
3^n / 5^n

то есть решаем уравнение
3^n / 5^n = <Количество всего>/100*<Количество в процентах за>

3^n / 5^n = 200 000

Легко. В США как раз так.
Пофигу как там делить или умножать.
В результате у тебя получается всего пара десятков выборщиков которые выбирают президента.
Они же люди, у них кровь течет, это всего 20 человечков. К каждому приходит специальный человек, с большим ножичком, крутит им возле яиц и говорит за кого проголосовать.
На следующий день 19 человек голосуют за президента. 19, потому что всегда найдется один придурок который считает что перехитрит всех. Он потом подавится оливкой в ресторане и сдохнет.

(12) Можно и на 3, тогда 2^n/3^n, просто чем большая степень дробления, тем меньше нужно превышение над 1/2, например 2/3-1/2=1/6 разница, а для 3/5-1/2 - уже 1/10. А для 13/25-1/2=1/50

(16) 20 000 000 не делится на 3

(13) Вообще-то получаем 5^n=20 000 000 и 3^n = 200 000,

(17) Ну я так, абстрактно считал )))

(6) отзывается. Ответ: можно.

Получается такая система: (Ч-числитель З - знаменатель) Л - последняя, самая маленькая группа человек.
1) Ч%2=1 (Ч - нечетное)
2) Ч^n*Л=20 000 000
3) З = Ч/2+0.5
4) З^n*(Л/2+1) < 200 000
Так?

Блин, Ч и З местами перепутал...
1) З%2=1 (Ч - нечетное)
2) З^n*Л=20 000 000
3) Ч = З/2+0.5
4) Ч^n*(Л/2+1) < 200 000

http://www.picshare.ru/view/8893331/

http://kvant.ras.ru/1970/07/resheniya_zadachnika_kvanta_ma.htm

(24) забавна оговорка в 1970-м году
"Кстати, по такой системе голосуют во многих капиталистических странах."

20000000=5^7*2^8
Теперь смотрим: для победы в группе из 256 человек надо 129 своих. Если же эту группу поделить, например на 4 подгруппы, то для победы надо 33*4=132 человека, поэтому такие группы делить невыгодно.
итого имеем 7 разделений на 5 подгрупп где свои должны победить в 3-х из 5. Т.е. своих размещаем только в этих 3-х подгруппах. И 129 человек своих в каждой из самых маленьких подгрупп.
Итого надо 3^7*129 = 282123 своего человека.
Ответ: нельзя

(24) А, они для победы в группе из 256 человек разбили ее на 16 подгрупп по 16 и для победы в каждой подгруппе им потребовалось 9 своих, и для общей победы им надо 9 таких подгрупп. т.е. для выигрыша в группе из 256 человек им надо 9*9=81 своих. И тогда всего надо будет 3^7*81=177147

равные группы это значит делим на каждом шаге на 2 или на 5 или на их комбинацию
20 000 000 = 5^7*2^8
есть 5 отдельно то 2^7/5^7*9^2/16^2
0,0005184
т.е. достаточно 0,05%

0,00885735
есть 5 отдельно то 3^7/5^7*9^2/16^2
хватит
0,9% нужно и 9 туров

(14) >>>К каждому приходит специальный человек, с большим ножичком, крутит им возле яиц и говорит за кого проголосовать.

Не было такого, поклёп.

Если убрать требование равные то достаточно президента и премьерминистра

(30) хз, было, не было...
говорят он прилетал на большом самолете в цветах российского триколора

В итоге то какие это группы будут?

(33) смотри (23) или (24)

Решение не одно, как вы понимаете.


Вот одно из них:
Разобьём избирателей на группы по 5 человек. В 66666 таких групп можно поместить по 3 военных. В результате получится 66666 военных выборщиков из 4 миллионов.
Разобьём эти 4 миллиона выборщиков на группы по 4 человека, поместив в 22222 из них по 3 военных. В результате получится 22222 военных выборщика из миллиона.
Повторяя эти две операции, мы видим, что уменьшая число выборщиков в 20 раз, мы уменьшаем число военных выборщиков в 9 раз. Последовательно получаем 2469 военных выборщиков из 50000, 274 из 2500, 30 из 125. Далее дважды разделив на группы по 5, получим трёх военных выборщиков из пяти, что позволит президенту выиграть.

Демократические выборы - это игры неприкасаемых.

(35) да понятно, что делители "5" и "4" в (23) можно переставлять в любом порядке. Ответ на данную задачу не предполагает "найти все способы", а лишь доказать, что решение существует.

Перем ГСЧ;
Перем Ошибки;

Функция ПравильноеРешение(а,б)
    Возврат "" + а + "*" + б + "=" + (а*б);
КонецФункции

Функция НеПравильноеРешение(а,б)
    Задача = "" + а + "*" + б;
    Решение = Ошибки.Получить(Задача);
    Если Решение = Неопределено Тогда
        Решение = "" + (а*б+1);
        Ошибки.Вставить(Задача, Решение);
    КонецЕсли;
    Возврат Задача + "=" + Решение;
КонецФункции

Ошибки = Новый Соответствие;

ГСЧ = Новый ГенераторСлучайныхЧисел();

КоличествоГолосований = 1000;

//Исходные данные
КоличествоГолосующих = 100;
ОбъемЗнаний = 70;
МинимальныйПроцентПравильныхЗнаний =  30;
МаксимальныйПроцентПравильныхЗнаний = 70;
КоличествоВариантовВыбора = 2;

КоличествоВерноПринятыхРешений = 0;
КоличествоНеВерноПринятыхРешений = 0;
Проголосовало = 0;
ПорогВыбора = 0;

УчастникиГолосования = Новый Массив();

Для н = 0 по КоличествоГолосующих-1 Цикл
    Голосующий = Новый Структура("Знания", Новый Массив());
    Для к = 0 по ОбъемЗнаний-1 Цикл
        ПроцентПравильныхЗнаний = ГСЧ.СлучайноеЧисло(МинимальныйПроцентПравильныхЗнаний, МаксимальныйПроцентПравильныхЗнаний);
        Если ГСЧ.СлучайноеЧисло(1, 100) <= ПроцентПравильныхЗнаний Тогда
            а = Цел(к/10);
            б = к-а*10;
            реш = ПравильноеРешение(а,б);
            Голосующий.Знания.Добавить(реш);
        Иначе
            а = Цел(к/10);
            б = к-а*10;
            реш = НеПравильноеРешение(а,б);
            Голосующий.Знания.Добавить(реш);
        КонецЕсли;
    КонецЦикла;
    УчастникиГолосования.Добавить(Голосующий);
КонецЦикла;

Для г = 1 по КоличествоГолосований Цикл
    
    ВариантыВыбора = Новый Массив;
    ВыбранныеВарианты = Новый Массив;
    Для к = 0 по КоличествоВариантовВыбора-1 Цикл
        а = ГСЧ.СлучайноеЧисло(0, 9);
        б = ГСЧ.СлучайноеЧисло(0, 9);
        ВариантыВыбора.Добавить(НеПравильноеРешение(а,б));
        ВыбранныеВарианты.Добавить(0);
    КонецЦикла;
    ПравильныйВариант = ГСЧ.СлучайноеЧисло(0, КоличествоВариантовВыбора-1);
    ВариантыВыбора[ПравильныйВариант] = ПравильноеРешение(а,б);
    
    Для каждого Голосующий Из УчастникиГолосования Цикл
        Для н = 0 по КоличествоВариантовВыбора-1 Цикл
            Если Голосующий.Знания.Найти(ВариантыВыбора[н]) = Неопределено Тогда
                Продолжить;
            КонецЕсли;
            ВыбранныеВарианты[н]=ВыбранныеВарианты[н]+1;
            Проголосовало = Проголосовало + 1;
            Прервать;
        КонецЦикла;
    КонецЦикла;
        

    ВыбранныйВариантКоличество = 0;
    ВыбранныйВариант = 0;
    
    Для н = 0 по КоличествоВариантовВыбора-1 Цикл
        Если ВыбранныеВарианты[н] > ВыбранныйВариантКоличество Тогда
            ВыбранныйВариантКоличество = ВыбранныеВарианты[н];
            ВыбранныйВариант = н;
        КонецЕсли;
    КонецЦикла;

    ПорогВыбора = ПорогВыбора + ВыбранныйВариантКоличество;

    Если ВыбранныйВариантКоличество > 0 Тогда
        Если ВыбранныйВариант = ПравильныйВариант Тогда
            КоличествоВерноПринятыхРешений = КоличествоВерноПринятыхРешений + 1;
        Иначе
            КоличествоНеВерноПринятыхРешений = КоличествоНеВерноПринятыхРешений + 1;
        КонецЕсли;
    КонецЕсли;

КонецЦикла;

Сообщить("Порог выбора, % " + Цел(100*ПорогВыбора/(КоличествоГолосований*КоличествоГолосующих)));
Сообщить("Вероятность принятия верного решения, % " + Цел(100*КоличествоВерноПринятыхРешений/(КоличествоВерноПринятыхРешений + КоличествоНеВерноПринятыхРешений)));
Сообщить("Проголосовало, % " + Цел(100*Проголосовало/(КоличествоГолосований*КоличествоГолосующих)));

(38) лень проверять. Каков результат?

(39) все время разный. рассчитывает вероятность принятия верного решения голосованием.

1. 100 (всего) из них 51 (вояки)
2. 100*10 = 1000 из них 51*6 = 306
3. 1000*10 = 10 000 из них 306*6 = 1832
4. 10 000*10 = 100 000 из них 1832*6 = 11 016
5. 100 000*10 = 1 000 000 из них 11 016*6 = 66 096
6. 1 000 000*10= 10 000 000 из них 66 096*6 = 396 576

Осталось подобрать требуемый коэффициент k (10 как видим не подходит) чтобы расхождение всего/вояки было максимальным.

Так как в условии "Равных" групп, то для начала нужно 20 000 000 разложить на простые множителя.

Это 2^8*5^7

Виноват, не заметил что выше есть решение.