Ortogonalita obyčejných čtverců
Úloha číslo: 3727
Obyčejný čtverec řádu \(n\) je matice \(n \times n\) s prvky z množiny \(\{1{,}2,\ldots,n\}\).
Ortogonalita obyčejných čtverců je definována stejně jako pro latinské čtverce (t.j. \(A\) je kolmý na \(B\) právě tehdy, když \((a_{ij},b_{ij})=(a_{k\ell},b_{k\ell}) \Rightarrow (i,j)=(k,\ell)\)).
Dokažte, že existuje množina \(t\) navzájem po dvou ortogonálních latinských čtverců řádu \(n\) právě tehdy, když existuje množina \(t+2\) navzájem ortogonálních obyčejných čtverců řádu \(n\).
Nápověda
Nalezněte transformace, jež jednu množinu čtverců převedou na druhou.
Řešení
Máme-li \(t\) navzájem po dvou ortogonálních latinských čtverců, potom přidáním čtverce s konstantními řádky a čtverce s konstantními sloupci dostaneme \(t+2\) obyčejných čtverců.
Nově přidané jsou ortogonální navzájem – pro předepsanou dvojici symbolů je pozice řádku určená z prvně přidaného a pozice sloupce z druhého.
Čtverec s konstantními řádky je ortogonální i k latinským čtvercům – pro předepsanou dvojici symbolů je pozice řádku určená z přidaného a v latinském čtverci se v tomto řádku každý symbol vyskytuje právě jednou.
Ortogonalita druhého přidaného čtverce se dokáža stejným způsobem, jen namísto řádků se použijí sloupce.
Pro opačnou implikaci je třeba čtverce transformovat na sadu tyto dva obsahující. Pokud na všech \(n^2\) políčcích obyčejného čtverce použijeme nějakou permutaci, dostaneme opět obyčejný čtverec. Navíc, pokud použijeme stejnou permutaci na všech čtvercích, zachová se i vzájemná ortogonalita.
Nyní zbývá nalézt permutaci takovou, aby jeden ze čtverců měl konstantní řádky a druhý konstantní sloupce. Ortogonalita k těmto dvěma znamená, že se neopakují symboly ani v řádku, ani v sloupci.
