Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Докажите, что 2n элементов И и ИЛИ достаточно, чтобы построить автомат для голосования n человек (n – нечётное).
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Допустим, n=2k+1, k -- натуральное число. Тогда на выходе схемы должна быть 1, если на (k+1) входах имеется единица. Все случаи, когда единица находится более, чем на (k+1) входах, можно не рассматривать, они входят в те, где единица строго на (k+1) входах. Всего возможно С комбинаций, где С -- количество размещений из (2k+1) по (k+1), C=(2k+1)*(2k)*(2k-1)*...*(k+2) Из предыдущего номера ясно, что выходы C маленьких схем (проверяющих одну комбинацию каждая) необходимо подключить через элементы ИЛИ на общий выход. Это можно сделать так: Разбить все C комбинаций попарно, каждую пару соединить элементом ИЛИ. Выходы всех элементов ИЛИ разбить по парам и соединить. Повторять до тех пор, пока не останется один элемент ИЛИ, выход которого подключаем к общему выходу схемы. Оценим количество элементов ИЛИ: C/2 -- для соединения разбитых по парам C выходов комбинаций. C/4 - для соединения элементов ИЛИ, полученных на предыдущем шаге C/8 - для соединения элементов ИЛИ, полученных на предыдущем шаге C/16 - ... Получаем бесконечную геометрическую прогрессию, ее сумма -- 1, то есть необходимо C элементов ИЛИ. Рассмотрим схему, проверяющую каждую отдельную комбинацию. Разобьем (k+1) вход на пары, соединим эти пары элементами И (причем один вход может быть без пары, его подключим в самом конце) -- (k+1)/2 элементов Для соединения выходов элементов И, полученных на предыдущем шаге -- еще (k+1)/4 элементов И, и так далее. Всего не более (k+1)+1=k+2~=n/2 элементов И. То есть, всего необходимо не более A=((k+2)+C)=(k+2)((2k+1)*(2k)*(2k-1)*...*(k+3) + 1) элементов обоих типов.