Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Докажите, что 2n элементов И и ИЛИ достаточно, чтобы построить автомат для голосования n человек (n – нечётное).
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Введем функцию f(n), которая будет считать минимальное количество элементов схемы, нужных, для построения схемы для решения задачи с n человек, И будем ее сравнивать с показательной функцией 2^n. f(1) = 0, так как для одного элемента нам не нужны элементы "И" и "ИЛИ". 2^1 = 2 f(3) = 4, так как решением будет формула y(x+z)+xz, тут всего 4 операции. 2^3 = 8 f(5) = 17, так как решением будет формула ab(c+d+e)+ac(d+e)+bc(d+e)+de(a+b+c). 2^5 = 32 Функции f(n) и 2^n обе представлены на координатной плоскости в виде парабол, чьи ветки направленны вверх. Но сравнив значения в трех точках (1, 3 и 5), мы видим, что функция 2^n возрастает намного быстрее. Из чего следует вывод, что 2^n элементов всегда будет достаточно для схемы