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