С середины XVIII веке, когда Леонард Эйлер первым проанализировал свойства латинских квадратов, в течение длительного времени убегали они за объекты более развлекательные, чем чисто математические. Только в начале XX века их значение в науке, а также прикладной, она начала расти, что привело к публикации Dénesa и Keedwella1. В XXI веке, благодаря, в основном, судоку, квадраты латинские снова доминируют в качестве развлечения, что также можно считать их практическое применение.

Напомним, что речь идет о квадраты делятся на n2 решетки (n×n), в которые внесены числа от 1 до n – очень редко больше 9 – так, что в каждой строке и в каждом столбце существует n различных чисел. В логических квестах в начале так называемой частично квадратами (цифры внесены только в некоторые поля), а решение заключается в заполнении всех пустых полей. Для того, чтобы появилась загадка, например, такой, как на рис. 1a, не требуется никаких дополнительных условий, но с ними весело, гораздо привлекательнее, чем она. Самый простой заключается в том, чтобы цифры по диагонали, также были разные – этого достаточно для создания интересных и сложных задач (например, рис. 1b). Почти как простое условие действует в судоку (различных цифр в девяти секторов 3 х 3). Данная статья применима к состоянии, который выделяется оригинальностью и математическим аспектом и является основой заданий популярны уже более 20 лет.

В 1992 году Masanori Natsuhara, учитель математики из Осаки, он отметил, что ключом к заливки латинского квадрата может быть умная информация, указанная рядом схемы. Это позволило, предназначенную первоначально для студентов остроумное головоломка „строительную”, целью которой является воссоздание внешнего вида микрорайона, состоящего из n2 пеналов блоков, установленных в квадрат n×n. Каждый блок-это куб или „небоскреб” из одинаковых кубиков, как этажность, количество которых определяет высоту блока. В каждой строке и в каждом столбце стоит n блоков разной высоты – от 1 до n. Для n=4 яма может выглядеть так, как на рис. 2а. Если на крыше каждого блока мы поставим цифры, обозначающие высоту и посмотреть сверху на всю застройку, то появится латинский квадрат (рис. 2b). Числа со стрелками вокруг диаграммы-это полная информация важна и гвоздь идеи японского учителя:

каждое число означает, сколько блоков в ряд, видно, хотя бы частично, с места, в котором дана количество находится, глядя в соответствии с указанием стрелки (не увидим никакого нижнего блока, стоящего за выше).

После удаления цифр с крыш получилась бы, так что загадка с полной информацией, однако, как правило, вы также можете удалить большинство чисел со стрелками. На рис. 2b достаточно оставить только четыре (рис. 2c), а решение будет однозначным – пожалуйста, проверьте.

Строительная головоломка быстро стала популярной в Японии, а в конце XX века уже была известна в мире под различными названиями, чаще всего как в самом центре коммерческого центра (в россии яма или небоскребы). Возникло множество его разновидностей, а два года назад появилась привлекательная графически версия для ipad и iPhone – Skyline. Стоит присмотреться одному аспекту matematycznemu небоскребов, который связывается с комбинаторика.

Каждый ряд n блоков n различных высотах является permutację цифр от 1 до n. Каждая цифра со стрелкой рядом ряд – эти цифры в целом мы назовем индикаторами – определяет, сколько цифр, перестановки создает самую длинную подстроку на подъеме, начинающийся с цифры на берегу схема (часто подстрока ограничивается одной или двух цифр). Показатели должны содержать между 1 и n, а сумма двух показателей на концах этого же ряда не может быть меньше 3 и больше, чем n+1. Для крайних значений легко определить зависимость между этой суммой и число перестановок, т. е. возможных настроек небоскребов в ряд. Если сумма минимальная, то на концах ряда являются индикаторы 1 и 2, а так два высших блоки ограничивают правительство, а между ними находятся n-2 блоки, установленные на один из (n-2)! способами. Если сумма является максимальным, после этого на концах ряда являются показатели L (слева) и P=n+1–L (справа), однозначно определяющие положение самого высокого здания, крыши, а оставшиеся образуют одно- (для L или P , равного 1) или двустороннюю „лестницы”, в общем, будет так возможных настроек. Подсчет перестановок для общего случае требуется немного другой подход – начинать нужно с более простой ситуации, когда указан только один показатель, например L с левой стороны ряда. Если нижний блок находит на левом краю, то остальные будут расположены так, чтобы показать было L-1 блоков. А если будет где-нибудь в другом месте, то есть на одном из n-1 дополнительных мест, то расположение остальных будет таковой, чтобы можно было разглядеть L блоков. Отсюда вытекает формула rekurencyjny на функцию f(n,L), определяющий количество перестановок n блоков в зависимости от L:

f(n,L) = f(n-1,L-1)+(n-1)f(n-1,L)

Для небольших n и L легко проверить, что f(1,1)=f(2,1)=1, и, кроме того, f(n,n)=1 и f(n,k)=0, когда k>n. Оказывается, что такая же картина rekurencyjny, с одинаковыми начальными условиями, определяет так наз. числа Стирлинга первого рода. Их основная определение связано с другим вопросом kombinatorycznym: числа Стирлинга первого рода s(n,c) определить, сколькими способами можно разместить n чисел в c циклах. Или иначе: сколько различных групп циклов, после c циклов в каждой группе, если каждая группа содержит ровно n чисел – все от 1 до n.

