Летней Математической Школы, проходившей 11-25 июня 2011 года под Костромой. Всодержание лекционных занятий изложено в опре­де­­лениях, задача

Вид материала

Задача

Содержание Латинские и магические квадраты Построение пары ортогональных квадратов p

Подобный материал:

• Отчет о Летней Школе пул ап день 29 июня, 77.18kb.
• Русской Онтологической Школы в г. Новосибирске, 13-17 июля 2011 года, в том числе лекции, 643.67kb.
• Программа VIII международной летней школы по русской литературе на Карельском перешейке, 53.89kb.
• Вторая- организация профильного обучения в школе, 1770.94kb.
• Конкурс на участие в летней школе " Права человека и медицина", 56.38kb.
• Г. Орел 29 июня 2011 года На основании плана работы Контрольно-счетной палаты, 316.4kb.
• Основная образовательная программа начального общего образования г. Пермь, 2011, 2132.92kb.
• Расписание занятий для студентов, 56.4kb.
• М к. Аммосова Педагогический институт Рабочая программа, 114.38kb.
• Пресс-обзор рынка недвижимости с 22 июня по 28 июня 2011 года, 1403.06kb.

Латинские и магические квадраты

• Латинский¹ квадрат — таблица n  n, заполненная числами от 1 до n так, что в любой строке, в любом столбце и в любой (в том числе, разбитой) диагонали встречаются все числа от 1 до n.
  

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

18. Найдите латинские квадраты 3  3 и 4  4.
    

• Магический² квадрат — таблица n  n, заполненная числами от 1 до n² так, суммы чисел во всех ее строках, столбцах и в двух диагоналях одинаковы.
  

19. Найдите магический квадрат 3  3 и докажите его единственность.
    

• Даны два латинских квадрата a_ij и b_ij размера n  n.
  Составим таблицу (a_ij; b_ij), заполненную парами чисел.
  Такая таблица называется греко-латинским³ квадратом, если все пары различны. В этом случае латинские квадраты называют ортогональными.
  

20. Построение магического квадрата 4  4.
    (а) Найдите два ортогональных латинских квадрата 4  4.
    (б) Постройте греко-латинский квадрат 4  4.
    (в) Замените в каждой ячейке греко-латинского квадрата пару (a_ij; b_ij) числом a_ij + 4b_ij. Докажите, что результат — магический квадрат 4  4.
    (г) Найдите четверки чисел магического квадрата 4  4, суммы в которых равны сумме чисел в строках и столбцах.
    
21. Докажите, что, имея пару ортогональных латинских квадратов n  n, можно построить магический квадрат n  n.
    

• 00	11	22	33	44	55	66	77	88	99
  12	05	50	86	39	24	73	98	61	47
  23	58	06	60	97	41	35	84	19	72
  34	83	69	07	70	18	52	46	95	21
  45	32	94	71	08	80	29	63	57	16
  56	27	43	15	82	09	90	31	74	68
  67	79	38	54	26	93	01	10	42	85
  78	96	81	49	65	37	14	02	20	53
  89	64	17	92	51	76	48	25	03	30
  91	40	75	28	13	62	87	59	36	04

  Леонард Эйлер высказал гипотезу, что не существует обычного квадрата порядка N, если N — чётное число, не деля­щееся на 4 (то есть 6, 10, 14 и так да­лее). В 1901 гипотеза была подтверж­де­на для N = 6 математиком Гасто­ном Терри. Это было сделано перебо­ром всех возможных вариан­тов квад­ра­та. В 1959 году гипотеза была оп­ро­вергнута Э. Т. Паркером, Р. К. Боусом и С. С. Шрикхер­дом, обнаружив­шими квадрат порядка 10 (не диагональный, см. рисунок справа). После были обнаружены квад­раты 14, 18 и т. д. порядков. Пары диагональ­ных ОЛК 10-го порядка были найдены только в 1992 г. При этом не найдено (к 2009 году) трех попарно ортогональных латинских квадратов порядка 10.
  

22. Построение латинского квадрата p  p.
    Пусть p — простое число, d — остаток при делении на p, не равный 0, 1, p – 1.
    Занумеруем столбцы и строки таблицы числами 0, 1, 2, …, p – 1.
    В каждую ячейку столбца x и строки y запишем остаток, который дает сумма x + dy при делении на p. Получим таблицу L(d).
    (а) Докажите, что в каждом столбце и каждой строке все числа различны.
    (б) Докажите, что координаты ячеек одной диагонали (полной или разбитой) удовлетворяют условию x + y  с (mod p) или x – y  с (mod p).
    (в) Докажите, что в каждой диагонали (полной или разбитой) все числа различны.
    
23. Построение пары ортогональных квадратов p  p.
    Пусть d₁ и d₂ — различные остатки при делении на p, не равные 0, 1, p – 1. Докажите, что латинские квадраты L(d₁) и L(d₂) ортогональны.
    
24. Используя результаты предыдущих задач, постройте магические квадраты 5  5 и 7  7.