Problem Parzystkowa i jego uogólnienia

W mieście Parzystkowo zacny burmistrz postanowił w nietypowy sposób zaktywizować społeczeństwo. Zarządził utworzenie stowarzyszeń, które wykonywać będą powierzone im zadania...

W trakcie zebrania z Radą Miasta uchwalono następujące zasady:

1.: każde stowarzyszenie wyznaczone jest jednoznacznie przez swój skład (innymi słowy nie ma dwóch stowarzyszeń o takim samym składzie osobowym),
2.: każde stowarzyszenie ma parzystą liczbę uczestników,
3.: część wspólna każdych dwóch stowarzyszeń tworzy ugrupowanie złożone z parzystej liczby uczestników.

Rada rada, burmistrz zadowolony... A mieszkańcy? Bardzo chętni do dzielenia się na stowarzyszenia. Okazało się jednak, że to, co łatwe w teorii, w praktyce może być trudne. Powstał bowiem niemały chaos - tym większy, im więcej stowarzyszeń już zostało powołanych. Wszystko dlatego, że mieszkańcy chcieli utworzyć ich jak najwięcej. Zbadajmy tę sprawę.

Opisany powyżej problem zwany problemem Parzystkowa (Eventown problem) można sformułować następująco. Niech $|P$ będzie zbiorem $n$ -elementowym oraz niech $|S1,...,Sm$ będą jego podzbiorami. Żądamy od tych podzbiorów, żeby:

1.: $Si ≠Sj$ dla $i≠ j,$
2.: $| 2 Si$ dla dowolnego $| i,$
3.: $2 Si ∩Sj$ dla $|i≠ j,$

gdzie $| X$ oznacza liczbę elementów zbioru $. X$ Zachodzi następujące oszacowanie na liczbę ugrupowań.

Twierdzenie 1. Maksymalna liczba stowarzyszeń w Parzystkowie liczącym $|n$ mieszkańców wynosi co najmniej $2 n2 .$

Dowód jest prosty i konstruktywny.

Dowód. Załóżmy na początek, że $n = 2k$ dla pewnego $|k.$ Dzielimy zbiór $| 2k$ -elementowy na $| k$ różnych podzbiorów 2-elementowych. Każde stowarzyszenie budujemy teraz z tych par (rysunek obok). Jak widać, takie stowarzyszenia spełniają wszystkie postulowane warunki.

Ponieważ par jest $k,$ wszystkich podzbiorów jest $k 2 .$ Znaleźliśmy zatem $n |2k = 2 2$ stowarzyszeń, co kończy dowód w przypadku $n = 2k.$ Jeśli teraz $|n = 2k + 1,$ to odsuwamy na bok jednego mieszkańca i rozważamy problem dla parzystej liczby mieszkańców, otrzymując $|k n2- 2 = 2$ stowarzyszeń.

Zauważamy, że próba manipulowania parami nie prowadzi do utworzenia nowego stowarzyszenia ponad te zdefiniowane przez podzbiory par. Okazuje się ponadto, że jest to najlepszy możliwy podział - nierówność w twierdzeniu 1 można zastąpić równością.

Twierdzenie 2. Maksymalna liczba stowarzyszeń w Parzystkowie liczącym $|n$ mieszkańców wynosi dokładnie $n 2 2 .$

