Kwadrat grecko-łaciński

{{Dopracować|źródła=20^[1]

↑ 15-09}} Kwadrat grecko-łaciński lub kwadrat Eulera rzędu n {\displaystyle n} nad dwoma n {\displaystyle n} -elementowymi zbiorami S {\displaystyle S} i T {\displaystyle T} – kwadratowa tablica o n {\displaystyle n} wierszach i n {\displaystyle n} kolumnach, zawierająca pary ( s , t ) , {\displaystyle (s,t),} gdzie s ∈ S {\displaystyle s\in S} i t ∈ T , {\displaystyle t\in T,} taka że:
każdy wiersz i każda kolumna zawiera dokładnie jeden raz każdy element z S {\displaystyle S} i dokładnie jeden raz każdy element z T {\displaystyle T} oraz

żadne dwie komórki nie zawierają tej samej pary ( s , t ) {\displaystyle (s,t)}
Autorem koncepcji jest Leonhard Euler, który używał zbiorów:
S = { A , B , C , … } , {\displaystyle S=\{A,B,C,\dots \},} pierwsze n {\displaystyle n} dużych liter z alfabetu łacińskiego,
i
T = { α , β , γ , … } , {\displaystyle T=\{\alpha ,\beta ,\gamma ,\dots \},} pierwsze n {\displaystyle n} małych liter z alfabetu greckiego
Stąd nazwa kwadrat grecko-łaciński. Przykłady poniżej:

Rzędu 3 Rzędu 4 Rzędu 5

Układ samych łacińskich znaków, a także układ samych greckich znaków w kwadracie grecko-łacińskim tworzą kwadrat łaciński. Kwadrat grecko-łaciński może zostać rozłożony na dwa ortogonalne kwadraty łacińskie. Ortogonalność oznacza tu, że każda para ( s , t ) {\displaystyle (s,t)} z iloczynu kartezjańskiego S × T {\displaystyle S\times T} wystąpi dokładnie raz.

Planowanie eksperymentów

Kwadraty grecko-łacińskie mają zastosowanie w planowaniu eksperymentów naukowych. Załóżmy, że mamy maksymalnie 4 nominalne zmienne, którymi możemy wpływać na wynik eksperymentu i każda z nich może przyjmować n {\displaystyle n} wartości. Na przykład w badaniach medycznych zmiennymi mogą być:

podawany lek (jeden z trzech),

stopień nasilenia choroby (niski, średni lub wysoki),

wiek badanego (podzielony na trzy kategorie),

szpital, w którym przeprowadzane jest badanie (jeden z trzech).

Teraz wystarczy ułożyć kwadrat grecko-łaciński rzędu n {\displaystyle n} (tutaj: 3), aby otrzymać plan n 2 {\displaystyle n^{2}} eksperymentów. Każde pole kwadratu odpowiada jednemu z eksperymentów, kolumny to możliwe wartości pierwszej zmiennej, wiersze – drugiej zmiennej, litery łacińskie odpowiadają trzeciej zmiennej, a greckie czwartej.
Jeśli efekty wywołane przez każdą ze zmiennych są addytywne (to znaczy dodają się do ogólnego wyniku), to plan taki daje nieobciążone estymatory wpływu każdej możliwej wartości każdej z tych zmiennych na zmienną objaśnianą, choć możliwych kombinacji ich wartości jest o wiele więcej: n 4 . {\displaystyle n^{4}.} Znacząco obniża to koszt badania. Aby obliczyć wpływ danej wartości danej zmiennej, wystarczy uśrednić wyniki odpowiadających jej eksperymentów.
Kwadraty grecko-łacińskie mogą też być użyte do konstrukcji kwadratów magicznych.

Historia

