La [tex]X=\{1,2, \ldots, n \}[/tex]. Finn den minste [tex]m[/tex] slik at det finnes [tex]m[/tex] delmengder [tex]A_1, A_2, \ldots, A_m[/tex] med følgende egenskap:
For ethvert utvalg av to distinkte elementer [tex]a, b \in X[/tex] finnes en i slik at [tex]A_i[/tex] inneholder enten a eller b, men ikke begge.
Mengde av delmenger
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Vi påstår at den minste [tex]m[/tex] er [tex]\min(k|2^k \ge n)[/tex].
Anta vi har funnet oss noen delmenger [tex]A_1,...A_m[/tex] som kanskje eller kanskje ikke fungerer. For enhver [tex]k \in X[/tex], tilegner vi en m-tuppel [tex]T_k[/tex] som er slik at [tex]T_k(j)=1[/tex] hvis [tex]k \in A_j[/tex], og 0 hvis ikke. Legg så merke til at hvis [tex]T_u=T_v[/tex] for distinkte [tex]u,v[/tex], vil [tex]u [/tex]og [tex]v [/tex] være i elementer i nøyaktig samme delmengder, som betyr at ønskede egenskap for delmengdene ikke holder når vi betrakter [tex]u [/tex]og [tex]v[/tex]. Hvis derimot de to m-tuplene er forskjellig for et element [tex]j[/tex], vil nøyaktig en av [tex]u,v[/tex] være i [tex]A_j[/tex], og egenskapen holder for [tex]u [/tex]og [tex]v[/tex]. Vi konkluderer med at delmengdene oppfyller egenskapen hvis og bare hvis alle m-tupler er forskjellige.
Siden det for en gitt [tex]m [/tex] finnes [tex]2^m[/tex] distinkte m-tupler, kan vi klare å finne ønskede delmengder hvis og bare hvis [tex]2^m \ge n[/tex]. Konklusjonen følger.
Anta vi har funnet oss noen delmenger [tex]A_1,...A_m[/tex] som kanskje eller kanskje ikke fungerer. For enhver [tex]k \in X[/tex], tilegner vi en m-tuppel [tex]T_k[/tex] som er slik at [tex]T_k(j)=1[/tex] hvis [tex]k \in A_j[/tex], og 0 hvis ikke. Legg så merke til at hvis [tex]T_u=T_v[/tex] for distinkte [tex]u,v[/tex], vil [tex]u [/tex]og [tex]v [/tex] være i elementer i nøyaktig samme delmengder, som betyr at ønskede egenskap for delmengdene ikke holder når vi betrakter [tex]u [/tex]og [tex]v[/tex]. Hvis derimot de to m-tuplene er forskjellig for et element [tex]j[/tex], vil nøyaktig en av [tex]u,v[/tex] være i [tex]A_j[/tex], og egenskapen holder for [tex]u [/tex]og [tex]v[/tex]. Vi konkluderer med at delmengdene oppfyller egenskapen hvis og bare hvis alle m-tupler er forskjellige.
Siden det for en gitt [tex]m [/tex] finnes [tex]2^m[/tex] distinkte m-tupler, kan vi klare å finne ønskede delmengder hvis og bare hvis [tex]2^m \ge n[/tex]. Konklusjonen følger.
