Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.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) элементов обоих типов.