Festyn
-
- 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
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.
Festyn
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.
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.
-
- 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
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??
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??
Festyn
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
czy A2 ..... A1002 czy dowolne inne ,
jesli dobrze zrozumialem
-
- 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
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
Festyn
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
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
-
- 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
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??
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??
Festyn
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.
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.