Имя: Пароль:
IT
 
Задача. "Демократические" выборы
,
0 1Сергей
 
19.07.18
09:52
В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 000 000 избирателей, из которых только один процент (регулярная армия Анчурии) поддерживает Мирафлореса. Он хочет быть демократически избранным.

"Демократическим голосованием" Мирафлорес называет вот что: всех избирателей разбивают на несколько равных групп, затем каждую из этих групп вновь разбивают на некоторое количество равных групп, затем эти последние группы снова разбивают на равные группы и так далее; в самых мелких группах выбирают представителя группы - выборщика, затем выборщики выбирают представителей для голосования в ещё большей группе и так далее; наконец, представители самых больших групп выбирают президента. Мирафлорес сам делит избирателей на группы. Может ли он так организовать выборы, чтобы его избрали президентом? (В каждой группе выборщики выбирают своего представителя простым большинством. При равенстве голосов побеждает оппозиция.)
1 Xapac
 
19.07.18
09:59
можно я буду рассматривать 200 населения и 2 человека армия?
2 Eiffil123
 
19.07.18
09:59
Прям как в США, там тоже выборщики.
3 RomanYS
 
19.07.18
10:01
(0) можно
(1) можно, но ответ тогда будет "нельзя"
4 butterbean
 
19.07.18
10:14
делим сначала на 25 групп по 800,000, нам нужны голоса только 13 групп, поэтому остается 13 групп по 800,000 = 10,400,000
потом делим опять каждую группу на 25, уже по 32,000
потом опять по 25
потом по 25 уже не делится, делим по 13, потом еще раз по 13 и остается меньше миллиона тех, чьи голоса нужны, т.е. армии хватит
5 Asmody
 
19.07.18
10:14
Где-то у меня были конспекты по "Теории игр"...
6 RomanYS
 
19.07.18
10:25
*(3) ответ похоже всё-таки нельзя. При населении 25 млн было бы можно.
И такой ответ (входные условия) как-то обесценивает задачу в контексте данной ветки)
7 RomanYS
 
19.07.18
10:26
(4) "делим по 13" это невозможно, по условию группы равные
8 butterbean
 
19.07.18
10:30
(7) они будут равные
9 torgm
 
19.07.18
10:35
(1)  при этом раскладе нельзя,

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

,
10 RomanYS
 
19.07.18
10:38
(8) 20 000 000 не делится на 13
11 Xapac
 
19.07.18
10:44
(4) 25 - подбором взял?
12 RomanYS
 
19.07.18
10:48
(11) делить надо на 5, тогда для победы надо
3 из 5,
9 из 25,
27 из 125,
81 / 625,
243 / 3125,
729 / 1562
...
3^n / 5^n
13 Xapac
 
19.07.18
10:54
то есть решаем уравнение
3^n / 5^n = <Количество всего>/100*<Количество в процентах за>

3^n / 5^n = 200 000
14 Oftan_Idy
 
19.07.18
10:56
Легко. В США как раз так.
Пофигу как там делить или умножать.
В результате у тебя получается всего пара десятков выборщиков которые выбирают президента.
Они же люди, у них кровь течет, это всего 20 человечков. К каждому приходит специальный человек, с большим ножичком, крутит им возле яиц и говорит за кого проголосовать.
На следующий день 19 человек голосуют за президента. 19, потому что всегда найдется один придурок который считает что перехитрит всех. Он потом подавится оливкой в ресторане и сдохнет.
16 Salimbek
 
19.07.18
10:58
(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
17 RomanYS
 
19.07.18
11:02
(16) 20 000 000 не делится на 3
18 Salimbek
 
19.07.18
11:02
(13) Вообще-то получаем 5^n=20 000 000 и 3^n = 200 000,
19 Salimbek
 
19.07.18
11:03
(17) Ну я так, абстрактно считал )))
20 RomanYS
 
19.07.18
11:06
(6) отзывается. Ответ: можно.
21 Salimbek
 
19.07.18
11:10
Получается такая система: (Ч-числитель З - знаменатель) Л - последняя, самая маленькая группа человек.
1) Ч%2=1 (Ч - нечетное)
2) Ч^n*Л=20 000 000
3) З = Ч/2+0.5
4) З^n*(Л/2+1) < 200 000
Так?
22 Salimbek
 
19.07.18
11:11
Блин, Ч и З местами перепутал...
1) З%2=1 (Ч - нечетное)
2) З^n*Л=20 000 000
3) Ч = З/2+0.5
4) Ч^n*(Л/2+1) < 200 000
23 RomanYS
 
