Последние новости
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-1 элементов И. После этого дизъюнкта стоит элемент ИЛИ. Получается n элементов. Количество следующих дизъюнктов равно n-1. Эти дизъюнкты отвечают за перебор всех вариантов, когда голосуют больше половины, но не все. Количество элементов в этих дизъюнкатах будет равняться n!/k!(n-k)!)+1.Сумма n-1 и n!/k!(n-k)!)+1 будет меньше или равно 2 в степени n.