Fyrstikklek

[daofeishi]

På et bord ligger m fyrstikker og en ladd revolver. Du og en venn sitter tvers overfor hverandre, og spiller et spill etter følgende regler: Når det er din tur kan du fjerne 1, 2..., (n-1) eller n fyrstikker fra bordet, etter ditt eget valg. Den personen som fjerner siste fyrstikk plukket opp revolveren og fyrer av et velrettet skudd over bordet. Finn et uttrykk som bestemmer om du eller vennen din bør begynne hvis du har lyst til å overleve spillet.

[moth]

Hvis [tex]n=m[/tex] så vil jeg begynne

[Charlatan]

Du vil begynne hvis [tex]m \not \equiv 0 (\rm{mod}(n+1))[/tex].

Kommer med bevis senere.

[Charlatan]

[tex]P(s)[/tex] er "Hvis [tex]m=s(n+1)[/tex], så vil begynneren tape [tex]\ s \in \mathbb{Z}^+[/tex]".

[tex]P(1)[/tex]: La [tex]s=1 \Rightarrow m=n+1[/tex]. Begynneren velger et antall mellom [tex]1[/tex] og [tex]n[/tex] han skal trekke, og dermed vil det resterende antallet være mellom [tex]1[/tex] og [tex]n[/tex], så nestemann vil vinne [tex]\Rightarrow[/tex] begynneren vil tape [tex]\Rightarrow P(1)[/tex] er sant.

Anta at [tex]P(k)[/tex] er sant. Dvs [tex](m=k(n+1) \Rightarrow[/tex] Begynneren taper).

Hvis [tex]s=k+1 \Rightarrow m=(k+1)(n+1)=k(n+1)+(n+1)[/tex]. Begynneren må nå velge et antall fyrstikker mellom [tex]1[/tex] og [tex]n[/tex] som etterlater [tex]m_1=k(n+1)+r[/tex], [tex]( 1\leq r \leq n )[/tex] fyrstikker. Hvis nestemann nå velger bort [tex]r[/tex] fyrstikker, vil begynneren tape ifølge av at [tex]P(k)[/tex] er sant. Dermed følger det av induksjonsprinsippet at Hvis [tex]m=s(n+1)[/tex], så vil begynneren tape.

Hvis nå [tex]m=s(n+1)+r, (1 \leq r \leq n, \ s \in \mathbb{Z}^+ \cup \{ 0\} )[/tex] så kan begynneren velge bort [tex]r[/tex] fyrstikker, og dermed vil [tex]P(s)[/tex] ([tex]s \not = 0[/tex])implisere at nestemann taper. Da vinner begynneren.
Hvis [tex]s=0[/tex], så vil det å ta bort [tex]r[/tex] fyrstikker automatisk gjøre at begynneren vinner.

Vi har nå dekket alle mulige verdier av [tex]n[/tex].

Dermed har vi følgende:

Du bør ikke begynne hvis [tex]m \equiv 0 (\rm{mod} (n+1))[/tex], men du bør begynne hvis ikke.

Jeg anbefaler ikke å spille dette spillet mot en venn!

[Karl_Erik]

Antar daofeishi med 'et velrettet skudd over bordet' mener at den som tar den siste fyrstikken skyter motstanderen - dvs at å ta den siste fyrstikken gjør at man vinner. Eller har jeg misforstått oppgaven?

[meCarnival]

Det er slik jeg også oppfatter den... Men dette er et høyere nivå for meg å regne ut hvertfall

[Charlatan]

Antar daofeishi med 'et velrettet skudd over bordet' mener at den som tar den siste fyrstikken skyter motstanderen - dvs at å ta den siste fyrstikken gjør at man vinner. Eller har jeg misforstått oppgaven?

Det gikk jeg også ut ifra.
Mente du at jeg har gjort en feil? Jeg skjønte ikke helt...

[Karl_Erik]

Whoops. I går så det ut som om du hadde misforstått oppgaven og regnet ut når man burde begynne for ikke å ta den siste fyrstikken, men i dag ser jeg at jeg var på villspor. Får bare beklage og eventuelt skylde på klokkeslettet.

[daofeishi]

Stemmer så klart dette, Jarle.

[Charlatan]

Oppfølger: Finn den vinnende strategien.

[BMB]

Den vinnende strategien her blir vel bare å hele tiden redusere antall brikker på bordet til et multippel av n+1.

[Charlatan]

Jepp.