Julekalender #7

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
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

En sirkel kuttes i seks sektorer (som en pizza), og du skriver tallene 1,0,1,0,0,0 klokkevis, ett tall i hver sektor. Følgende operasjon er tillatt: du velger deg ut to sektorer som ligger inntil hverandre og legger til 1 til hver av de to tallene som står der fra før av.

Er det mulig å få alle sektorene til å inneholde samme tall?
alund
Noether
Noether
Innlegg: 48
Registrert: 31/03-2017 21:40

Der er sikkert en fin løsning med paritet eller noe sånt, men jeg løste den slik:

Sektor 1,2,3,4,5,6 har henholdsvis 1,0,1,0,0,0. Lar [tex]a[/tex] være antall operasjoner utført på 1 og 2, og likeså med [tex]b[/tex] på 2 og 3, [tex]c[/tex] på 3 og 4, [tex]d[/tex] på 4 og 5, [tex]e[/tex] på 5 og 6, og [tex]f[/tex] på 6 og 1.

For at tallene i sektorene skal bli like, må vi ha
[tex]f+a+1=a+b=b+c+1=c+d=d+e=e+f[/tex].
Da gir fjerde likhet [tex]c=e[/tex] og siste uttrykks likhet med det første gir [tex]e=a+1[/tex].
Andre likhet gir [tex]a=c+1[/tex], men [tex]c+1=e+1=a+1+1=a+2[/tex], som da gir [tex]a=a+2[/tex], som er umulig.

Nei er altså svaret jeg kom frem til. Riktig?
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Representér tilstanden ved multippelen $a_i=(a_1,a_2,...,a_6)$, og definér funksjonen $f(a_i)=a_1-a_2+a_3-a_4+a_5-a_6$. Da er $f$ invariant og lik $f(1,0,1,0,0,0)=2$. Anta at alle tallene er like, dvs. $a_i=n$ for et positivt heltall $n$, men da er $f(n,n,n,n,n,n)=n-n+n-n+n-n=0\neq 2$, så det er umulig at alle tallene er like.
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

Helt riktig, både alund og Gustav!
alund skrev:Der er sikkert en fin løsning med paritet eller noe sånt
Ja, dette er en invariant-oppgave. Trikset er å finne et uttrykk (eller en egenskap) som ikke endrer seg, uansett hvordan man utfører operasjonene. Og så vise at invarianten har forskjellig verdi for start-tilstanden og ønsket slutt-tilstand. Altså er det umulig å nå slutt-tilstanden fra den gitte start-tilstanden.

I denne oppgaven ser vi at verdien til uttrykket $I = x_1 - x_2 + x_3 - x_4 + x_5 - x_6$ (der $x_i$ er tallet i sektor $i$) aldri vil endre seg, uansett hvordan vi utfører operasjonene. Siden $I=2$ til å begynne med, og den nødvendigvis må være $I=0$ når vi har like tall i sektorene, kan vi aldri nå ønsket slutt-tilstand ved utelukkende å anvende den lovlige operasjonen.

Men som du viste selv: vi kan også løse oppgaven ved å anta at vi har oppnådd slutt-tilstanden og så vise at dette leder til en selvmotsigelse!
Svar