|
Rješenje 1. zadatka:
1.
(i) Dizajn 2-(2015,15,5) ne postoji jer nije ispunjen osnovni nužni uvjet,
5 · 2014 nije djeljiv s 14.
(ii) Dizajn 2-(403,3,1) ne samo da može postojati, nego je poznati rezultat da
i postoji budući da je broj točaka 403 ≡ 1 (mod 6), a za 2-(v,3,1) nužni uvjeti
su i dovoljni. (Treba biti v ≡ 1 ili 3 (mod 6)).
(iii) Ne postoji simetrični 2-(v,15,5) dizajn. Naime, moralo bi biti v = 43, a onda
diofantska jednadžba iz uvjeta teorema Bruck-Ryser-Chowla glasi
10 x**2 – 5 y**2 = z**2. Standardnim razmatranjem djeljivosti obje strane
jednadžbe s 5 (tj. izvlačenjem najveće potencije od 5 s kojom su djeljivi x, y i z)
vidi se da ne postoji netrivijalno rješenje.
(iv) Elementarnim razmatranjem djeljivosti vidi se da je v = 57 najmanja vrijednost
za koju bi mogao postojati 2-(v,15,5) dizajn. Po samim parametrima,
kad bi takav bio rezidualni (u bloku) od simetričnog dizajna, bio bi to 2-(77,20,5)
dizajn, ali njegovi parametri ne ispunjavaju uvjet Bruck-Ryser-Chowla jer
pripadna diofantska jednadžba 15 x**2 + 5 y**2 = z**2 nema netrivijalnih rješenja.
Rješenje 2. zadatka
2. U 2-(v,3,1) dizajnu S vrijedi v = 2r+1, b = r(2r+1)/3. Iz definicije
skupa L blokova strukture D jasno je da će D imati jednaki broj točaka i blokova i da će to biti b,
pod uvjetom da su različitim elementima iz B pridruženi različiti podskupovi koji čine L .
Prvo treba odrediti broj točaka na svakom bloku iz L, a za to nam
treba broj blokova koji su u S disjunktni s (bilo kojim) blokom.
Kroz svaku od 3 točke nekog bloka B prolazi još r-1 blokova pa B ima neprazan presjek s ukupno 3(r-1) blokova.
Zato je blok disjunktan s b – 3(r-1) – 1 = b – 3r + 2
blokova iz B. Stoga svaki blok iz L ima
b - 3r+3 točaka, jer treba uračunati i sam blok B.
Nadalje, ako bi se za neke B1 i B2 iz B podudarali njima pridruženi L1 i L2,
to bi najprije značilo da su B1 i B2 nužno disjunktni.
Zato treba prebrojiti blokove iz B koji su uzajamno disjunktni i s B1 i B2.
kad ovi nemaju zajedničkih točaka. Taj broj trebao bi biti manji od
b – 3r + 2 kako se L1 i L2 ne bi podudarali.
Prebrojimo najprije blokove koji imaju zajedničku točku s barem jednim od B1 i B2.
Prvo, to je 9 spojnica trojki točaka na ta dva bloka (dakle, 9 blokova
koji imaju 2 točke u B1 U B2) te još 6(r -4) blokova koji prolaze samo po jednom točkom iz B1 ili B2.
Ukupno 6r - 15 blokova, različitih od B1 i B2, ima neprazan presjek s B1 U B2,
stoga ima b – 2 – (6r – 15) = b – 6r +13 blokova disjunktnih s B1 U B2.
Taj će nam broj ionako trebati za uvjet balansiranosti u dizajnu,
a zasad je važno da je doista b – 3r + 2 > b – 6r +13 (jer r > 3).
Dakle, S je simetrična konfiguracija s b točaka i b blokova, a svaki
blok incidentan je s b – 3r + 3 točaka.
Dalje, kako bi D bio dizajn, treba vrijediti balansiranost, tj. da se svake dvije točke
nalaze na jednako mnogo blokova. Pritom treba razlikovati slučajeve kad se
dva bloka sijeku u jednoj točki (u S) odnosno kad su disjunktni.
U drugom slučaju već znamo da dva disjunktna bloka iz B određuju
dvije točke u D koje se nalaze na
b – 6r + 15 zajedničkih blokova iz L. (Prethodno dobivenom broju
b – 6r +13 pribrajaju se još 2 bloka, L1 i L2 za B1 i B2).
Preostaje slučaj kada B1 i B2 imaju zajedničku točku (u S).
Tada ni L1 ni L2 ne sadrže obje točke B1 i B2 (u D).
Blokovi iz L koji sadrže B1 i B2 bit će samo oni koji su zadani blokovima
disjunktnima i s B1 i s B2. Ponovno prebrojimo blokove iz
B koji imaju neprazan presjek s B1 U B2.
Kroz njihovo sjecište prolaze još r-2 bloka, zatim postoje 4 bloka
koji spajaju preostale točke na B1 i B2, a onda postoji još
4(r-3) blokova koji prolaze samo po jednom točkom na B1 ili B2.
Ukupno, to je 4(r -3) + r - 2 + 4 = 5r – 10 blokova, različitih od B1 i B2,
koji nisu disjunktni s B1 U B2.
Preostaje b – 2 – (5r -10) = b – 5r +8 blokova koji ne sadrže nijednu točku iz
B1 U B2.
Dakle, općenito u strukturi D postoje svega dvije moguće vrijednosti
broja blokova koji sadrže neke dvije točke pa će D biti dizajn
ako i samo ako se te vrijednosti podudaraju: iz b -6r +15 = b – 5r +8 dobivamo
jedinstveno rješenje r=7.
Tada je v = 15, b = 35, S je STS(15),
a D je simetrični 2-(35,17,8 ) dizajn, Hadamardov.
Rješenje 1. zadatka:
1.
(i) Dizajn 2-(2015,15,5) ne postoji jer nije ispunjen osnovni nužni uvjet,
5 · 2014 nije djeljiv s 14.
(ii) Dizajn 2-(403,3,1) ne samo da može postojati, nego je poznati rezultat da
i postoji budući da je broj točaka 403 ≡ 1 (mod 6), a za 2-(v,3,1) nužni uvjeti
su i dovoljni. (Treba biti v ≡ 1 ili 3 (mod 6)).
(iii) Ne postoji simetrični 2-(v,15,5) dizajn. Naime, moralo bi biti v = 43, a onda
diofantska jednadžba iz uvjeta teorema Bruck-Ryser-Chowla glasi
10 x**2 – 5 y**2 = z**2. Standardnim razmatranjem djeljivosti obje strane
jednadžbe s 5 (tj. izvlačenjem najveće potencije od 5 s kojom su djeljivi x, y i z)
vidi se da ne postoji netrivijalno rješenje.
(iv) Elementarnim razmatranjem djeljivosti vidi se da je v = 57 najmanja vrijednost
za koju bi mogao postojati 2-(v,15,5) dizajn. Po samim parametrima,
kad bi takav bio rezidualni (u bloku) od simetričnog dizajna, bio bi to 2-(77,20,5)
dizajn, ali njegovi parametri ne ispunjavaju uvjet Bruck-Ryser-Chowla jer
pripadna diofantska jednadžba 15 x**2 + 5 y**2 = z**2 nema netrivijalnih rješenja.
Rješenje 2. zadatka
2. U 2-(v,3,1) dizajnu S vrijedi v = 2r+1, b = r(2r+1)/3. Iz definicije
skupa L blokova strukture D jasno je da će D imati jednaki broj točaka i blokova i da će to biti b,
pod uvjetom da su različitim elementima iz B pridruženi različiti podskupovi koji čine L .
Prvo treba odrediti broj točaka na svakom bloku iz L, a za to nam
treba broj blokova koji su u S disjunktni s (bilo kojim) blokom.
Kroz svaku od 3 točke nekog bloka B prolazi još r-1 blokova pa B ima neprazan presjek s ukupno 3(r-1) blokova.
Zato je blok disjunktan s b – 3(r-1) – 1 = b – 3r + 2
blokova iz B. Stoga svaki blok iz L ima
b - 3r+3 točaka, jer treba uračunati i sam blok B.
Nadalje, ako bi se za neke B1 i B2 iz B podudarali njima pridruženi L1 i L2,
to bi najprije značilo da su B1 i B2 nužno disjunktni.
Zato treba prebrojiti blokove iz B koji su uzajamno disjunktni i s B1 i B2.
kad ovi nemaju zajedničkih točaka. Taj broj trebao bi biti manji od
b – 3r + 2 kako se L1 i L2 ne bi podudarali.
Prebrojimo najprije blokove koji imaju zajedničku točku s barem jednim od B1 i B2.
Prvo, to je 9 spojnica trojki točaka na ta dva bloka (dakle, 9 blokova
koji imaju 2 točke u B1 U B2) te još 6(r -4) blokova koji prolaze samo po jednom točkom iz B1 ili B2.
Ukupno 6r - 15 blokova, različitih od B1 i B2, ima neprazan presjek s B1 U B2,
stoga ima b – 2 – (6r – 15) = b – 6r +13 blokova disjunktnih s B1 U B2.
Taj će nam broj ionako trebati za uvjet balansiranosti u dizajnu,
a zasad je važno da je doista b – 3r + 2 > b – 6r +13 (jer r > 3).
Dakle, S je simetrična konfiguracija s b točaka i b blokova, a svaki
blok incidentan je s b – 3r + 3 točaka.
Dalje, kako bi D bio dizajn, treba vrijediti balansiranost, tj. da se svake dvije točke
nalaze na jednako mnogo blokova. Pritom treba razlikovati slučajeve kad se
dva bloka sijeku u jednoj točki (u S) odnosno kad su disjunktni.
U drugom slučaju već znamo da dva disjunktna bloka iz B određuju
dvije točke u D koje se nalaze na
b – 6r + 15 zajedničkih blokova iz L. (Prethodno dobivenom broju
b – 6r +13 pribrajaju se još 2 bloka, L1 i L2 za B1 i B2).
Preostaje slučaj kada B1 i B2 imaju zajedničku točku (u S).
Tada ni L1 ni L2 ne sadrže obje točke B1 i B2 (u D).
Blokovi iz L koji sadrže B1 i B2 bit će samo oni koji su zadani blokovima
disjunktnima i s B1 i s B2. Ponovno prebrojimo blokove iz
B koji imaju neprazan presjek s B1 U B2.
Kroz njihovo sjecište prolaze još r-2 bloka, zatim postoje 4 bloka
koji spajaju preostale točke na B1 i B2, a onda postoji još
4(r-3) blokova koji prolaze samo po jednom točkom na B1 ili B2.
Ukupno, to je 4(r -3) + r - 2 + 4 = 5r – 10 blokova, različitih od B1 i B2,
koji nisu disjunktni s B1 U B2.
Preostaje b – 2 – (5r -10) = b – 5r +8 blokova koji ne sadrže nijednu točku iz
B1 U B2.
Dakle, općenito u strukturi D postoje svega dvije moguće vrijednosti
broja blokova koji sadrže neke dvije točke pa će D biti dizajn
ako i samo ako se te vrijednosti podudaraju: iz b -6r +15 = b – 5r +8 dobivamo
jedinstveno rješenje r=7.
Tada je v = 15, b = 35, S je STS(15),
a D je simetrični 2-(35,17,8 ) dizajn, Hadamardov.
|