19.07.18
11:15
24 Ненавижу 1С
 
гуру
19.07.18
11:17
25 RomanYS
 
19.07.18
11:22
(24) забавна оговорка в 1970-м году
"Кстати, по такой системе голосуют во многих капиталистических странах."
26 Salimbek
 
19.07.18
11:22
20000000=5^7*2^8
Теперь смотрим: для победы в группе из 256 человек надо 129 своих. Если же эту группу поделить, например на 4 подгруппы, то для победы надо 33*4=132 человека, поэтому такие группы делить невыгодно.
итого имеем 7 разделений на 5 подгрупп где свои должны победить в 3-х из 5. Т.е. своих размещаем только в этих 3-х подгруппах. И 129 человек своих в каждой из самых маленьких подгрупп.
Итого надо 3^7*129 = 282123 своего человека.
Ответ: нельзя
27 Salimbek
 
19.07.18
11:37
(24) А, они для победы в группе из 256 человек разбили ее на 16 подгрупп по 16 и для победы в каждой подгруппе им потребовалось 9 своих, и для общей победы им надо 9 таких подгрупп. т.е. для выигрыша в группе из 256 человек им надо 9*9=81 своих. И тогда всего надо будет 3^7*81=177147
28 ERWINS
 
19.07.18
11:57
равные группы это значит делим на каждом шаге на 2 или на 5 или на их комбинацию
20 000 000 = 5^7*2^8
есть 5 отдельно то 2^7/5^7*9^2/16^2
0,0005184
т.е. достаточно 0,05%
29 ERWINS
 
19.07.18
12:00
0,00885735
есть 5 отдельно то 3^7/5^7*9^2/16^2
хватит
0,9% нужно и 9 туров
30 JeHer
 
19.07.18
12:21
(14) >>>К каждому приходит специальный человек, с большим ножичком, крутит им возле яиц и говорит за кого проголосовать.

Не было такого, поклёп.
31 ERWINS
 
19.07.18
12:25
Если убрать требование равные то достаточно президента и премьерминистра
32 RomanYS
 
19.07.18
12:31
(30) хз, было, не было...
говорят он прилетал на большом самолете в цветах российского триколора
33 Eiffil123
 
19.07.18
15:10
В итоге то какие это группы будут?
34 RomanYS
 
19.07.18
15:11
(33) смотри (23) или (24)
35 1Сергей
 
19.07.18
15:14
Решение не одно, как вы понимаете.


Вот одно из них:
Разобьём избирателей на группы по 5 человек. В 66666 таких групп можно поместить по 3 военных. В результате получится 66666 военных выборщиков из 4 миллионов.
Разобьём эти 4 миллиона выборщиков на группы по 4 человека, поместив в 22222 из них по 3 военных. В результате получится 22222 военных выборщика из миллиона.
Повторяя эти две операции, мы видим, что уменьшая число выборщиков в 20 раз, мы уменьшаем число военных выборщиков в 9 раз. Последовательно получаем 2469 военных выборщиков из 50000, 274 из 2500, 30 из 125. Далее дважды разделив на группы по 5, получим трёх военных выборщиков из пяти, что позволит президенту выиграть.
36 trdm
 
19.07.18
15:32
Демократические выборы - это игры неприкасаемых.
37 RomanYS
 
19.07.18
15:47
(35) да понятно, что делители "5" и "4" в (23) можно переставлять в любом порядке. Ответ на данную задачу не предполагает "найти все способы", а лишь доказать, что решение существует.
38 vasvl82
 
30.07.18
10:19
Перем ГСЧ;
Перем Ошибки;

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

Функция НеПравильноеРешение(а,б)
    Задача = "" + а + "*" + б;
    Решение = Ошибки.Получить(Задача);
    Если Решение = Неопределено Тогда
        Решение = "" + (а*б+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*Проголосовало/(КоличествоГолосований*КоличествоГолосующих)));
39 1Сергей
 
30.07.18
10:43
(38) лень проверять. Каков результат?
40 vasvl82
 
30.07.18
13:56
(39) все время разный. рассчитывает вероятность принятия верного решения голосованием.
41 Garykom
 
гуру
30.07.18
14:27
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 как видим не подходит) чтобы расхождение всего/вояки было максимальным.
42 NSSerg
 
30.07.18
14:44
Так как в условии "Равных" групп, то для начала нужно 20 000 000 разложить на простые множителя.
43 NSSerg
 
30.07.18
14:45
Это 2^8*5^7
44 NSSerg
 
30.07.18
14:47
Виноват, не заметил что выше есть решение.