Клетчатые задачи и комбинаторные подсчёты на СПБГУ

Если зрители расселись на рядов, то на каком-то ряду оказалось не менее зрителей (в противном случае на каждом ряду не более зрителей, а всего их тогда не более ). Так как нельзя рассадить зрителей этого ряда после антракта так, чтобы в каждом ряду их оказалось не более трех. Таким образом, нас устраивает.

Покажем теперь, что при наличии рядов зрителей можно рассадить так, чтобы нужных четырех зрителей не нашлось. Назовем -й колонкой места в зале с номером циклически упорядоченные по рядам:

Пусть циклический сдвиг колонки на рядов — перестановка колонки, при которой новый номер ряда каждого зрителя получается из старого сдвигом на позиций вправо в последовательности Заполним зрителями колонки с номерами от по а также первые мест -й колонки. Таким образом, в зале окажется человек. После антракта мы рассадим зрителей следующим образом. Зрители колонок садятся на свои места; в колонках зрители циклически сдвигаются на один ряд, в колонках — на два ряда, и так далее. В результате мы получим ситуацию, когда нет четырех зрителей, сидевших на одном ряду и до, и после антракта.