Gammel kjent oppgave
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
La [tex]x_1,x_2,\dots,x_n\in\{-1,1\}[/tex] slik at [tex]x_1x_2x_3x_4+x_2x_3x_4x_5+\dots+x_{n-1}x_nx_1x_2+x_nx_1x_2x_3=0[/tex]. Vis at n er delelig med 4.
Jeg har faktisk ikke sett denne oppgaven før, men moro var den.
Representer tallene med n-tuppelen (x[sub]1[/sub], ... , x[sub]n[/sub])
La summen over være S(x[sub]1[/sub], ... , x[sub]n[/sub]).
Vi konstruerer en hvilken som helst n-tuppel ved å starte med (1, ..., 1), og forandre gitte komponenter til -1. Vi legger merke til at bytte av et enkelt komponent vil skifte paritet på 4 ledd i S. Forandringen vil enten legge til eller trekke fra 2 fra hvert ledd vi har forandret.
Vi har følgende muligheter:
Fire (-1)-ledd skifter paritet: S -> S + 8
Tre (-1)-ledd og ett 1-ledd skifter paritet: S -> S + 4
To (-1)-ledd og to 1-ledd skifter paritet: S -> S
Ett (-1)-ledd og to 1-ledd skifter paritet: S -> S - 4
Fire 1-ledd skifter paritet: S -> S - 8
Dermed ser vi at S(x[sub]1[/sub], ... , x[sub]n[/sub]) er invariant modulo 4. Uansett n-tuppel, vil S(x[sub]1[/sub], ... , x[sub]n[/sub]) = n (mod 4).
Derfra følger at n må være kongruent til 0 modulo 4 dersom summen skal være 0, og vi er i mål.
Representer tallene med n-tuppelen (x[sub]1[/sub], ... , x[sub]n[/sub])
La summen over være S(x[sub]1[/sub], ... , x[sub]n[/sub]).
Vi konstruerer en hvilken som helst n-tuppel ved å starte med (1, ..., 1), og forandre gitte komponenter til -1. Vi legger merke til at bytte av et enkelt komponent vil skifte paritet på 4 ledd i S. Forandringen vil enten legge til eller trekke fra 2 fra hvert ledd vi har forandret.
Vi har følgende muligheter:
Fire (-1)-ledd skifter paritet: S -> S + 8
Tre (-1)-ledd og ett 1-ledd skifter paritet: S -> S + 4
To (-1)-ledd og to 1-ledd skifter paritet: S -> S
Ett (-1)-ledd og to 1-ledd skifter paritet: S -> S - 4
Fire 1-ledd skifter paritet: S -> S - 8
Dermed ser vi at S(x[sub]1[/sub], ... , x[sub]n[/sub]) er invariant modulo 4. Uansett n-tuppel, vil S(x[sub]1[/sub], ... , x[sub]n[/sub]) = n (mod 4).
Derfra følger at n må være kongruent til 0 modulo 4 dersom summen skal være 0, og vi er i mål.