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