Feladat: 5.67.
(
Blokkrendszer)
Egy
(v,k,λ)-blokkrendszer egy
V alaphalmazból (elemei a pontok) és annak részhalmazainak egy
B részhalmazából (elemei a blokkok) álló (
V,B) halmazrendszer, ha
VB1.
|V|=v,
VB2. Minden blokk
k elemű,
VB3. minden két különböző pontból álló pár pontosan
λ blokkban van egyszerre benne.
a) Fejezzük ki
v,
k és
λ segítségével a blokkok
|B|=b számát!
b) Fejezzük ki
v,
k és
λ segítségével egy adott pontot tartalmazó blokkok
r számát!
(Ez miért független a ponttól?)
c) Mutassuk meg, hogy ha létezik
(
n2
+n+1,n+1,1) blokkrendszer (
n≥2), akkor az projektív sík!
d) Mutassuk meg, hogy ha létezik
(v,k,1) blokkrendszer (
v>k≥3), akkor
v≥
k2
-k+1 és egyenlőség esetén a blokkrendszer projektív sík!
e) Igaz-e, hogy ha létezik
(
n2
,n,1) blokkrendszer (
n≥2), akkor az affin sík?
f) Próbáljuk meg eldönteni, hogy mely
2<k<v≤31 esetén van
(v,k,1) blokkrendszer!
Megoldás: 5.67
a)
b=
λ(
n
2
)
(
k
2
)
.
b)
r=
λ(n-1)
k-1
d) Számoljuk össze kétféleképpen azokat a blokkpárokat (egyenespárokat), amelyeknek van közös eleme (metszéspontja).
Egyrészt
b blokk van, így a metsző párok száma legfeljebb
(
b
2
), és ha ennyi metsző pár van, akkor bármely két blokk metszi egymást, így a blokkrendszer projektív síkot.
Másrészt egy pontban
r egyenes találkozik, tehát pontonként
(
r
2
) pártalálkozás van, összesen pedig
v(
r
2
). Ha a kétféle számolást összevetjük és felhasználjuk az a), b) feladatrészben kapott összefüggéseket és átszorzás után egyszerűsítünk a
(v-k)>0 tényezővel, akkor a kívánt egyenlőtlenséghez jutunk.
e) Igaz.
f) Az alábbi táblázat a lehetséges eseteket foglalja össze. A táblázat egy-egy oszlopában egy-egy lehetséges
v értéket (pontok száma) vizsgálunk, 6 ponttól 31-ig.
| |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
| |
15 |
21 |
28 |
36 |
45 |
55 |
66 |
78 |
91 |
105 |
120 |
136 |
153 |
3 |
3 | - | 1 | - | 2 | - | X | - | 3 | - | 4 | - | X | - |
4 |
6 | - | X | - | - | X | - | - | 10 | - | - | 11 | - | - |
5 |
10 | - | - | - | X | - | - | - | X | - | - | - | X | - |
6 |
15 | 16 | - | - | - | - | X | - | - | - | - | 17 | - | -
|
| |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
| |
171 |
190 |
210 |
231 |
253 |
276 |
300 |
325 |
351 |
378 |
409 |
435 |
462 |
3 |
3 | 5 | - | 6 | - | X | - | 7 | - | 8 | - | X | - | 9 |
4 |
6 | X | - | - | X | - | - | 12 | - | - | 13 | - | - | X |
5 |
10 | - | - | 14 | - | - | - | 15 | - | - | - | X | - | - |
6 |
15 | - | - | 18 | - | - | - | - | X | - | - | - | - | 19
|
Egy-egy sor a blokk egy-egy lehetséges méretének felel meg 3-tól 6-ig.
A ,,-" jelet tettük egy mezőbe, ha a
(k-1)|(v-1) feltétel miatt kiesik az a lehetőség, míg ,,X" mutatja, hogy a
(
k
2
)|(
n
2
) feltétel az akadály. A megmaradt helyekre egy-egy számot, az eset sorszámát írtuk, később eszerint vesszük végig a lehetőségeket. A táblázatból kimaradtak a 6-nál hosszabb blokkoknak megfelelő esetek, de ezeknél minden eset kizárható az említett két feltétel miatt. 6-nál kevesebb ponttal nincs nemtriviális blokkrendszer.
A táblázatból kiolvasható esetek:
1. eset:
(7,3,1) - a kételemű test feletti projektív sík, a Fano sík. Jelben:
PG(2,2).
2. eset:
(9,3,1) - a háromelemű test feletti affin sík. Jelben:
AG(2,3).
3. eset:
(13,3,1),
r=6,
b=26. Vegyünk egy szabályos
13-szöget és csúcsai közül két háromszöget, melyek összesen hat oldala mind különböző hosszú. Legyenek a blokkok ezek a háromszögek és elforgatottjaik.
4. eset:
(15,3,1),
r=7,
b=35. Legyenek a pontok egy teljes hatszög-gráf élei. Három él tartozzon egy blokkba, ha háromszöget alkot vagy ha hat kölönböző végpontja van.
5. eset:
(19,3,1),
r=9,
b=57.Vegyünk egy szabályos
19-szöget és csúcsai közül három háromszöget, melyek összesen kilenc oldala mind különböző hosszú (a csúcsok sorszámai lehetnek pl
0,
1,
5 és
0,
2,
8 illetve
0,
9,
12). Legyenek a blokkok ezek a háromszögek és elforgatottjaik.
6. eset:
(21,3,1),
r=10,
b=70. Vegyünk három Fano síkot:
P0
,
P1
, ... ,
P6
,
Q0
,
Q1
, ... ,
Q6
,
R0
,
R1
, ... ,
R6
. A blokkok álljanak egyrészt azokból a hármasokból, amelyek betűjele azonos és saját projektív síkjukon egy egyenesen vannak, másrészt azokból, amelyek három különböző betűt tartalmaznak és indexeik összege
0-val kongruens
(mod3).
7. eset:
(25,3,1),
r=12,
b=100. Vegyünk egy szabályos
25-szöget és csúcsai közül négy háromszöget, melyek összesen 12 oldala mind különböző hosszú. A csúcsok sorszámai lehetnek pl (
0,
1,
6), (
0,
2,
9), (
0,
3,
11) és (
0,
4,
11). Legyenek a blokkok ezek a háromszögek és elforgatottjaik.
8. eset:
(27,3,1),
r=13,
b=117. A háromelemű test feletti affin tér:
AG(3,3). Másképp: Vegyünk három
AG(2,3) síkot:
P0
,
P1
, ... ,
P8
,
Q0
,
Q1
, ... ,
Q8
,
R0
,
R1
, ... ,
R8
. A blokkok álljanak egyrészt azokból a hármasokból, amelyek betűjele azonos és saját affin síkjukon egy egyenesen vannak, másrészt azokból, amelyek három különböző betűt tartalmaznak és indexeik összege
0-val kongruens
(mod3).
9. eset:
(31,3,1),
r=15,
b=155. Vegyünk egy szabályos
31-szöget és csúcsai közül öt háromszöget, melyek összesen 15 oldala mind különböző hosszú. A csúcsok sorszámai lehetnek pl (
0,
1,
5), (
0,
2,
16), (
0,
3,
11), (
0,
6,
13) és (
0,
9,
19). Legyenek a blokkok ezek a háromszögek és elforgatottjaik.
10. eset:
(13,4,1),
r=4,
b=13.
PG(2,3).
11. eset:
(16,4,1),
r=5,
b=20.
AG(2,4).
12. eset:
(25,4,1),
r=8,
b=100. ??
13. eset:
(28,4,1),
r=9,
b=126. ??
14. eset:
(21,5,1),
r=5,
b=21.
PG(2,4).
15. eset:
(25,5,1),
r=6,
b=30.
AG(2,5).
16. eset:
(6,6,1),
r=1,
b=1. Triviális dizájn, egy halmaz és egyetlen részhalmaza, önmaga.
17. és 18. eset: A d) feladatrész eredménye miatt nem létezik.
19. eset:
(31,6,1),
r=6,
b=31.
PG(2,5).