Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Докажите, что 2n элементов И и ИЛИ достаточно, чтобы построить автомат для голосования n человек (n – нечётное).
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Всего n=2m+1 входов. Разобьем их на все возможные наборы из m+1 входа. Посмотрим сколько "И" нужно для определения являются ли все эл-ты из набора из m+1 эл-та единицами. Будем разбивать на пары из различных эл-ов и брать для них "И" таким образом в первом разбиении будет (m+1)/2 "И". Снова разобьем, и снова. Будем так делать пока не останется 1 выход. Кол-во таких "И" равно m. Всего наборов (2m+1)*(2m)*(2m-1)...*m/(m+1)!. Т.е. (C из 2m+1 по m+1) * m и еще нужно (столько-же)-1 "ИЛИ". Итого всего (C из 2m+1 по m+1) * m +(C из 2m+1 по m+1)-1=(C из 2m+1 по m+1)(m+1)-1.