Вход | Регистрация


Информационные технологии ::

Метки: 

Задача. "Демократические" выборы

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

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

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

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

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

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


Вот одно из них:
Разобьём избирателей на группы по 5 человек. В 66666 таких групп можно поместить по 3 военных. В результате получится 66666 военных выборщиков из 4 миллионов.
Разобьём эти 4 миллиона выборщиков на группы по 4 человека, поместив в 22222 из них по 3 военных. В результате получится 22222 военных выборщика из миллиона.
Повторяя эти две операции, мы видим, что уменьшая число выборщиков в 20 раз, мы уменьшаем число военных выборщиков в 9 раз. Последовательно получаем 2469 военных выборщиков из 50000, 274 из 2500, 30 из 125. Далее дважды разделив на группы по 5, получим трёх военных выборщиков из пяти, что позволит президенту выиграть.
   trdm
 
36 - 19.07.18 - 15:32
Демократические выборы - это игры неприкасаемых.
   RomanYS
 
37 - 19.07.18 - 15:47
(35) да понятно, что делители "5" и "4" в (23) можно переставлять в любом порядке. Ответ на данную задачу не предполагает "найти все способы", а лишь доказать, что решение существует.
   vasvl82
 
38 - 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*Проголосовало/(КоличествоГолосований*КоличествоГолосующих)));
   1Сергей
 
39 - 30.07.18 - 10:43
(38) лень проверять. Каков результат?
   vasvl82
 
40 - 30.07.18 - 13:56
(39) все время разный. рассчитывает вероятность принятия верного решения голосованием.
   Garykom
 
41 - 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 как видим не подходит) чтобы расхождение всего/вояки было максимальным.
   NSSerg
 
42 - 30.07.18 - 14:44
Так как в условии "Равных" групп, то для начала нужно 20 000 000 разложить на простые множителя.
   NSSerg
 
43 - 30.07.18 - 14:45
Это 2^8*5^7
   NSSerg
 
44 - 30.07.18 - 14:47
Виноват, не заметил что выше есть решение.



Список тем форума
Рекламное место пустует  
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует