metoda probabilistyczna
-
bazyl01
- Użytkownik
- Posty: 46
- Rejestracja: 12 cze 2023, o 20:27
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 5 razy
metoda probabilistyczna
Niech \(\displaystyle{ m_3(n)}\) oznacza najmniejszą liczbę \(\displaystyle{ m}\), dla której istnieje rodzina \(\displaystyle{ E_1,E_2,...,E_m}\) zbiorów \(\displaystyle{ n-}\)elementowych taka, że jakkolwiek pokolorujemy trzema kolorami elementy tych zbiorów, to zawsze znajdziemy zbiór \(\displaystyle{ E_j,\,\,j=1,2,3,...,m,}\) w którym nie występuje jeden z kolorów. Znajdź oszacowanie dolne na \(\displaystyle{ m_3(n).}\)
-
arek1357
Re: metoda probabilistyczna
Przecież kolorować to ja sobie mogę jak chcę...nawet mogę wszystko pokolorować na jeden kolor..., chyba , że wyraźnie jest zaznaczone, że muszę użyć wszystkich kolorów...
-
bazyl01
- Użytkownik
- Posty: 46
- Rejestracja: 12 cze 2023, o 20:27
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 5 razy
Re: metoda probabilistyczna
Kolor jest wybierany losowo każdy z prawdopodobieństwem równym \(\displaystyle{ \frac{1}{3}.}\)
-
arek1357
Re: metoda probabilistyczna
Czemu ma nie występować, załóżmy, że mamy 4 zbiory w każdym trzy elementy i elementy każdego ze zbiorów będą pokolorowane w trzech kolorach, i w każdym zbiorze każdy kolor wystąpi...zawsze znajdziemy zbiór
w którym nie występuje jeden z kolorów.
No chyba, że zbiory są dwuelementowe...