Rezultati 1. kolokvija od 3. svibnja 2011. (informacija)

[Juraj Siftar]

Rezultati 1. kolokvija




1191207055 2+2+0+0+2+0=6
1191200561 0+5+1+0+5+0=11
1191211018 0+0+4+1+1+0=6
1191205921 5+5+1+0+2+0=13
1191209156 0+2+4+0+1+0=7
1191210650 1+0+3+0+4+4=12
1191208965 5+2+3+0+0+0=10
1191208827 2+0+4+0+5+4=15
1191211504 1+1+0+0+2+4=8
1191206453 1+5+0+0+0+4=10
1191212041 1+5+1+0+5+4=16
1191210208 5+0+0+1+4+4=14
1191210367 5+5+0+1+2+0=13
1191205893 5+0+5+0+5+1=16
1191211999 0+4+0+1+5+0=10
1191210923 2+5+3+0+2+1=13
1191202503 4+2+0+0+2+1=9
1191212377 1+2+1+0+5+4=13
1191209289 5+0+4+0+3+0=12
1191205440 2+2+0+0+0+0= 4
1191200582 1+0+0+0+0+1= 2
1191208783 1+5+1+0+0+2= 9
1181204235 0+2+0+1+1+0= 4
1191200096 5+0+0+1+0+0= 6
1191211497 1+0+0+0+2+1= 4

Ovo su rezultati, a kasnije (danas, 6.5. ili sutra 7.5.) uslijedit će i
komentari s rješenjima i tipičnim pogreškama u pojedinim zadacima.
Uvidi: na konzultacijama ili po dogovoru.

Ako je došlo do neke pogreške u navođenju matičnih brojeva,
molim da me upozorite.

Radi lakšeg snalaženja, evo i zadataka:

1. Ispitajte da li postoji simetrični (v,k, λ)-dizajn (netrivijalni, v > k+1) s
v = 34 točke. (Navedite koje ste rezultate pritom koristili).

2. Neka je S 5-(v,k, λ) dizajn. Izvedite formulu za broj blokova koji sadrže
bilo koje tri točke iz S (taj broj označavali smo s λ3).

3. Konstruirajte 3-(8,4,1) dizajn. Je li taj dizajn nužno jednak vlastitom
komplementarnom dizajnu?

4. Neka je p prim broj i v = 2p+1. Ako je D simetrični (v,k, λ) dizajn u kojem
je v > k+1, dokažite da je D Hadamardov dizajn ili komplementarni dizajn Hadamardovog.

5. Na jednom fakultetu studenti imaju 5 sati praktikuma tjedno, svaki radni dan po jedan sat.
Podijeljeni su u 5 grupa, a pomaže im 5 demonstratora.
Dnevno je na raspolaganju jedna učionica u 5 stalnih termina
(npr. od 8-9 h, 9-10 h itd). Može li se raspored
praktikuma organizirati tako da svaka grupa kroz tjedan ima
praktikum u različitim
vremenskim terminima i da im u svim terminima pomažu različiti demonstratori, a da i demonstratori,
radi
ravnopravnosti, dežuraju u različitim terminima?
Uputa: za jedan latinski kvadrat može se uzeti onaj s cikličkom strukturom.

6. Konstruirajte (15,8,4) dizajn pomoću diferencijskog skupa i multiplikatora.



Juraj Šiftar

[Juraj Siftar]

Komentar rješavanja zadataka na kolokviju

1. zadatak
Trebaju biti ispunjeni uvjeti za (v,k, λ)
33 λ = k(k-1) i n = k-λ je kvadrat cijelog broja (Schutzenbergerov tm).
Očito za n u obzir dolaze samo 1,4,9,16 i 25 koji se redom eliminiraju
ili se uoči da 11 mora biti djelitelj od k ili k-1 pa k može biti samo
12 (tada je λ = 4) ili 22 (tada je λ = 14), no u oba slučaja n nije
kvadrat.
Zadatak je relativno dobro rješavan, no kod nekih se zapaža bitna
pogreška da se nužni uvjeti postojanja dizajna miješaju s dovoljnima -
ispunjavanje navedenih aritmetičkih uvjeta samo je nužan uvjet.
Također ima dosta nesnalaženja oko elementarnih svojstava djeljivosti,
primjerice da "ako 33 dijeli k(k-1), onda ili 33 dijeli k ili 33 dijeli k-1"
i slično.


2. zadatak:
Riječ je dakako o poznatoj formuli za koju je trebalo ili navesti
izvod kako je dokazano na predavanjima ili izvesti specijalni
slučaj za 5-(v,k,λ) dizajn i parametar λ3.
Bilo je pogrešnih pokušaja izvoda na temelju "djelomičnog
prisjećanja" kako bi to trebalo ići. Kao što je naglašeno na kolokviju,
tražio se izvod, a ne samo uvrštavanje brojeva u gotovu formulu
pa se za takvo "rješenje" dobivao samo 1 bod.


3. zadatak:
Dosta nesnalaženja i pogrešaka oko vrlo jednostavnog 3-(8,4,1)
dizajna koji bi trebao biti poznat i iz domaće zadaće i iz primjera
s predavanja (interpretacija pomoću kocke, ali treba točno
definirati koje četvorke vrhova čine blokove - oko toga je bilo
dosta zabune). Broj blokova je 14 (što se lako izračuna, ali i u
tome se dosta griješilo).
Bilo je i pogrešaka tipa da taj dizajn uopće ne postoji jer da bi
trebala biti ispunjena jednakost (8-1) = r (4-1) , ali 3 ne dijeli 7.
Ne, u toj relaciji treba biti λ2 = 3 (jer 3-(8,4,1) dizajn je ujedno
i 2-(8,4,3) dizajn i jednakost se onosi na λ2, ne na λ).
U svakom slučaju, 3-(8,4,1) dizajn vrlo lako se konstruira "izravno",
bez neke posebne metode, dakle čisto kombinatorički (neki su
tako i radili), a pritom se vidi da je doista jednak svojem
komplementarnom dizajnu.
Dakle, ovo je bio zadatak u kojem se "isplatilo" rješavanje domaće
zadaće, ali moglo se snaći i bez nje.


4. zadatak:
Očito najteži, nitko ga nije ni blizu riješio, no nije toliko to problem
samo po sebi koliko je problem što se miješaju smjerovi zaključivanja,
što bi trebalo slijediti iz čega.
Dakle, ako je v = 2p+1 i p prim broj, a dizajn je simetričan,
onda v-1 = 2p dijeli umnožak k(k-1). Sada p, kao prim broj mora
dijeliti ili k ili k-1 (koji očito nemaju zajedničkih djelitelja)
pa ili je k = p (ne može biti 2p jer v = 2p+1) ili je k-1 = p, k = p+1.
Sad izravno slijedi oblik parametara karakterističan za Hadamardov
odnosno komplementarni Hadamardov dizajn.
Znači, jedino je trebalo pravilno razmotriti navedeni uvjet djeljivosti.


5. zadatak:
Uglavnom se shvaćalo, barem otprilike, što bi trebalo napraviti,
samo uz dosta pogrešaka različitih vrsta.
Naime, traženi plan jednostavno se dobiva iz 2 ortogonalna
latinska kvadrata reda 5 (ne treba maksimalni MOLS(5), to jest
četiri, nego samo dva). Neki su to shvatili, ali pogrešno naveli
kvadrate (koji nisu ortogonalni), neki su pak ne različite načine
krivo protumačili što bi trebalo učiniti.

6. zadatak:
Treba naći (15,8,4)-diferencijski skup u (cikličkoj) grupi reda 15.
Po teoremu s predavanja siguran multiplikator je 2, a množenje s 2
u grupi ostataka mod 15 daje cikluse:
(0) (1,2,4,8 ) (3,6,12,9) (5,10) (7,14,13,11).
Diferencijski skup očito mora biti unija dva ciklusa duljine 4
no - u tome je bilo dosta propusta - taj nužni uvjet nije općenito
dovoljan pa za izabranu uniju dvije čevorke treba provjeriti je li
doista to diferencijski skup. No, ako je zaključivanje dobro
provedeno, ali je izostala provjera spomenutog uvjeta, dobivalo se
4 od 5 bodova budući da je to ipak s posljednjeg predavanja
pa je uzeta u obzir upućenost u temu (koje kod mnogih nije uopće
bilo).

Općenito: osim dosta "tankog" poznavanja osnovnih činjenica
(vidljivog u pogrešnom navođenju tvrdnji teorema itd), najčešće
uočeni problemi ne odnose se toliko na specifično gradivo iz
kolegija nego na elementarne logičke pogreške i slabo snalaženje
u također elementarnom zaključivanju (aritmetika, kombinatorika).


Juraj Šiftar