ࡱ>  ( F/ 0|DTimes New Roman 3|dv 0|( 0De0}fԚ New Roman 3|dv 0|( 0 DArialNew Roman 3|dv 0|( 0"0DWingdingsRoman 3|dv 0|( 0@DSymbolgsRoman 3|dv 0|( 0 ` .  @n?" dd@  @@`` |1    ) A J  c 1?@8  7uʚ;2Nʚ;g43d3dv 0pppp@ <4!d!d` 0,3<4dddd` 0,3 ? %bNec N'Yaxe| !UYck    DefinitionA Latin square of order n with entries from an n-set X is an n n array L in which every cell contains an element of X such that every row of L is a permutation of X and every column of L is a permutation of X.&>  DefinitionLet X be a finite set of cardinality n, and let  be a binary operation defined on X. We say that the pair ( X,  ) is a quasigroup of order n provided that the following two properties are satisfied: 1.For every x,y X, the equation x  z = y has a unique solution for z X. 2.For every x,y X, the equation z  x = y has a unique solution for z X. d&"7""7""         ` f3f3` ff̙` ___` ff` 3ff3f>?" dd@,?lPd@   Z l<@ d`"  n?" dd@   @@``PR    @ ` ` p>> f^ 0(  0^T y 0 "yZ 0 S B7 C DEHFPv @?q 6 6 n(dx  G b q %(@"B y2 0 ZG1?" 0 T|jgֳgֳ ?"P  L cN NN}/kGrjL#j_   0 Tngֳgֳ ?"``  Z* 0 TDsgֳgֳ ?"`   \* 0 Twgֳgֳ ?"`   \*  0 0z "  |0 cN NN}/kGr ,{Nd\ ,{ Nd\ ,{Vd\ ,{Nd\  ` 0 Hd޽h? ?0 f3f3 Soaring0     4@(  4T t 4 "tZ 4 S BsC5 DEHFPv @?3 r4 rv$[I_l3HxF 3 %(@" 2 4 3 CRENGCJRQ1? `TO`TR`TO`TRR`TRR"t 4 Tgֳgֳ ?"/O  L cN NN}/kGrjL#j_   4 T,/gֳgֳ ?"pp   N cN NN}/kGroRjL#j_  4 Tpgֳgֳ ?"``  Z* 4 Tugֳgֳ ?"`   \*  4 Txgֳgֳ ?"`   \*` 4 Hd޽h? ?4 f3f3  00(  x  c $L0P   x  c $ 0`     H  0޽h ? ̙33  00(  x  c $0P   x  c $ 0  H  0޽h ? ̙33  @0(  x  c $,0P   x  c $ 0  H  0޽h ? ˽"i6ffff VN@$(  $ $ S  0``  HTheorem: Suppose  is a binary operation defined on a finite set X of cardinality n. Then ( X,  ) is a quasigroup if and only if its operation table is a Latin square of order n. Note: We obtain Latin squares that are the multiplication tables of groups. & H $ 0޽h ? ˽"i6ffff@!   P(8 (  82 8 S | 0  fExample: ( c " e ) " d `" c " ( e " d )J4  n pp  8 #"&  8 # l1? p  L b @` 8 # l1? p  L a @` 8 # l1? p  L d @` 8 # l 1? p  L c @` 8 # lt41? p  L e @` 8 # ll<1?=  L c @` 8 # l=1? =  L b @` 8 # lK1? =  L a @` 8 # lS1?=  L e @` 8 # l[1?=  L d @` 8 # lU1?= L a @` 8 # l$k1? = L e @` 8 # lxl1?  = L b @` 8 # lt1? = L d @` 8 # l1?= L c @` 8 # l|1?  L d @` 8 # lD1?  L c @` 8 # l1?   L e @` 8 # l81?   L a @` 8 # lة1?  L b @` ~8 # lģ1?p  L e @` }8 # ld1? p  L d @` |8 # l1? p  L c @` {8 # lX1?p  L b @` z8 # l1?p  L a @`B 8 To ?pp~B 8 N1 ?  ~B 8 N1 ?~B 8 N1 ?==~B 8 N1 ?  B 8 To ?p p B 8 To ?pp ~B 8 N1 ?pp ~B 8 N1 ? p p ~B 8 N1 ? p p ~B 8 N1 ?pp B 8 To ?pp H 8 0޽h ? f3f3 `<P(  < < c $ 0PP  |Definition: An orthogonal array OA(n, 3) of order n and depth 3 is a 3 by n^2 array with the integers 1 to n as entries, such that for any two rows of the array, the n^2 vertical pairs occurring in these rows are different. Definition: Two Latin squares for which the corresponding orthogonal arrays have the same three rows ( possibly in different order ) are called conjugates. }}H < 0޽h ? f3f3]  pE(  D D S   0  9 Example:   9f P` E #"[Z[P` QD # l1? ` G4 @` PD # l$1?  ` G3 @` OD # lL1?B  ` G1 @` ND # l 1? B ` G2 @` MD # lH 1?  ` G2 @` LD # l1?  ` G1 @` KD # l%1?Z  ` G3 @` JD # lT'1?Z ` G4 @` ID # l41?` G3 @` HD # l|<1?,` G2 @` GD # lC1?r,` G4 @` FD # lTK1?r` G1 @` ED # lR1?` G1 @` DD # l,Z1?D` G4 @` CD # la1?D` G2 @` BD # li1?` G3 @` AD # lpp1?  G4 @` @D # lw1?   G3 @` ?D # lH1?B   G2 @` >D # l1? B  G1 @` =D # l 1?   G4 @` X # lp1?` {  G1 @` =X # l1?E `  G3 @` 1?@ I 3 @` X # l,?1?@ I 1 @` X # lL1?@ I 2 @` X # lLT1?`@ I 2 @` X # l[1?@` I 3 @` X # lc1?`@ I 1 @`B X To ?`@`~B X N1 ?@~B X N1 ?@B X To ?2@2B X To ?`2~B X N1 ?@`@2~B X N1 ?`2B X To ?@`@2m f pp  X #"PPP` @P X # lg1?  p  I 2 @` X # ln1? p  I 3 @` X # llv1? p  c 1 @` X # lX1?   I 1 @` X # l1?   I 2 @` X # l1?  I 3 @` X # lP1? p I 3 @` X # ld1?p  I 1 @` X # lh1?p I 2 @`B X To ?pp~B X N1 ?~B X N1 ?  B X To ?p p B X To ?pp ~B X N1 ?pp ~B X N1 ? p p B X To ?pp H X 0޽h ? f3f3- ,,8@\N,(  \ \ S  0  bDefinition: An n n array A with cells which are either empty or contain exactly one symbol is called a partial Latin square if no symbol occurs more than once in any row or column. Example:N NiQ Ppartial Latin square N b_b[tevbNec.F2  ,j  p ( @\ #""     p ( \ # l1? p ( > @` \ # l1? ( > @` \ # lL1?<( > @` \ # l1?<( > @` \ # l1? p  > @` \ # lp1?  > @`  \ # l1?<  > @`  \ # l<1? < > @`  \ # l1? V p  I 4 @`  \ # lL1?V  > @`  \ # l 1?<V   > @` \ # l1?V <  > @` \ # l1?  p V  > @` \ # l$$1? V  I 3 @` \ # lt+1?< V  I 2 @` \ # l,1? <V  I 1 @`B \ To ? p  ~B \ N1 ?V p V ~B \ N1 ? p ~B \ N1 ?p B \ To ?(p (B \ To ? (~B \ N1 ?< <(~B \ N1 ? (~B \ N1 ?  (B \ To ?p  p (j  p ( >\ #""@@@@ ( 1\ # l71? p ( I 2 @` 0\ # l?1? ( > @` /\ # lDL1?<( > @` .\ # lS1?<( > @` -\ # l[1? p  > @` ,\ # lb1?  I 1 @` +\ # lj1?<  > @` *\ # lLq1? < > @` )\ # lx1? V p  > @` (\ # lHz1?V  > @` '\ # l1?<V   I 1 @` &\ # lL1?V <  > @` %\ # lx1?  p V  > @` $\ # lН1? V  > @` #\ # l1?< V  > @` "\ # l1? <V  c 1 @`B 2\ To ? p  ~B 3\ N1 ?V p V ~B 4\ N1 ? p ~B 5\ N1 ?p B 6\ To ?(p (B 7\ To ? (~B 8\ N1 ?< <(~B 9\ N1 ? (~B :\ N1 ?  (B ;\ To ?p  p (H \ 0޽h ? f3f3% %%/I`0%(  ` ` S P 0  XNote: NiQ Ppartial Latin square&N^wv(W[ N N T [ Npconjugates0 Definition: If the first k rows of a partial Latin square ( k f" n) are filled and the remaining cells are empty, then A is called a k n Latin rectangle.F  ,{" > f pp  0` #"@   &` # l1? p  I 4 @` %` # l1?@  p  I 3 @` $` # l1? @ p  I 2 @` #` # ll1? p  I 1 @` "` # l1?  I 4 @` !` # l1?@   I 3 @`  ` # ld1?@   I 2 @` ` # l1?  I 1 @` ` # l1?p I 2 @` ` # l 1?@ p I 1 @` ` # l,1?p@  I 1 @` ` # l@"1?p I 1 @`B '` To ?pp~B (` N1 ?~B )` N1 ?  B *` To ?p p B +` To ?pp ~B ,` N1 ?pp ~B -` N1 ?@ p@ p ~B .` N1 ?pp B /` To ?pp rf pp  I` #"0   =` # l+1? p  I 2 @` <` # ll-1?@  p  I 2 @` ;` # l;1? @ p  c 1 @` :` # lC1? p  I 1 @` 9` # lK1?  I 4 @` 8` # llL1?@   I 3 @` 7` # lZ1?@   I 2 @` 6` # l[1?  c 1 @` 5` # l\c1?p I 4 @` 4` # lpq1?@ p I 3 @` 3` # ltr1?p@  I 2 @` 2` # lz1?p I 1 @`B >` To ?pp~B ?` N1 ?~B @` N1 ?  B A` To ?p p B B` To ?pp ~B C` N1 ?pp ~B D` N1 ?@ p@ p ~B E` N1 ?pp ~B H` N1 ? p B F` To ?p H ` 0޽h ? f3f3 dV(  d d S  00P  Theorem: A k n Latin rectangle, kn, can be extended to a ( k+1 ) n Latin rectangle. Proof: Let Bj={ a | a NQs(W,{jL} j=1,2,& & ,n 4"SIfB1,B2,& & ,BnwQSDRsSS W.L.O.G. Sr PƖTpB1,B2,& & ,Br 5" B1,B2,& & ,BrqQ r(n-k) PCQ }(S͑) Sk PCQ }YQs (n-k) !k 4" B1,B2,& & ,Br\ gr P N TCQ } 4" B1,B2,& & ,BnwQSDR A "&""""" "         2      "m   H d 0޽h ? f3f3 h(  h h S D 0  ~Theorem:L(n) g" (n!)^2n / n^(n^2) (We denote by L(n) the total number of different Latin squares of order n) Proof: to construct a Latin square of order n, we can take any permutation of 1 to n as the first row. If we have constructed a Latin rectangle with k rows, then the number of choices for the next row is perB where if bij=1 if i Bj. By theorem 12.8, this permutation is at least (n-k)^nn!/n^n. so we find L(n) g" [n!][ (n-1)^nn!/n^n][ (n-2)^nn!/n^n] & & [1^nn!/n^n] = (n!)^2n / n^(n^2) ,  <  >>  H h 0޽h ? f3f3  lW(  l l S  0P  & Theorem:(due to H. J. Ryser in 1951) Let A be a partial Latin square of order n in which cell ( i, j ) is filled if and only if if"r and jf"s. Then A can be completed to a Latin square if and only if A( i ) r+s-n for i=1,& & ,n, where A( i ) denotes the number of elements of A that are equal to i. Proof: () b[b}YvLatin squareRbVNYS naB+D, i(WB+D-Np`}YQsn-s!k, i=1,& & ,n 4" B( i ) f" n-s SA( i )+ B( i ) = r, 4" B( i ) = r- A( i ) 4" r- A( i ) f" n-s i.e A( i ) + n-s r, sSA( i ) r+s-n 4'\CHQ     &ab p @`  l #" p  l # l 1? @`  L D  @` l # l`1?p `  L C  @` l # l` 1? @  L B  @` l # lp1?p   Q A    @`B l To ?p @ ~B  l N1 ?p @ B  l To ?p` @` B  l To ?p p` ~B  l N1 ? ` B  l To ?@ @` H l 0޽h ? f3f3 0(p(  p p S X0 0  "() Let B be the (0,1)-matrix of size r n with bij=1, if and only if the element j does not occur in row i of A. Clearly every row of B has sum n-s. The j-th column of B has sum r-A( j ) f" n-s. (5" A( j ) r+s-n ) By Theorem7.5 ( with d:=n-s ) we have B=L(s+1)+& & +L(n) where each L(t) is an r n (0,1)-matrix with one 1 in each row and at most one 1 in each column. Say L(t) = [lij(t)]. Then we fill the cell in position ( i,j ) of A, i = 1,& & ,r, j = s+1,& & ,n, by k if lik(j) = 1. Thus A is changed into a partial Latin square of order n with r complete rows, i.e. a Latin rectangle. So this can be completed to a Latin square of order n.+" [   "V  ^ Z +k`H p 0޽h ? f3f3  H @ t(  t t S P 0   :Theorem: A partial Latin square of order n with at most n-1 filled cells can be completed to a Latin square of order n. (dkp g TvEvans conjecture, NB. Smetaniuke1981t^IQ) Proof: case1: Assume that no row or column contains exactly one filled cell. Thus the filled cells are contained in at most m rows and columns, where m:= n/2 . We may permute rows and columns so that all filled cells lie in the upper left subarray of order m. 5" Every m m Latin rectangle can be completed to a Latin square of order n. So it will suffice to fill in the unfilled cells of the upper left subarray of order m to get a Latin rectangle. But this is easy, as we have n symbols available and we may proceed in any order, filled in a cell of the subsquare with a symbol not yet used in the row or column containing the cell. up1p$"H z    LH t 0޽h ? f3f3פ x(  x x S 0 0  d case2: Assume there is a symbol x of L that occurs only once in L. s0}Ifܖ,@bNweu case1KNExample: omDH  5v p Z  Jx #"."NMNNNMNp  4x # l1?  Z  > @` 3x # lp1?, Z  > @` 2x # l1?J ,Z  > @` 1x # l\1?f JZ  > @` 0x # l1? fZ  > @` /x # l1? Z  > @` .x # l@1? Z  > @` -x # lз1?   > @` ,x # l1?,   G5 @` +x # l1?J ,  > @` *x # l1?f J  > @` )x # lx1? f  > @` (x # l1?   > @` 'x # lP1?   G2 @` &x # l1?   > @` %x # l1?,  > @` $x # l1?J,  > @` #x # lX1?fJ  > @` "x # lD 1?f  > @` !x # l1?  > @`  x # l01?  > @` x # l\1? B  > @` x # l 1?,B  > @` x # l.1?JB, > @` x # l51?fBJ > @` x # l<1?Bf G3 @` x # l`D1?B > @` x # lK1?B G1 @` x # lPS1?  B > @` x # lZ1?, B > @` x # la1?J,B > @` x # lPi1?fJB > @` x # lj1?fB > @` x # lw1?B > @` x # lly1?B > @` x # l1?   > @` x # l(1?,  > @` x # l1?J, > @` x # l1?fJ > @`  x # l1?f > @`  x # l(1? > @`  x # l1? > @`  x # l1? p  > @`  x # l1?,p  G4 @` x # l1?Jp, > @` x # l01?fpJ > @` x # l1?pf G1 @` x # l|1?p > @` x # l1?p > @`B 5x To ?p p~B 6x N1 ? ~B 7x N1 ? ~B 8x N1 ?B B~B 9x N1 ? ~B :x N1 ? ~B ;x N1 ?  B x N1 ?pZ ~B ?x N1 ?pZ ~B @x N1 ?fpfZ ~B Ax N1 ?JpJZ ~B Bx N1 ?,p,Z ~B Cx N1 ? p Z B Dx To ? p Z 5v pp  x #"."NMNNNMN   |x # l1? p  > @` {x # l1?w p  > @` zx # lX1?R  wp  > @` yx # lD 1?.  R p  > @` xx # l1?  . p  > @` wx # l01? p  > @` vx # l\1? p  > @` ux # l 1?   > @` tx # l.1?w   > @` sx # l51?R w  > @` rx # l<1?. R   > @` qx # ldD1?  .   > @` px # lK1?   > @` ox # lS1?   > @` nx # lZ1?'   > @` mx # l@b1?w'   > @` lx # lc1?R ' w  > @` kx # lp1?. ' R  > @` jx # l`x1? ' .  > @` ix # l1?'   > @` hx # l 1?'   > @` gx # lP1?'  > @` fx # l1?w'  > @` ex # l1?R w'  > @` dx # l1?. R '  > @` cx # lЫ1? . '  > @` bx # l`1? '  > @` ax # l1?'  > @` `x # l 1?K > @` _x # lP1?wK > @` ^x # l1?R Kw > @` ]x # l1?. KR  > @` \x # l1? K.  G5 @` [x # l 1?K  > @` Zx # l1?K G2 @` Yx # l1?K > @` Xx # lp1?wK > @` Wx # l1?R wK > @` Vx # l 1?. R K > @` Ux # l1? . K > @` Tx # l1? K G3 @` Sx # lP#1?K G1 @` Rx # l*1?p > @` Qx # l21?wp > @` Px # l91?R pw > @` Ox # l@1?. pR  > @` Nx # lH1? p.  G4 @` Mx # lO1?p  G1 @` Lx # l W1?p > @`B }x To ?pp~B ~x N1 ?~B x N1 ?KK~B x N1 ?~B x N1 ?' ' ~B x N1 ?  ~B x N1 ?  B x To ?p p B x To ?pp ~B x N1 ?pp ~B x N1 ? p p ~B x N1 ?. p. p ~B x N1 ?R pR p ~B x N1 ?wpwp ~B x N1 ?pp B x To ?pp 6v pp  x #"."NMNNNMN`  x # lb1? p  > @` x # lDj1?w p  > @` x # lq1?R  wp  > @` x # ls1?.  R p  > @` x # l<1?  . p  > @` x # l̇1? p  > @` x # l1? p  > @` x # l1?   > @` x # l41?w   > @` x # lĤ1?R w  > @` x # l1?. R   > @` x # l1?  .   > @` x # l1?   > @` x # l1?   > @` x # l1?'   > @` x # l`1?w'   > @` x # l1?R ' w  > @` x # l1?. ' R  > @` x # l1? ' .  > @` x # l1?'   > @` x # l$1?'   > @` x # lp1?'  > @` x # l1?w'  > @` x # l 1?R w'  > @` x # l1?. R '  > @` x # l@1? . '  > @` x # l"1? '  > @` x # l*1?'  > @` x # l11?K > @` x # lD91?wK > @` x # lt@1?R Kw > @` x # lH1?. KR  > @` x # lLO1? K.  G5 @` x # lV1?K  G4 @` x # lt^1?K G2 @` x # le1?K > @` x # l(m1?wK > @` x # ltt1?R wK > @` x # l{1?. R K > @` x # lă1? . K G6 @` x # l01? K G3 @` x # l1?K G1 @` x # lL1?p > @` x # l1?wp > @` x # lܨ1?R pw > @` x # lh1?. pR  > @` x # lı1? p.  G4 @` x # l1?p  G1 @` x # l1?p G3 @`B x To ?pp~B x N1 ?~B x N1 ?KK~B x N1 ?~B x N1 ?' ' ~B x N1 ?  ~B x N1 ?  B x To ?p p B x To ?pp ~B x N1 ?pp ~B x N1 ? p p ~B x N1 ?. p. p ~B x N1 ?R pR p ~B x N1 ?wpwp ~B x N1 ?pp B x To ?pp H x 0޽h ? f3f3rh %#%' ` ) ,NQ4,J.Mu" TOh+'0. hp  0 < HT\ ԤB}  Aquarius MC:\Program Files\Microsoft Office\Templates\Presentation Designs\Soaring.pot\ Aquariusm F92aMicrosoft PowerPointoso@0X @P@ bKaGJ-g  F& &&#TNPP 2OMi & TNPP &&TNPP    &&--- $  $   $- $(( $(22( $2<<2- $<FF<- $FPPF $PZZP- $ZddZ $dnnd- $nxxn- $xx- $ $- $- $- $- $- $ $- $- $- $- $- $- $- $- $""- $",,"- $,66,- $6@@6- $@JJ@- $JTTJ- $T^^T- $^hh^- $hrrh- $r||r- $||- $- $- $- $- $- $- $- $- $- $- $- $- $- $- $- $&&- $&00&- $0::0- $:DD:- $DNND- $NXXN- $XbbX- $bllb- $lvvl~- $vvz- $w- $s- $o- $l- $h- $d- $a- $]- $Y- $W- $S- $O- $L- $  H- $  D- $  B- $ ** >- $*44*:- $4>>48- $>HH>4- $HRRH0- $R\\R.- $\ff\*- $fppf&- $pzzp#- $zz- $- $- $- $ - $- $---&&&&6&--&&/v- $6@@6/w- $@JJ@0y- $JTTJ1{- $T^^T2~- $^hh^3- $hrrh4- $r||r6- $||7- $9- $;- $=- $?- $ A- $!C- $"E- $#H- $%J- $&L- $'N- $(Q- $)S- $*U- $+W- $&&,Y- $&00&-Z- $0::0.\- $:DD:.]- $DNND/^- $NXXN/`- $XbbX0a- $bllb0b- $lvvl1b- $vv1c- $2d- $2d- $2e- $2e- $2e- $3f- $&&&- &($s6Ws =p8KY%cIluqs&&-&& &&-&&($s6Ws =p8KY%cIluqs&&/v- $6@@6/w- $@JJ@0y- $JTTJ1{- $T^^T2~- $^hh^3- $hrrh4- $r||r6- $||7- $9- $;- $=- $?- $ A- $!C- $"E- $#H- $%J- $&L- $'N- $(Q- $)S- $*U- $+W- $&&,Y- $&00&-Z- $0::0.\- $:DD:.]- $DNND/^- $NXXN/`- $XbbX0a- $bllb0b- $lvvl1b- $vv1c- $2d- $2d- $2e- $2e- $2e- $3f- $&- --&&&v3f--F%!-Z 0,X9GWh{2Rq!=Z x.=KWa>ibnrs--&&&G&wc~@ ~~ ~0- &Gy& --y@H-- sөu j ~~ ~0- .2 lԤB};;;;. f.2 jԤB};;;;.--11-- fsө ~~ ~0- .2  jƨt+++*+. .2 +++.--"System !~-&TNPP &՜.+,0     pùjpLinuxj Times New Roman sөArial WingdingsSymbolSoaring ԤB} Definition DefinitionPowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²PowerPoint ²  ϥΦr ²]pd vD _AquariusAquarius  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcefghijklmnopqrstuvwxyz{}~Root EntrydO)Current UserSummaryInformation(d.PowerPoint Document(DocumentSummaryInformation8|