1. В настольной игре есть 3 ряда карточек длины n. На каждой карточке написано одно из трёх заклинаний, и всего каждого заклинания – ровно n штук. Докажите, что можно поменять карточки местами внутри каждого ряда так, чтобы в каждом столбце оказались все три разные заклинания.

Решение:

Данная задача является комбинаторной. По условию у нас есть 3 ряда карточек, каждый ряд имеет длину \( n \). Всего есть 3 вида заклинаний, и каждого заклинания по \( n \) штук. Это означает, что в каждом ряду карточки содержат все три вида заклинаний, и причём ровно \( n \) раз встречается каждое заклинание, если смотреть по рядам. Но задача требует, чтобы в каждом столбце оказались все три разные заклинания.

Доказательство:

Рассмотрим пример для \( n = 3 \). У нас есть 3 ряда по 3 карточки. Всего 9 карточек, по 3 каждого заклинания (назовем их A, B, C).

Исходное расположение карточек в рядах может быть таким:

Ряд 1: A B C

Ряд 2: A B C

Ряд 3: A B C

В таком случае столбцы выглядят так:

Столбец 1: A, A, A

Столбец 2: B, B, B

Столбец 3: C, C, C

Как видим, в каждом столбце оказались одинаковые заклинания.

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

Построим следующее расположение:

Ряд 1: A B C

Ряд 2: B C A

Ряд 3: C A B

Теперь проверим столбцы:

Столбец 1: A, B, C

Столбец 2: B, C, A

Столбец 3: C, A, B

В каждом столбце теперь находятся три разных заклинания.

Обобщение для любого \( n \):

Мы можем использовать принцип построения латинских квадратов. Для \( n \) заклинаний и \( n \) рядов, мы можем составить такую таблицу:

Пусть заклинания пронумерованы от 0 до \( n-1 \). Карточка в \( i \)-ом ряду и \( j \)-ом столбце (где \( i, j \) от 0 до \( n-1 \)) может иметь заклинание, равное \( (i+j) n \) (операция взятия остатка от деления).

Формально, элемент в позиции \( (i, j) \) (строка \( i \), столбец \( j \)) будет иметь заклинание \( S_{i,j} \).

Мы можем расположить карточки следующим образом:

• Ряд 0: \( 0, 1, 2, ..., n-1 \)
• Ряд 1: \( 1, 2, 3, ..., 0 \)
• Ряд 2: \( 2, 3, 4, ..., 1 \)
• ...
• Ряд \( n-1 \): \( n-1, 0, 1, ..., n-2 \)

Это соответствует построению латинского квадрата.

Рассмотрим \( i \)-ый ряд. Он содержит последовательность \( i, i+1, n, i+2, n, …, i+n-1, n \). Так как \( n \) чисел, и мы берем остаток от деления на \( n \), то в каждом ряду будут представлены все числа от 0 до \( n-1 \) ровно по одному разу.

Рассмотрим \( j \)-ый столбец. Его элементы будут \( S_{0,j}, S_{1,j}, …, S_{n-1,j} \). Где \( S_{i,j} = (i+j) n \).

Для фиксированного \( j \), рассмотрим элементы \( (0+j) n, (1+j) n, …, (n-1+j) n \). Каждое из этих выражений \( (i+j) n \) для \( i = 0, 1, …, n-1 \) примет все значения от 0 до \( n-1 \) ровно один раз. Это значит, что в каждом столбце будут присутствовать все три (или \( n \) в общем случае) разные заклинания.

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

Доказано.