[Kombinatoryka] Rodzina podzbiorów
: 21 gru 2006, o 01:53
Ze zbioru n>2 -elementowego wybrano \(\displaystyle{ 2^{n-1}}\) róznych podzbiorów,ale takich ze kazde trzy z nich maja element wspólny. Wykaz ze wtedy wszystkie te podzbiory maja elemnt wspolny.
Uwaga: interesuja mnie rozne sposoby/metody rozwiazania problemu jak tez jego ewntualne uogolnienia.
[ Dodano: 23 Sierpnia 2008, 12:12 ]
Zbior X jest dany . Rodzina \(\displaystyle{ S}\) liczy \(\displaystyle{ 2^{n-1}}\) tj połowe podzbiorów X. Druga polowe stanowia ich dopełnienia tj zbiory \(\displaystyle{ A^C}\) gdzie \(\displaystyle{ A \in S}\). Tak wiec mamy \(\displaystyle{ A \in S}\) wtedy i tylko wtedy gdy \(\displaystyle{ A^C \notin S}\), Teza jest jasna gdy w \(\displaystyle{ S}\) jest jakis zbior jednoelementowy \(\displaystyle{ \{x_0\}}\). Załozmy ze takich zbiorow nie ma i dojdziemy do sprzecznosci. Wezmy wiec -zbior A najmniejszej mocy k>1 w \(\displaystyle{ S}\).i niech \(\displaystyle{ x_0 \in A}\) Wtedy mamy \(\displaystyle{ A \cap (A-\{x_0\})^C \cap \{ x_0\}^C = \emptyset}\). z tego juz wynika ze zbior A po usunieciu z niego x0 tez nalezy do \(\displaystyle{ S}\). sprzecznosc
Interesujace jest problem dualny
Ze zbioru n>2 -elementowego wybrano f(n) róznych podzbiorów,ale takich ze kazde dwa z nich maja element wspólny. Wykaz ze wtedy wszystkie te podzbiory maja elemnt wspolny. Jesli nie mozna f(n) w ogolnej sytuacji znalezc to rozwiazac dla ustalonego n np n=7 .
Uwaga: interesuja mnie rozne sposoby/metody rozwiazania problemu jak tez jego ewntualne uogolnienia.
[ Dodano: 23 Sierpnia 2008, 12:12 ]
Zbior X jest dany . Rodzina \(\displaystyle{ S}\) liczy \(\displaystyle{ 2^{n-1}}\) tj połowe podzbiorów X. Druga polowe stanowia ich dopełnienia tj zbiory \(\displaystyle{ A^C}\) gdzie \(\displaystyle{ A \in S}\). Tak wiec mamy \(\displaystyle{ A \in S}\) wtedy i tylko wtedy gdy \(\displaystyle{ A^C \notin S}\), Teza jest jasna gdy w \(\displaystyle{ S}\) jest jakis zbior jednoelementowy \(\displaystyle{ \{x_0\}}\). Załozmy ze takich zbiorow nie ma i dojdziemy do sprzecznosci. Wezmy wiec -zbior A najmniejszej mocy k>1 w \(\displaystyle{ S}\).i niech \(\displaystyle{ x_0 \in A}\) Wtedy mamy \(\displaystyle{ A \cap (A-\{x_0\})^C \cap \{ x_0\}^C = \emptyset}\). z tego juz wynika ze zbior A po usunieciu z niego x0 tez nalezy do \(\displaystyle{ S}\). sprzecznosc
Interesujace jest problem dualny
Ze zbioru n>2 -elementowego wybrano f(n) róznych podzbiorów,ale takich ze kazde dwa z nich maja element wspólny. Wykaz ze wtedy wszystkie te podzbiory maja elemnt wspolny. Jesli nie mozna f(n) w ogolnej sytuacji znalezc to rozwiazac dla ustalonego n np n=7 .