Festyn

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

Festyn

Post autor: półpasiec »

Na festyn przyszly 2002 osoby. W kazdej grupie skladajcej sie z 1001 osob jest taka sama liczba par osob N>0, ktore sie znaja (jesli A zna B, to B zna A). Ile co najmniej par znajomych jest wsrod tych 2002 osob.
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

Festyn

Post autor: _el_doopa »

na razie mam taki trywialny fakt ze kazdy zna tyle samo osob,... ale na to pewnie juz wpadles

dowod.
wezmy osoby A i B razem z tysiacem innych kazda tworzy grupe, wobec tego maja po tyle samo znajomych wsrod tych 1000, analogicznie z drugim tysiacem a sami albo sie znaja albo nie, skad A i B maja tyle samo znajomych.
półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

Festyn

Post autor: półpasiec »

w zasadzie mam rozwiazanie, tylko ze troche nie rozumiem polecenia, bo jest w tresci dodatkowo podane, ze im wieksza liczba tym lepsza ocena, bo to zadanie z austropolu druzynowego, ale mi wychodzi, ze wystarczy, ze osoby beda mialy tyle samo znajomych i juz beda warunki spelnione, to juz nie wiem, o co chodzi.
Niech i-ta osoba zna \(\displaystyle{ x_i}\) osob. Dla kazdego podzbioru P 1001 elementowego zbioru M={1,2,...2002} mamy \(\displaystyle{ \bigsum_{i \in P}x_i = \bigsum_{i \in M/P} x_i}\) Istotnie, wszystkich znajomosci, ktore trafiaja w ten sam zbior jest z zalozenia tyle samo, natomiast jesli osoba z jednej grupy zna kogos z pozostalej, to tamta tez ja zna, wiec wszystkie liczby sie redukuja. Rownosc dziala dla kazdego podzbioru, wiec wszystkie liczby x sa rowne. Z drugiej strony mozliwe jest zeby dla kazdego \(\displaystyle{ q \in \{1,2,...2001 \}}\) kazda osoba znala q osob, wystarczy posadzic je przy okraglym stole i odpowiednio dobrac ilosc osob, ktore ma znac. Po drugie dla kazdego takiego q istnieje tyle samo par. Zalozmy przeciwnie. Niech przy pewnym podziale w jednej grupie bedzie wiecej par - w jednej m, drugiej n i m>n. Z kazdej grupy wychodzi 1001q krawedzi, jesli teraz w jednej 2m krawedzi trafia w te sama grupe, to 1001q-2m krawedzi trafia w pozostala grupe. Natomiast z tamtej 1001q-2n krawedzi trafia w grupe przeciwna, ale wielkosci te nie sa rowne a powinny, wiec sprzecznosc.
Czy ktos moze powiedziec, czy to dobre jest w ogole??
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

Festyn

Post autor: _el_doopa »

u ciebie chyba tylko przy dowolnym rozdziale na 2 podzbiory maja taka sama ilosc par znajomych. a tu wszystkie maja miec tyle samo czy wezme A1 .... A1001
czy A2 ..... A1002 czy dowolne inne ,
jesli dobrze zrozumialem
półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

Festyn

Post autor: półpasiec »

no dla kazdego jednego i jego dopelniajacego maja taka sama sume, ale jesli wezmiemy jeden x z jednego i jeden z drugiego, to bedzie tez rownosc, dodajac stronami reszta sie zredukuje i dostaniemy, ze x z jednego i x z drugiego tez sa rowne, analogicznie dostajemy rownosc wszystkich
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

Festyn

Post autor: _el_doopa »

to niech kazdy zna jednego
A1 zna A2
A3 zna A4
....
A2001 zna A2002

i jak rozdzielam na 2 podzbiory to owszem zawsze maja te sama ilosc par znajomych
ale co innego otrzymam jak wezme samych nieparzystych a co innego jak wezme powiedzmy pierwszych 1001
półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

Festyn

Post autor: półpasiec »

racja racja, to dziala tylko dla dopelniajacych sie, ale jest dobry, wiec istotnie kazdy ma taka sama liczbe znajomych, niech to bedzie liczba k.
Rozwazmy dwa przypadki
1) k== 1002. Wezmy teraz grupe 1000 osob M, ze pewna osoba zna z niej kazdego. Podobnie jak wyzej pokazujemy, ze kazdy zna z niej kazdego, iech ta grupa osob, ktore znaja z M kazdego to W. Wezmy 999 z M. Niech wsrod nich bedzie d par. Bierzemy pare osob, ktora sie zna z W. Mamy teraz d + 999 + 999+1 par. Jesli natomiast wezmiemy pare osob, ktora sie nie zna z W i ten sam podzbior M, to uzyskamy w niej d+999+999 par. Sprzecznosc, zatem nie moze istniec sytuacja taka, ze pewne dwie osoby sie nie znaja. Zatem taka sytuacja ma miejsce wtedy i tylko wtedy, gdy kazdy zna kazdego.

Troche sie zastanawiam nad tym, czy nie mozna byloby uznac, ze ta sytuacja jest symetryczna, zachodzi dla k wtedy i tylko wtedy gdy zachodzi dla 2002-k, no bo jak znajomych polaczymy biala krawedzia, a nieznajomych czarna, to i tak zalezec nam bedzie tylko na rownej liczbie krawedzie wszedzie, wiec zamieniajac kolory krawedzi uzyskamy sytuacje symetryczna wzgledem k. Wtedy mozna byloby robic tylko dowod dla k mniejszego od 1002. Czy poprawne by to bylo??
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

Festyn

Post autor: _el_doopa »

No jak dla mnie to byłoby to bardzo sprytne i poprawne jaknajbardziej.
Jak sie poprzednio znali to sie teraz nie znaja, a skoro liczba par znajomych jest stala w kazdym zbiorze mocy 1001 to par nieznajomych tez jest stala.
ODPOWIEDZ