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