Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Докажите, что можно построить автомат для голосования любого нечётного числа человек, используя только элементы голосования для трёх человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Используем наш автомат для 1ых трёх человек. Получаем на выходе один логический элемент. дальше соединяем полученный логический элемент с 2мя следующими людьми(если оные не закончились). Всё это приведёт к одному выходу, который и будет являться ответом. Данное решение будет верно для любого нечётного числа человек. Представим ряд нечётных чисел. Очевидно, что соседи в ряду при вычитании дают нам двойку. Это и есть те 2 человека, которые соединяются с логическим выходом машины. Чтобы было понятнее, абстрагируемся и представим, что мы на выборах, куда точно придёт нечётное число человек. Вначале запустили троих, дальше пускают только парами(так мы добьёмся любого нечётного числа). Изначально в машину поместили троих человек, а дальше двое новоприбывших совмещают свои голоса с выходом машины и так далее. Доказано