Например, четыре цифры – 1, 2, 3, 4 – образуют 24 различные циклы: (1), (2), (3), (4), (12), (13), (14), (23), (24), (34), (123), (132), (124), (142), (134), (143), (234), (243), (1234), (1243), (1324), (1342), (1423), (1432). Каждый цикл, можно сохранить как циклический строку, например (123)→12312312.. – содержатся в нем также циклы (231) и (312), поэтому считается, что они тождественны с (123), так что среди указанных 24 различных были опущены.

Если мы будем создавать równoliczne группы циклов, например, после 2 циклов (4 разные цифры) в каждой группе, то всех различных групп восстание 11, т. е. s(4,2)=11: а–(1)(234), b–(1)(243), c–(2)(134), d–(2)(143), электронной(3)(124), f–(3)(142), г–(4)(123), h–(4)(132)–(12)(34), j–(13)(24), k–(14)(23). Схемах аналогом этих групп является 11 способов настройки в ряду n=4 многоэтажки (рис. 3), расположенной с левой стороны, показатель L=2 (буквы в строках и в тексте выше при циклах связаны с первым из конкурсных задач, приведенных в конце статьи).

Блочные числа Стирлинга первого рода являются функцией двух переменных – n и Ln; их значения образуют треугольную таблицу (рис. 4). Вытекает из нее, например, что если рядом ряд, 6 блоков с левой стороны находится индикатор Л=4, то блоки могут быть расположены на 85 способов. Способов, конечно, будет меньше, после добавления справа от указателя Р. Сколько?

Если P=1, то перестановка столько же, что и для короткого на одну клетку порядка без этой единицы, т. е. gn(L,1)=f(n-1,L-1). В приведенном выше примере число способов уменьшится из f(6,4)=85 к f(5,3)=35.

Если ни Л, ни Р не равно 1, это самый высокий блок высотой n, который может находиться в одном из nLP+2 k (LknP+1), делит ряд на две части (блок n не принадлежит ни к одной из них): левой длиной k-1 с индексом L-1 слева и справа с длиной nk с индексом P-1 справа.

Разрывы ряд для n=6, Л=4 и P=2 (две позиции k) представлены на рис. 5. Каждая часть имеет индикатор только с одной стороны, что напоминает ситуацию, упомянутый ранее, однако на этот раз выбор блоков для размещения в любой части больше количества полей. Левая часть состоит из k-1 полей, права с nk, а можно выбрать один из n-1 блоков на высоте от 1 до n-1. Вместо перестановки появляются, поэтому комбинации. Как справиться с ними?

Считываем из таблицы значение числа Стирлинга для любой части, например, для левой – sl, а затем мы вычисляем для этой части количество комбинаций h(s), которая столько раз больше числа Стирлинга, сколько комбинаций q-elementowych с n-1 элементов (q – количество полей, образующих данную часть), т. е. h(sl)=. Каждой из этих комбинаций соответствует sP перестановки из оставшихся n-1-q чисел в правой части и, следовательно, h(sl) следует умножить на sp. Результат будет общее число перестановок для двух частей, для данного k. Общее количество способов установки блоков в ряд gn(L,P) равна общей сложности перестановки для всех k. Для ряда рис. 5 – n=6, L=4, P=2, k1=4 (q=3), k2=5 (q=4) – выражается формулой:

Из таблицы (рис. 4) следует, что когда указатель находится только с одной стороны, это можно больше способов заполнения ряда блоками всегда для показателя равного 2. Если же индикаторы находятся с двух сторон, то для типичных длин рядов в башнях (от 4 до 8) максимальное количество перестановок там для двух двоек или двойки и тройки: г4(2,2)=6, g5(2,2)=22, г,6(2,3)=105, g —7(2,3)=675, г,8(2,3)=4872.

ЗАДАЧИ

  • 1. Ряда блоков на рис. 3 обозначены большими буквами, а соответствующие им пары циклов – строчными буквами в тексте. Однако, такие же буквы не означают соответствующих объектов. Пожалуйста, в соответствии с каждой пары циклов для соответствующего ему ряда блоков из рис. 3, то есть, соответственно, объединить в пары, маленькие и большие буквы.
  • 2. Небоскребы с дополнительным условием: числа должны быть разные и в каждом секторе, окруженном красной линии (рис. 6). Решение это неоднозначное, потому что на берегу ни одного указателя – двойки. В каком месте следует ее поместить, чтобы было одно решение?

    3. Показатели зашифрованы буквами – таким же показателям соответствуют одинаковые буквы, а разным – разные (рис. 7). В решении достаточно указать сумму цифрами на диагонали.

    Решения просим присылать до 31 марта текущего года по электронной почте ([email protected]), указав в теме письма пароль UG03/14, или по почте: Мир Науки, ул. по улице rzymowskiego проходят 28, 02-697 Warszawa. Среди отправителей правильных решений, по крайней мере, двух задач финале будут выбраны пять победителей, и мы награждаем их книгой , Откуда он взялся кот Шредингера Джона Gribbina, ufundowaną издательством Prószyński Сми.

    1 Ю. Dénes, A. D. Keedwell, Latin Squares and their Applications, Academic Press, 1974.

    Решение задач с январского номера

    1. Решение примеры: 77, 49, 36, 18, 9, -9. Каждый даже слово за меньше предыдущей на podwojoną сумму его цифр, а каждый нечетный – сумму цифр. Таким образом, шестой выражением строки 9 – 2*9 = -9.

    2. 1359→135→15→5.

    3. 789→504, 123→6.

    За правильное решение как минимум двух задач, награды, книги Иена Стюарта, Математика в жизни, ufundowaną издательством Prószyński Сми, получают: Радослав Чая, Михаил Furmaniak с Obrzycka, Диана Jacak с Dwikoz, Михаил Липинский из Кракова, Павел Памула из Вроцлава.