[Kombinatoryka] rodzina

[mol_ksiazkowy]

Dana jest pewna rodzina dwu elementowych podzbiorów zb. liczb naturalnych.Nawijmy ją sobie A.Udowodnij ze istnieje pewien taki nieskończony zbiór M, zawarty w N, iz albo wszystkie dwu-element. podzbiory zbioru M należa do A, albo żaden nich nie należy. Czy taki zbior jest jedyny....?!

[arek1357]

Nie bardzo rozumiem ale weźmy :
A={{1,2}{4,5}{7,8},...}
wtedy raczej chyba trudno znaleźdź taki M
bo jeśli np 1,2,3 e M to
{1,2}eA a np {1.3}nie naley do A
i trudno znaleźdź taki M żeby wszystkie jego 2 elementowe podzbiory należały do A

[mol_ksiazkowy]

Arek1357 napisał:

Nie bardzo rozumiem ale weźmy :
A={{1,2}{4,5}{7,8},...}

wtedy mamy M={3,6,9,.....} ...ok?!

[arek1357]

czyli żaden wtedy dwuelement zbioru M nie należy do A

[mol_ksiazkowy]

no tak...mozna tez wziasc dowolny jego niesk podzbior....

[arek1357]

Jeśli M będzie skończony to może się zawierać
a gdyby M był nieskończony to wtedy A musi zawierać wszstkie kombinacje par:
jeśli np do dwuelementów należy a1,a2 a3,...
to elementami A muszą być wszstkie kombinacje podwójne elementów
ai aj gdzie ij czyli {ai,aj}

[mol_ksiazkowy]

hmmmmm nieco tego nie kumam....bo jesli do M dobierasz A , to chyba nie ten kierunek...mogłbys ciut uscicłic?!jaka jest twoja idea...?

[arek1357]

To znaczy ja tak nie do końca dobieram do M A
ale głośno myślę nad tym jak może wyglądać zbiór M
i jeśli rodzina A składa się s par np typu:
A={{1,2}{4,5}{7,8},...}

do tego dobieramy M np M={3,6,...}
i wtedy dwupodzbiory M nie zawierają się w A
ale jeśli A zawiera wszystkie możliwe pary dwu - podzbiorów
to do M można dobrać dowolne elementy wzięte z dwupodzbiorów A
i wtedy dwuelementy M zawierają się w A

[przemk20]

zadanie sprowadza sie do wykazania...
jesli k to liczba przywitan wsrod n osob, gdzie \(\displaystyle{ k \geq \frac{n(n-1)}{4}}\) zas m max liczba osob jakie da sie ustawic przy okraglym stole tak zeby wszyskie sie miedzy soba przywitaly, to dla \(\displaystyle{ n \to \infty, \ \ m \to \infty}\)