Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://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.
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).
Re: Trójki Steinera
: 9 lut 2024, o 21:50
autor: arek1357
Zauważmy, że jeżeli wszystkich par w takim zestawie jest: