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.

Gammel kjent oppgave

Innlegg mrcreosote » 05/10-2007 17:37

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.
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Innlegg daofeishi » 05/10-2007 18:19

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.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 60 gjester

cron