3.1 (8 баллов). На совместной конференции партий лжецов и правдолюбов в президиум было избрано 32 человека, которых рассадили в четыре ряда по 8 человек. В перерыве каждый член президиума заявил, что среди его соседей есть представители обеих партий. Известно, что лжецы всегда лгут, а правдолюбцы всегда говорят правду. При каком наименьшем числе лжецов в президиуме возможна описанная ситуация? (Два члена президиума являются соседями, если один из них сидит слева, справа, спереди или сзади от другого.)

Чтобы высказывание было истинным, у человека должны быть среди соседей и лжец, и правдолюбец. Значит, каждый правдолюбец обязан иметь соседей обеих партий. Лжец же не может иметь соседей обеих партий: тогда его высказывание было бы истинным. Следовательно, у каждого лжеца среди соседей могут быть только лжецы или только правдолюбцы.

Однако для точного минимума нужно учитывать, как именно образуют соседство четыре ряда: в условии не сказано, замкнуты ли ряды по краям и считаются ли соседями люди из разных рядов напротив друг друга. При обычной прямоугольной рассадке 4×8 без соседства через края задача имеет конкретный ответ, но его обоснование требует отдельного комбинаторного перебора.