Gammel kjent oppgave

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
mrcreosote
Guru
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.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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.
Svar