Hej,
Mam takie zadanie, do którego jest wskazówka, ale nadal nie wiem jak.
Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.
Wskazówka jest taka:
Dołożyć \(\displaystyle{ n - k}\) chłopaków, ale tak że każda dziewczyna zna ich wszystkich (nowa sytuacja)
Pokazać, że co najmniej k dziewcząt w starej sytuacji możne znaleźć wszystkich mężów wtw gdy
wszystkie mogą w nowej sytuacji.
No więc ten lemat mogę pokazać:
=>)
To jasne, każda z dziewczyna, która nie znalazła jeszcze męża, na pewno go znajdzie,
bo w nowej sytuacji będzie \(\displaystyle{ n - k}\) chłopaków (każda dziewczyna ich zna)
<=)
To też jasne chyba. Wszystkie dziewczyny znalazły mężów, w nowej sytuacji.
Jeśli "zużyły" wszystkich \(\displaystyle{ n - k}\) "nowych" to wówczas \(\displaystyle{ k}\) musiało być starych
(jeśli zużyły trochę mniej, to więcej "starych" -stąd co najmniej)
Więc jasne, że conajmniej \(\displaystyle{ k}\) dziewcząt można ożenić w starej sytuacji.
Dalej jest wskazówka, żeby zastosować twierdzenie Halla w nowej sytuacji.
Czyli, że można pożenić wtw gdy każdy podzbiór dziewczyn, "razem zna"
nie mniejszy podzbiór chłopaków,
Ale nie wiem jak to dokończyć.
Jakieś wskazówki ?
Graf, twierdzenie Halla
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Graf, twierdzenie Halla
Czy tam nie miało być \(\displaystyle{ k-n+r}\) zamiast \(\displaystyle{ n-k+r}\)? Dla \(\displaystyle{ k=0}\) warunek po prawej stronie powinien być zawsze prawdziwy.matinf pisze: Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Graf, twierdzenie Halla
Tak, masz rację.norwimaj pisze:Czy tam nie miało być \(\displaystyle{ k-n+r}\) zamiast \(\displaystyle{ n-k+r}\)? Dla \(\displaystyle{ k=0}\) warunek po prawej stronie powinien być zawsze prawdziwy.matinf pisze: Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Graf, twierdzenie Halla
To teraz już łatwo możesz udowodnić ostatnią brakującą równoważność: zachodzi warunek Halla w nowej sytuacji wtw dowolny \(\displaystyle{ r}\)-podzbiór dziewcząt zna co najmniej \(\displaystyle{ k - n + r}\) starych (tzn. nie tych dołożonych) chłopców.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Graf, twierdzenie Halla
czyli lemat dobrze pokazałem ?
Ja rozumiem logikę tego dowodu. Na prawdę pokazanie równoważności, o której mówisz da tezę.
Ale tej równoważności nie widzę jak pokazać. Mimo, że jak twierdzisz to łatwe, to wcale nie jest łatwe.
Ja rozumiem logikę tego dowodu. Na prawdę pokazanie równoważności, o której mówisz da tezę.
Ale tej równoważności nie widzę jak pokazać. Mimo, że jak twierdzisz to łatwe, to wcale nie jest łatwe.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Graf, twierdzenie Halla
W jedną stronę mogę spróbować. Załóżmy, że jest spełniony warunek Halla w nowej sytuacji. Chcemy pokazać, że dowolny zbiór \(\displaystyle{ r}\) dziewcząt zna co najmniej \(\displaystyle{ k-n+r}\) chłopaków w starej sytuacji. Dla \(\displaystyle{ r=0}\) (złośliwy przypadek, łatwy do przeoczenia) liczba \(\displaystyle{ k-n+r}\) jest niedodatnia, więc tezę mamy za darmo. Jeśli \(\displaystyle{ r>0}\), to wybrane dziewczęta znają co najmniej \(\displaystyle{ r}\) chłopaków, w tym \(\displaystyle{ n-k}\) nowych. Znają więc co najmniej \(\displaystyle{ r-(n-k)}\) starych.