Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Докажите, что количество различных выражений, описывающих очереди для голосования (любой длины), которые можно составить при помощи предикатов "за", "против" и "рядом", двух переменных x и y, кванторов и логических связок, не превышает 2 218+15 . (Выражения считаются одинаковыми, если для каждой очереди их значения совпадают).
Вы можете пользоваться манипулятором, но оцениваться будет только текст решения.
Манипулятор позволяет создавать в том числе картинки, не являющиеся очередями. Их не надо учитывать и использовать при решении задачи.
Количество различных выражений, описывающих очереди для голосования не превышает 2^(2^18+15), так как каждое может содержать лишь ряд проверок: 1. ЗА/ПРОТИВ(y/х) (проверяются однобитные значения для отдельных "голосующих") 2. СОСЕД(x,y) (Существуют всего 2 переменных, так что изменение аргументов бессмысленно) Комбинируя эти 2 предиката, различные кванторы и логические операции, мы можем составить 2n различных выражений, но n не может превышать 2^17, т.к мы оперируем лишь с 3 значениями (ЗА(x) всегда противоположно ПРОТИВ(x) и новой информации в случае использования "ПРОТИВ(х)" не несёт).