W latach 80. XVIII wieku Euler pokazał metodę konstrukcji kwadratu grecko-łacińskiego, dla n {\displaystyle n} nieparzystego oraz dla wielokrotności 4. Zauważywszy, że nie istnieje kwadrat rzędu 2 i nie potrafiąc skonstruować kwadratu rzędu 6 (tzw. problem 36 oficerów) postawił hipotezę, że nie istnieją kwadraty grecko-łacińskie rzędu n = 4 k + 2 , {\displaystyle n=4k+2,} gdzie k = 0 , 1 , 2 , … {\displaystyle k=0,1,2,\dots } Faktycznie nieistnienie kwadratu rzędu 6 zostało udowodnione w 1901 przez Gastona Tarry’ego przez siłowe sprawdzenie wszystkich możliwych układów. Hipoteza Eulera nadal nie była jednak ani udowodniona, ani obalona. W 1959 R.C. Bose i Shrikhande znaleźli pewne kontrprzykłady; później Parker znalazł kontrprzykład rzędu 10. W 1960 Parker, Bose i Shrikhande pokazali, że hipoteza Eulera jest fałszywa dla wszystkich n ⩾ 10. {\displaystyle n\geqslant 10.} Ostatecznie okazało się, że istnieją kwadraty grecko-łacińskie każdego rzędu n ⩾ 3 {\displaystyle n\geqslant 3} z wyjątkiem 6.

Zobacz też

kwadrat łaciński

kwadrat magiczny

sudoku

Przypisy

Linki zewnętrzne

Narzędzie Javy asystujące w konstrukcji kwadratów grecko-łacińskich (samo ich nie tworzy) (ang.) z cut-the-knot

Anything but square: from magic squares to Sudoku (ang.)

[1] 15-09}} Kwadrat grecko-łaciński lub kwadrat Eulera rzędu $n$ nad dwoma $n$ -elementowymi zbiorami $S$ i $T$ – kwadratowa tablica o $n$ wierszach i $n$ kolumnach, zawierająca pary $(s,t),$ gdzie $s\in S$ i $t\in T,$ taka że:
każdy wiersz i każda kolumna zawiera dokładnie jeden raz każdy element z $S$ i dokładnie jeden raz każdy element z $T$ oraz

żadne dwie komórki nie zawierają tej samej pary $(s,t)$
Autorem koncepcji jest Leonhard Euler, który używał zbiorów:
$S=\{A,B,C,\dots \},$ pierwsze $n$ dużych liter z alfabetu łacińskiego,
i
$T=\{\alpha ,\beta ,\gamma ,\dots \},$ pierwsze $n$ małych liter z alfabetu greckiego
Stąd nazwa kwadrat grecko-łaciński. Przykłady poniżej:

Rzędu 3 Rzędu 4 Rzędu 5

Układ samych łacińskich znaków, a także układ samych greckich znaków w kwadracie grecko-łacińskim tworzą kwadrat łaciński. Kwadrat grecko-łaciński może zostać rozłożony na dwa ortogonalne kwadraty łacińskie. Ortogonalność oznacza tu, że każda para $(s,t)$ z iloczynu kartezjańskiego $S\times T$ wystąpi dokładnie raz.

Planowanie eksperymentów[edytuj | edytuj kod]

Kwadraty grecko-łacińskie mają zastosowanie w planowaniu eksperymentów naukowych. Załóżmy, że mamy maksymalnie 4 nominalne zmienne, którymi możemy wpływać na wynik eksperymentu i każda z nich może przyjmować $n$ wartości. Na przykład w badaniach medycznych zmiennymi mogą być:

podawany lek (jeden z trzech),

stopień nasilenia choroby (niski, średni lub wysoki),

wiek badanego (podzielony na trzy kategorie),

szpital, w którym przeprowadzane jest badanie (jeden z trzech).

