szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 sty 2018, o 17:33 
Użytkownik

Posty: 29
Lokalizacja: A kto to wie
Mamy daną grupę n dziewcząt i m chłopców. Pokaż, że warunkiem koniecznym i dostatecznym na to, by k dziewcząt mogło znaleźć męża (wewnątrz grupy), jest to, by każde r dziewcząt znało przynajmniej k+r-n chłopców.

Wskazówka: Dodaj n - k chłopców akceptowanych przez wszystkie dziewczyny i zastosuj tw. Halla.

Nie za bardzo rozumiem treść tego zadania. Twierdzenie Halla mówi, że warunkiem koniecznym i warunkiem wystarczającym na to, by istniało takie skojarzenie par, jest to, by każda podgrupa dziewcząt licząca k osób znała co najmniej k chłopców. Wziąłem sobie przykład n=5 , m=6 , k=3 i r=2 . Podstawiając to do zależności, która ma wyjść otrzymałem, że każde r dziewczyn musi znać 0 chłopców, dla r=1 w ogóle otrzymam liczbę ujemną. Gdzie jest błąd w moim rozumowaniu i jak się powinno rozwiązać to zadanie poprawnie?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 21:29 
Użytkownik

Posty: 15
Lokalizacja: Poznań
Dołączam się do pytania
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2018, o 23:22 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
A nie jest czasem konieczne założyć, żeby:

k+r-n>0
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rekurencja -> Czynnik sumacyjny -> problem z ciągiem  dong  0
 Metoda Rabina problem.  smaug14  0
 Problem - drzewko i urny  Oswald  7
 Problem z zadankiem z szachistami  dwukwiat15  1
 Alternatywny dowód twierdzenia Halla  Azamath  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl