Архив задач олимпиады по математике и криптографии
Латинский квадрат
Пусть – число, стоящее в строке с номером i и столбце с номером j квадратной таблицы А (табл. 6). По таблице А построена таблица В, в строке с номером i и столбце с номером j которой стоит выражение . Набор из десяти клеток таблицы будем называть «правильным», если в нем присутствуют ровно по одной клетке из каждого столбца и каждой строки. Вычисляются произведения элементов, входящих в правильные наборы. Результатом являются выражения вида . Найдите наибольшую возможную степень правильного набора (число n) и число правильных наборов степени 1023.
Наибольшая возможная степень правильного набора получается при перемножении элементов, стоящих в таблице B на местах, соответствующих местам в таблице A, которые в табл. 6 выделены жирным шрифтом. Поэтому наибольшая степень равна .
Табл. 6
5
6
7
8
0
0
0
0
0
0
6
5
8
7
0
0
0
0
0
0
7
8
5
6
0
0
0
0
0
0
8
7
6
5
0
0
0
0
0
0
0
0
0
0
9
0
1
0
0
0
0
0
0
0
0
1
9
0
0
0
0
0
0
0
1
9
0
0
0
0
0
0
0
0
0
0
0
2
3
4
0
0
0
0
0
0
0
3
4
2
0
0
0
0
0
0
0
4
2
3
Чтобы решить вторую часть задачи, заметим, что верно следующее:
Отсюда следует, что искомый коэффициент равен числу таких наборов по 10 элементов, стоящих в различных строках и столбцах в табл. 6, в которых каждое число от 0 до 9 встречается по одному разу. Любой такой набор распадается на 3 набора: набор с числами 2, 3, 4 в нижнем правом квадрате, набор с числами 0, 1, 9 в центральном квадрате и набор с числами 5, 6, 7, 8 в верхнем левом квадрате. Непосредственной проверкой убеждаемся в том, что в каждом из указанных квадратов соответственно имеется 3, 3 и 8 таких наборов, следовательно, общее число наборов равно 3*3*8 = 72.