Niełatwy dowód tego twierdzenia pomijamy. Oryginalny problem Parzystkowa można oczywiście modyfikować. Niech $|m(n,$ oznacza maksymalną liczbę stowarzyszeń w mieście o $| n$ mieszkańcach, przy następujących zasadach:

(1): $Si ≠Sj$ dla $i≠ j,$
(2): $ℓ Si ∩Sj$ dla $i ≠ j.$

Zauważmy, że można podzielić mieszkańców na zbiory złożone z $n ⌊ℓ⌋$ osób i rozważyć stowarzyszenia jako podzbiory tych grup (tak jak w Parzystkowie). Wynika z tego następujące oszacowanie.

Twierdzenie 3. $|m(n,$

Powyższe szacowanie jest elementarne, jednak nie jest znane ogólne, dokładne rozwiązanie.

Problem Nieparzystkowa

Pokażemy teraz, że w pewnych sytuacjach potrafimy podać dokładną odpowiedź. Rozważmy problem miasta Nieparzystkowo:

1.: $Si ≠Sj$ dla $i≠ j,$
2.: $2 / S i$ dla dowolnego $|i,$
3.: $2 Si ∩Sj$ dla $|i≠ j.$

Ponownie pytamy o maksymalną liczbę stowarzyszeń. Zaczniemy tym razem od podania górnego szacowania. Niech $Fq$ będzie ciałem o $q$ -elementach. Zbiór $Fnq$ to zbiór wektorów $(a1,...,an),$ gdzie każde $ai ∈Fq.$ W tym zbiorze naturalnym działaniem jest dodawanie wektorów po współrzędnych. Możemy również rozważyć działanie mnożenia liczby przez wektor. To znaczy jeśli $|α ∈Fq,$ to

α⋅(a1,...,an) = (α ⋅a1,...,α⋅an).

Powiemy, że wektory $v1,...,vk$ są liniowo niezależne w $|Fnq,$ jeśli układ równań

α1v1 +...+ αkvk = (0,...,0)

ma dokładnie jedno rozwiązanie $|α1 = ... = αk = 0.$ W $|Fnq$ możemy również rozważyć iloczyn skalarny dwóch wektorów $|a = (a ,...,a ) 1 n$ oraz $|b = (b1,...,bn),$ to jest liczbę

a⋅b = a1b1 + ... +anbn.

Zauważmy, że jeżeli wśród wektorów $|v,...,v 1 k$ są dwa wektory równe lub jeden z wektorów jest złożony z samych zer, to wektory te nie są liniowo niezależne.

Lemat 1. Jeżeli $v1,...,vk ∈ Fnq$ oraz wektory te są liniowo niezależne, to $|k⩽ n.$

Dowód. Zauważmy, że każdy wektor $n |a∈ Fq$ można zapisać jednoznacznie jako $|a = a1e1 + ...+ anen,$ gdzie w wektorze $e j$ na $j$ -tym miejscu stoi 1, na pozostałych zaś 0. W szczególności wektory $e1,...,en$ są liniowo niezależne. Pokażemy teraz, że żaden inny układ wektorów liniowo niezależnych nie może być liczniejszy niż $n.$

Załóżmy, że $k > n.$ Z uczynionej przed chwilą uwagi każdy z $vi$ można zapisać jako sumę $|vi = αi,1e1 +...+ αi,nen,$ wiemy w szczególności, że $|v1$ także można. Załóżmy teraz bez straty ogólności, że $α 1,1 ≠0$ (gdyby tak nie było, to wystarczy przenumerować wektory $e ,...,e 1 n$ do otrzymania żądanej cechy). Wtedy również

e = -1-v − α-1,2-e + ...− α1,n-e , 1 α1,1 1 α 1,1 2 α1,1 n

zatem każdy wektor, który można zapisać jako kombinację wektorów $|e1,...,en,$ można również zapisać jako kombinację wektorów $|v1,e2,...,en.$ W szczególności $v2$ można tak zapisać. Zauważmy, że przynajmniej jeden ze współczynników stojących przy $e2,...,en$ w zapisie $|v = α v + α e + ...+ α e 2 2,1 1 2,2 2 2,n n$ jest niezerowy; w przeciwnym przypadku $|v2$ byłby liniowo zależny od $v1.$ Podobnie jak poprzednio, można założyć, że $α 2,2≠ 0,$ oraz uzasadnić, że każdy wektor, który jest kombinacją wektorów $v1,e2,...,en,$ jest też kombinacją wektorów $|v,v ,e ,...,e . 1 2 3 n$

Postępując analogicznie jak powyżej dla $|vi(i = 3,4,5)$ dochodzimy do momentu, w którym wszystkie wektory $|e,...,e 1 n$ zastąpiliśmy przez $|v1,...,vn.$ Ponieważ założyliśmy, że $k > n,$ zatem wektor $|vn+1,$ który potrafimy zapisać za pomocą wektorów $e1,...,en,$ potrafimy również zapisać za pomocą wektorów $|v1,...,vn.$ Jest to jednak sprzeczne z liniową niezależnością wektorów.

Otrzymana powyżej sprzeczność oznacza, że warunek $k > n$ jest niemożliwy do spełnienia.

Twierdzenie 4. W Nieparzystkowie o $n$ mieszkańcach można utworzyć co najwyżej $|n$ stowarzyszeń.

Dowód. Rozważmy zbiór $|Fn. 2$ Każde stowarzyszenie $|S$ reprezentujemy przez jego wektor charakterystyczny $1S$ w $n F2,$ to jest taki wektor, w którym jeśli $P = {1,...,n},$ to $i$ -ta współrzędna wektora $1S$ jest równa 1 wtedy i tylko wtedy, gdy $i ∈S.$ W przeciwnym przypadku $|i$ -ta współrzędna jest równa 0. Powiedzmy, że tych wektorów jest $|k.$

Wektory postaci $1 S$ są liniowo niezależne. Aby to uzasadnić, załóżmy, że

z = α11S1 + ...+ αk1Sk = 0,

i rozważmy iloczyn skalarny $|1S`⋅z$ dla pewnego $Sℓ$ (dowolnego; $|ℓ∈ {1,...,k}$ ). Zauważmy, że:

$1Si⋅1Si = 1$ (liczba członków stowarzyszenia jest nieparzysta) - iloczyn skalarny obliczamy modulo 2 (patrz tabele na marginesie),
$1Si⋅1Sj = 0$ dla $i ≠ j$ (część wspólna stowarzyszeń jest parzysta).

Wynika z tego, że

0 = z⋅1S` = α11S11S` + ...+α k1Sk1S` = αℓ.

Rozważając kolejne $ℓ = 1,...,k,$ otrzymujemy $|α1 = ... = αk = 0,$ a więc wektory $|1S1,...1Sk$ są liniowo niezależne. Z lematu wynika teraz, że $|k⩽ n.$

Ostatni krok to pokazanie, że można utworzyć dokładnie $n$ stowarzyszeń. W tym celu wystarczy, aby każde stowarzyszenie złożone było z jednego mieszkańca.

Na zakończenie

Wróćmy do ogólnego problemu. Jak już wspomnieliśmy, nie istnieje ogólny wzór na $m(n,$ W twierdzeniu 3 wskazane zostało dolne oszacowanie. Ciekawe natomiast jest także znalezienie szacowania górnego. Wskazujemy je w poniższym twierdzeniu.

Twierdzenie 5. Zachodzą nierówności:

$m(n,$ gdzie $Ω$ jest krotnością czynników pierwszych w rozkładzie liczby $ℓ.$
$m(n,$
dla $|ℓ⩽ 166$ zachodzi $m(n,$
dla $|ℓ⩾ 167$ zachodzi $m(n,$

Ciekawostką jest fakt, że w dowodzie trzeciego z powyższych oszacowań wykorzystuje się tak zwane macierze Hadamarda (macierze kwadratowe o wymiarze $4 ℓ× 4ℓ$ o tej własności, że ich wyrazami są tylko 1 oraz -1 i iloczyny skalarne wszystkich możliwych par wierszy są równe 0). Wiadomo, że takie macierze istnieją dla wszystkich $|ℓ⩽ 166$ oraz dla wszystkich liczb postaci $|2k,$ gdzie $k$ jest dodatnią liczbą naturalną.