ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78719
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Теория алгоритмов (прочее) ]
[ Разбиения на пары и группы; биекции ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

Сможет.

Замечания

1. Порядок, в котором мы делили выборщиков на группы по 5 или 4 человека, разумеется, неважен.

2. В решениях задачника "Кванта" ("Квант", 1970, №7) обсуждаются обобщения этой задачи.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1970
выпуск
Номер 1
Задача
Номер М1
олимпиада
Название Московская математическая олимпиада
год
Номер 32
Год 1969
вариант
Класс 9
Тур 2
задача
Номер 4
Кружок
Название ВМШ 57 школы
класс
Класс 7
год
Год 1999/00
Место проведения 57 школа
занятие
Номер 13
Название Проценты
Тема Дроби
задача
Номер 05

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .