warunek Halla

pumbosza · Post autor: **pumbosza** » 25 lis 2009, o 17:31

Witam mam taki problem z zadaniem w którym należy skorzystać z warunku Halla:

Pokazać, że w grupie n pań i m panów istnieje k pań ,którym można znaleźć mężów wtedy i tylko wtedy gdy ,dowolny podzbiór pań (powiedzmy r-elementowy) lubi co najmniej k+r-n panów.

Dumel · Post autor: **Dumel** » 25 lis 2009, o 20:52

to nie jest prawda. weźmy np. k=2, n=m=r=1.
pani A zna pana X
pani B nie zna nikogo
podzbiór jednoelementowy składający się z pani B nie zna nikogo a mimo to A z X można zeswatać

micha?1899 · Post autor: **micha?1899** » 6 kwie 2010, o 14:11

Dumel pisze:to nie jest prawda. weźmy np. k=2, n=m=r=1.
pani A zna pana X
pani B nie zna nikogo
podzbiór jednoelementowy składający się z pani B nie zna nikogo a mimo to A z X można zeswatać

Tylko jeden błąd w twoim rozumowaniu. Jak wybierasz 2 panie skoro zakładasz że jest jedna? (k=2 a n=1)