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