Archief - Wiskunde sterke inductie

Beste,

Ik heb eind deze week een examen van wiskunde en ik zit bij één oefening nog steeds vast ik vind de oplossing maar niet.

Het gaat over het spelletje met staafjes stel er liggen 2 stappels met staafjes op de tafel allebei even veel. Om de beurt mag speler 1 en speler 2 een staafje nemen. Nu moet ik bewijzen met sterke inductie dat als speler 2 deze tactiek volgt: als speler 1 m staafjes neem, neem dan zelf ook m staafjes. Als hij dit zou volgen dan zou hij altijd het laatste staafje nemen en wint hij het spelletje.

Nu ik was begonnen met een base case van 1 maar dan loop ik al vast. Kan iemand mij helpen hierbij?

Met vriendelijke groeten,

Maar als hij direct alle staafjes neemt is hij direct gewonnen en is speler 1 een oen!

Wij moesten in het zesde iets gelijkaardigs programmeren op het GRM.
De clou zit er hem in dat als ge max m staafkes moogt nemen, en de ene neemt er bv n, gij er m-n+1<m kunt nemen. Op deze manier gaan er beurtelings m+1 staafkes weg, en dus moet de eerste proberen k staafjes weg te nemen zodanig, dat als er telkens m+1 weggaan er 1 zal overblijven. Op die manier zou hij het spel automatisch moeten winnen.
Hopelijk zijt ge iets wijzer geworden door mijn uitleg

Oké bedankt. Ik zal eens kijken op WisFaQ.

Woestijnvos zei:

Wij moesten in het zesde iets gelijkaardigs programmeren op het GRM.
De clou zit er hem in dat als ge max m staafkes moogt nemen, en de ene neemt er bv n, gij er m-n+1<m kunt nemen. Op deze manier gaan er beurtelings m+1 staafkes weg, en dus moet de eerste proberen k staafjes weg te nemen zodanig, dat als er telkens m+1 weggaan er 1 zal overblijven. Op die manier zou hij het spel automatisch moeten winnen.
Hopelijk zijt ge iets wijzer geworden door mijn uitleg

Klik om te vergroten...

Er staat toch dat ze allebei evenveel staafjes wegnemen ?

Vegitoo zei:

Er staat toch dat ze allebei evenveel staafjes wegnemen ?

Klik om te vergroten...

Hij beweert toch ergens dat speler 1 m staafjes kan wegnemen

stap 1: basisgeval

Bij 1 - 1 moet A zijn laatste staafje wegnemen, waarna B hetzelfde doet. A heeft als eerste zijn laatste staafje weggenomen

Stap 2: stel dat dit opgaat voor alle strikt positieve k kleiner of gelijk aan N, dan valt te bewijzen dat dit opgaat voor N+1.

De situatie is (N+1) - (N+1) en A heeft de vrije keuze om M staafjes weg te nemen. Onder de voorwaarde dat M>1 kom je dus na weglegging van de staafjes van speler B uit op (N-M+1) - (N-M+1).

geval 1: N-M+1 <0. Dit is een randgeval waaruit blijkt dat speler A maar de keuze heeft om maximaal al zijn staafjes weg te nemen. Indien deze voorwaarde niet opgenomen wordt, geldt het wiskundig bewijs niet (je zou 'oneindig lang' negatief verder kunnen werken).

geval 2: N-M+1 = 0: A heeft al zijn staafjes weggenomen en B is hierin gevolgd. A heeft als eerste zijn laatste staafje weggenomen. Let op: dit geval moet apart bekeken worden omdat hierin niet naar het basisgeval gegaan wordt!

geval 3: N-M+1 > 0: doordat M>=1 weten we dat N-M+1 <=N. Aangezien N-M+1 > 0, zitten we dus in een situatie K - K met K strikt positief en <=N. De inductiehypothese die we namen is dat voor deze gevallen A als eerste zijn laatste staafje zal moeten wegleggen.

Samen volgt hieruit dat dit ook geldt voor de situatie (N+1) - (N+1) indien dit geldt voor alle strikt positieve k kleiner of gelijk aan N. Het basisgeval is de kleinst mogelijke N waarvoor er dergelijke strikt positieve k bestaan en hieruit volgt door inductie dat dit bewezen is voor alle N>0.

Dobbelsteen zei:

Maar als hij direct alle staafjes neemt is hij direct gewonnen en is speler 1 een oen!

Klik om te vergroten...

Er lijkt idd een restrictie te ontbreken.