Matematyka.pl

Udowodnić, że jeśli istnieje system trójek Steinera rzędu \(\displaystyle{ n}\), to \(\displaystyle{ n}\) przy dzieleniu przez \(\displaystyle{ 6}\) daje resztę \(\displaystyle{ 1}\) lub \(\displaystyle{ 3}\).

Rodzinę zbiorów - trzyelementowych podzbiorów zbioru \(\displaystyle{ n}\) elementowego \(\displaystyle{ X}\) nazywa się systemem trójek Steinera rzędu \(\displaystyle{ n}\), jeśli każde dwa różne elementy \(\displaystyle{ X}\) należą do dokładnie jednej takiej trójki.

Dodano po 6 minutach 9 sekundach:

Skoro wybrany element z X wystąpi w trójkach z każdym z pozostałych elementów to n musi być liczbą nieparzystą (wybrany element i pary pozostałych elementów).
Gdy \(\displaystyle{ n=2k+1}\) to wybrany element wystąpi w \(\displaystyle{ k}\) trójkach, a trójek powinno być \(\displaystyle{ \frac{(2k+1)k}{3}}\). Ułamek ten jest liczbą całkowitą gdy \(\displaystyle{ 2k+1=3p}\) (a wtedy nieparzyste n jest podzielne przez 3 więc w dzieleniu przez 6 daje resztę 3) lub \(\displaystyle{ 2k+1=3p}\) (a wtedy \(\displaystyle{ n=6p+1}\) więc w dzieleniu przez 6 daje resztę 1).

Zauważmy, że jeżeli wszystkich par w takim zestawie jest:

\(\displaystyle{ {n \choose 2} = \frac{n(n-1)}{2} }\)

w każdej trójce jest trzy pary, więc wszystkich trójek musi być:


\(\displaystyle{ \frac{n(n-1)}{6} }\)

łatwo też zauważyć, że trójek w których zawarta jest np. cyfra \(\displaystyle{ a}\), np. \(\displaystyle{ a=1}\) jest ich dokładnie:

\(\displaystyle{ \frac{n-1}{2} }\)

Z zasady włączania i wyłączania ilość trójek w , których występuje: \(\displaystyle{ a \vee b \vee c}\) jest:

\(\displaystyle{ |a \cup b \cup c|= a+b+c-ab-ac-bc+abc=3 \cdot \frac{n-1}{2} -3 \cdot 1+1= \frac{3n-7}{2} }\)

Wyjaśnię jak napisałem wcześniej , trójek w których jest jena cyfra jest ich: \(\displaystyle{ \frac{n-1}{2} }\)

siłą rzeczy trójek w których są dwie lub trzy cyfry: \(\displaystyle{ ab \vee abc}\) jest siłą rzeczy po jednej stąd te liczby...

a trójek w których nie występuje żadna z liczb: \(\displaystyle{ a,b,c}\) siłą rzeczy musi być:

\(\displaystyle{ \frac{n(n-1)}{6} - \frac{3n-7}{2} = \frac{n^2-10n+21}{6} = \frac{(n-3)(n-7)}{6} }\)

oczywiście góra musi się dzielić przez \(\displaystyle{ 6}\), żeby to wyrażenie było całkowite...

czyli, że:

\(\displaystyle{ (r-3)(r-7)=0 \mod 6}\)

lub:

\(\displaystyle{ (r-3)(r-1)=0 \mod 6}\)

z tego widać, że reszta musi wynosić: \(\displaystyle{ 1 \vee 3}\)

znaczy to, że:

\(\displaystyle{ n=6k+1 \vee n=6k+3}\)

cnd...

Działa to dla np.:

\(\displaystyle{ n=3,7}\)