|
Zadaci s kolokvija i rješenja
1. Za sljedeće tvrdnje napišite i obrazložite jesu li istinite ili neistinite.
(a) Za svaki prim broj p>2 postoji 2-dizajn s v = p^2 točaka.
(b) Ne postoji simetrični dizajn s v = 22 točke.
(c) Grupa automorfizama projektivne ravnine reda 3 ima više od 11 000 elemenata.
Rj.
(a) Točno. Za prim broj p postoji konačno polje GF(p) reda p, a onda i
afina ravnina reda p tj. 2-(p^2, p, 1) dizajn.
(b) Istinita tvrdnja. Osnovna relacija glasi 21λ = k(k-1), odakle se
razmatranjem djeljivosti desne strane s 21 dobivaju samo (22,7,2) i
(22,15,10 ) (ovo bi bio komplementarni dizajn),. no 7-2 = 5 nije kvadrat
cijelog broja pa po Schutzenbergerovom teoremu ne postoji takav dizajn.
(c) Netočno, ali "samo" za faktor 2.
Naime, projektivna ravnina reda 3 ima grupu automorfizama PGL(3,3),
dakle svaki automorfizam može se zadati klasom proporcionalnih regularnih
matrica reda 3 nad poljem GF(3).
Općenito za red q, grupa GL(3,q) ima (q^3 - 1)(q^3 - q)(q^3 - q^2) elemenata,
a onda se taj broj još podijeli s q-1 (broj skalarnih faktora različitih od 0).
Za q=3 to je 26*24*18 = 11 232 (to je ono "više od 11 000") pa se dijeljenjem
s 2 dobiva 5 616.
2. Ispitujemo mogućnost postojanja simetričnih dizajna reda 22,
s manje od 100 točaka. Odredite sve odgovarajuće trojke (v, k, λ)
koje ispunjavaju osnovni nužni aritmetički uvjet. Među njima,
ako ih ima, prepoznajte parove koji pripadaju uzajamno
komplementarnim dizajnima.
Ima li među dobivenim trojkama onih koji su Hadamardovog tipa?
Ima li onih koje nisu Hadamardovog tipa, a osim osnovnog uvjeta
ispunjavaju i nužni uvjet dan teoremom Bruck-Ryser-Chowla?
Rj.
Iz osnovne relacije za (v, λ+22, λ) dobivamo
λ(v-1) = ( λ+22)( λ+21)
i onda v = λ + 44 + 21*22/ λ.
Zbog v<100 imamo nejednadžbu
λ^2 - 56 λ + 21*22 < 0
odakle se dobiva da se λ nalazi u
[11, 45].
Uzimajući u obzir djeljivost 21*22 s λ, za
λ dobivamo rješenja: 11,14,21,22,33,42.
To dovodi do tri para komplementarnih trojki
parametara:
(97, 33,11) i (97,64,42),
(91,36,14) i (91,55,33) te
( 87,43,21) i (87,44,22).
Treći par su Hadamardovi parametri.
Za (97,33,11) jednadžba iz B-R-Ch teorema glasi
22x^2 + 11y^2 = z^2,
ima cjelobrojno rješenje (1,3,11).
To je sve što se traži u zadatku, a još
za (91,36,14) može se napisati jednadžba
22x^2 - 14y^2 = z^2, za koju se može pokazati
(npr. promatranjem djeljivosti sa 7)
da nema cjelobrojnog rješenja osim (0,0,0)
pa takav dizajn ne postoji.
3. Odbojkaška ekipa broji 12 igračica. Trener želi formirati šesteročlane
timove tako da na treninzima po dva tima igraju međusobno, a da
se pritom svake tri igračice nađu zajedno u timu jednako mnogo puta.
Koliki je najmanji broj šestorki odbojkašica potreban za to i koliko
će se susreta odigrati? Sastavite jedan takav plan (dizajn).
Rj.
Očito se traži 3-(12,6, λ) dizajn.
Iz aritmetičkih uvjeta dobiva se r = 11λ/2, b = 11λ, λ_2 = 5λ/2
pa je najmanji mogući λ = 2.
3-(12,6,2) doista postoji, kao poznato proširenje
(Hadamardovog) 2-(11,5,2) dizajna.
4. Dokažite da je u simetričnom dizajnu konstantan broj točaka incidentnih
s dva različita bloka.
v. npr. Teorem 4.1. u skriptama.
Zadaci s kolokvija i rješenja
1. Za sljedeće tvrdnje napišite i obrazložite jesu li istinite ili neistinite.
(a) Za svaki prim broj p>2 postoji 2-dizajn s v = p^2 točaka.
(b) Ne postoji simetrični dizajn s v = 22 točke.
(c) Grupa automorfizama projektivne ravnine reda 3 ima više od 11 000 elemenata.
Rj.
(a) Točno. Za prim broj p postoji konačno polje GF(p) reda p, a onda i
afina ravnina reda p tj. 2-(p^2, p, 1) dizajn.
(b) Istinita tvrdnja. Osnovna relacija glasi 21λ = k(k-1), odakle se
razmatranjem djeljivosti desne strane s 21 dobivaju samo (22,7,2) i
(22,15,10 ) (ovo bi bio komplementarni dizajn),. no 7-2 = 5 nije kvadrat
cijelog broja pa po Schutzenbergerovom teoremu ne postoji takav dizajn.
(c) Netočno, ali "samo" za faktor 2.
Naime, projektivna ravnina reda 3 ima grupu automorfizama PGL(3,3),
dakle svaki automorfizam može se zadati klasom proporcionalnih regularnih
matrica reda 3 nad poljem GF(3).
Općenito za red q, grupa GL(3,q) ima (q^3 - 1)(q^3 - q)(q^3 - q^2) elemenata,
a onda se taj broj još podijeli s q-1 (broj skalarnih faktora različitih od 0).
Za q=3 to je 26*24*18 = 11 232 (to je ono "više od 11 000") pa se dijeljenjem
s 2 dobiva 5 616.
2. Ispitujemo mogućnost postojanja simetričnih dizajna reda 22,
s manje od 100 točaka. Odredite sve odgovarajuće trojke (v, k, λ)
koje ispunjavaju osnovni nužni aritmetički uvjet. Među njima,
ako ih ima, prepoznajte parove koji pripadaju uzajamno
komplementarnim dizajnima.
Ima li među dobivenim trojkama onih koji su Hadamardovog tipa?
Ima li onih koje nisu Hadamardovog tipa, a osim osnovnog uvjeta
ispunjavaju i nužni uvjet dan teoremom Bruck-Ryser-Chowla?
Rj.
Iz osnovne relacije za (v, λ+22, λ) dobivamo
λ(v-1) = ( λ+22)( λ+21)
i onda v = λ + 44 + 21*22/ λ.
Zbog v<100 imamo nejednadžbu
λ^2 - 56 λ + 21*22 < 0
odakle se dobiva da se λ nalazi u
[11, 45].
Uzimajući u obzir djeljivost 21*22 s λ, za
λ dobivamo rješenja: 11,14,21,22,33,42.
To dovodi do tri para komplementarnih trojki
parametara:
(97, 33,11) i (97,64,42),
(91,36,14) i (91,55,33) te
( 87,43,21) i (87,44,22).
Treći par su Hadamardovi parametri.
Za (97,33,11) jednadžba iz B-R-Ch teorema glasi
22x^2 + 11y^2 = z^2,
ima cjelobrojno rješenje (1,3,11).
To je sve što se traži u zadatku, a još
za (91,36,14) može se napisati jednadžba
22x^2 - 14y^2 = z^2, za koju se može pokazati
(npr. promatranjem djeljivosti sa 7)
da nema cjelobrojnog rješenja osim (0,0,0)
pa takav dizajn ne postoji.
3. Odbojkaška ekipa broji 12 igračica. Trener želi formirati šesteročlane
timove tako da na treninzima po dva tima igraju međusobno, a da
se pritom svake tri igračice nađu zajedno u timu jednako mnogo puta.
Koliki je najmanji broj šestorki odbojkašica potreban za to i koliko
će se susreta odigrati? Sastavite jedan takav plan (dizajn).
Rj.
Očito se traži 3-(12,6, λ) dizajn.
Iz aritmetičkih uvjeta dobiva se r = 11λ/2, b = 11λ, λ_2 = 5λ/2
pa je najmanji mogući λ = 2.
3-(12,6,2) doista postoji, kao poznato proširenje
(Hadamardovog) 2-(11,5,2) dizajna.
4. Dokažite da je u simetričnom dizajnu konstantan broj točaka incidentnih
s dva različita bloka.
v. npr. Teorem 4.1. u skriptama.
|
