Maksimer antall delmengder

[daofeishi]

La n være et positivt partall. Ta for deg mengden {1, 2, ..., n}. Hva er det absolutt største antall delmengder du kan plukke fra dette settet slik at:
- Hver delmengde inneholder et odde antall elementer
- For hvert par av delmengder du har plukket ut vil snittet av dem inneholde et partall antall elementer.

[mrcreosote]

Identifiser elementene i potensmengden til {1,2,...,n} med vektorer i [tex]V=\mathbb{Z}_2^n[/tex]. For eksempel svarer {1,3,4} til 1011 hvis n=4 og 101100 hvis n=6. Hvis vektorrommet V over [tex]\mathbb{Z}_2[/tex] har vanlig skalarprodukt, har den største ortogonale mengden av vektorer med norm ulik 0 i V, dette svarer til delmengder med et odde antall elementer, n elementer. (Jeg kan ikke gå helt god for dette, ting blir litt merkelige over kropper av positiv karakteristikk noen ganger.) En mulig slik mengde er standardbasisen for V, så svaret er n.

Edit: Innlegget er endra noe.

[mrcreosote]

Har du en mer elementær måte å gå fram på?

[daofeishi]

Stemmer så klart det her! Oppgaven var en øvingsoppgave vi fikk i lin. alg. klassen vår (med tilhørende hint), så jeg har ikke kjennskap til noe annet bevis. Kan vi klare å finne det?