Teraz wystarczy ułożyć kwadrat grecko-łaciński rzędu $n$ (tutaj: 3), aby otrzymać plan $n^{2}$ eksperymentów. Każde pole kwadratu odpowiada jednemu z eksperymentów, kolumny to możliwe wartości pierwszej zmiennej, wiersze – drugiej zmiennej, litery łacińskie odpowiadają trzeciej zmiennej, a greckie czwartej.
Jeśli efekty wywołane przez każdą ze zmiennych są addytywne (to znaczy dodają się do ogólnego wyniku), to plan taki daje nieobciążone estymatory wpływu każdej możliwej wartości każdej z tych zmiennych na zmienną objaśnianą, choć możliwych kombinacji ich wartości jest o wiele więcej: $n^{4}.$ Znacząco obniża to koszt badania. Aby obliczyć wpływ danej wartości danej zmiennej, wystarczy uśrednić wyniki odpowiadających jej eksperymentów.
Kwadraty grecko-łacińskie mogą też być użyte do konstrukcji kwadratów magicznych.

Historia[edytuj | edytuj kod]

W latach 80. XVIII wieku Euler pokazał metodę konstrukcji kwadratu grecko-łacińskiego, dla $n$ nieparzystego oraz dla wielokrotności 4. Zauważywszy, że nie istnieje kwadrat rzędu 2 i nie potrafiąc skonstruować kwadratu rzędu 6 (tzw. problem 36 oficerów) postawił hipotezę, że nie istnieją kwadraty grecko-łacińskie rzędu $n=4k+2,$ gdzie $k=0,1,2,\dots$ Faktycznie nieistnienie kwadratu rzędu 6 zostało udowodnione w 1901 przez Gastona Tarry’ego przez siłowe sprawdzenie wszystkich możliwych układów. Hipoteza Eulera nadal nie była jednak ani udowodniona, ani obalona. W 1959 R.C. Bose i Shrikhande znaleźli pewne kontrprzykłady; później Parker znalazł kontrprzykład rzędu 10. W 1960 Parker, Bose i Shrikhande pokazali, że hipoteza Eulera jest fałszywa dla wszystkich $n\geqslant 10.$ Ostatecznie okazało się, że istnieją kwadraty grecko-łacińskie każdego rzędu $n\geqslant 3$ z wyjątkiem 6.

Zobacz też[edytuj | edytuj kod]

kwadrat łaciński

kwadrat magiczny

sudoku

Przypisy[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Narzędzie Javy asystujące w konstrukcji kwadratów grecko-łacińskich (samo ich nie tworzy) (ang.) z cut-the-knot

Anything but square: from magic squares to Sudoku (ang.)

Encyklopedia internetowa (square table):
Britannica: topic/orthogonal-Latin-squares

[2] żdy wiersz i każda kolumna zawiera dokładnie jeden raz każdy element z $S$ i dokładnie jeden raz każdy element z $T$ oraz

[3] żadne dwie komórki nie zawierają tej samej pary $(s,t)$

[4] $S=\{A,B,C,\dots \},$ pierwsze $n$ dużych liter z alfabetu łacińskiego,

[5] $T=\{\alpha ,\beta ,\gamma ,\dots \},$ pierwsze $n$ małych liter z alfabetu greckiego

[6] wany lek (jeden z trzech),

[7] stopień nasilenia choroby (niski, średni lub wysoki),

[8] wiek badanego (podzielony na trzy kategorie),

[9] szpital, w którym przeprowadzane jest badanie (jeden z trzech).

[10] wadrat łaciński

[11] wadrat magiczny

[12] sudoku

[13] Narzędzie Javy asystujące w konstrukcji kwadratów grecko-łacińskich (samo ich nie tworzy) (ang.) z cut-the-knot

[14] Anything but square: from magic squares to Sudoku (ang.)

[15] Britannica: topic/orthogonal-Latin-squares

[16] żdy wiersz i każda kolumna zawiera dokładnie jeden raz każdy element z $S$ i dokładnie jeden raz każdy element z $T$ oraz

[17] żadne dwie komórki nie zawierają tej samej pary $(s,t)$

[1]


Rzędu 3	Rzędu 4	Rzędu 5

Planowanie eksperymentów[edytuj | edytuj kod]

Historia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]