Categorie archieven: Problem Solving

Opgave 29

Geplaatst op door

n spelers spelen n spelen en winnen om de beurt. Telkens een speler wint, verdubbelt hij het bezit van zijn n-1 tegenspelers. Op het einde hebben ze allemaal evenveel. Hoeveel hadden ze in het begin?

Antwoord

  • Laten we eenvoudig beginnen met 3 spelers, die in het begin a,b en c bezitten. Het rijtje tussen resultaten van de eerste speler is (a, a-b-c,2(a-b-c),4(a-b-c)). Het rijtje voor de tweede speler is (b,2b,3b-a-c,2(3b-a-c)). tenslotte voor de derde speler (c,2c,4c,7c-a-b). Als ze allemaal evenveel hebben op het laatst dan moet 4(a-b-c)=2(3b-a-c)=7c-a-b.. Dit stelsels is gelijkwaardig met : 4b=7c en 4a=13c. Hieruit volgt dat a=13, b=7 en c=4.
  • Deze manier van werken wordt moeilijk voor willekeurige n.
  • Noteer met s het totaal bezit van alle spelers. Op het einde hebben ze dan allemaal \frac{s}{n}.
  • Na het eerste spel heeft de eerste speler a_1-a_2-\cdots-a_n=2a_1-s.
  • Al de volgende keren wordt zijn bedrag verdubbeld zodat hij op het einde 2^{n-1}(2a_1-s)=\frac{s}{n} heeft. Hieruit volgt dat n2^na_1=s(2^{n-1}n+1).
  • Een analoge redenering voor speler 2 geeft :n2^na_2=s(2^{n-2}n+1). Idem voor alle andere spelers.
  • Hieruit volgt dat ze allen op het einde 2^n bezitten en dat in het begin speler k een som van 2^{n-k}n+1 heeft

Recursie

Geplaatst op door

Een rij van getallen kan je geven met behulp van een recursief  voorschrift zoals bijvoorbeeld : a_1=1 en a_n= 2a_{n-1}+1. Soms kan je uit dit recursief voorschrift een expliciete formule afleiden voor de algemene term van de rij. Soms kan dat niet, maar is het mogelijk, via recursie, de parameters te herleiden tot waarden waarvoor je het probleem wel kan oplossen.

Een eerlijk muntstuk wordt n keer opgeworpen. Wat is de kans op twee opeenvolgende keren kop ergens in de rij worpen?

  • Noteer met P_n de kans dat er nergens twee keer kop na elkaar voorkomt is de rij van n worpen.
  • Het is duidelijk dat P_1=1 en P_2=\frac{3}{4}.
  • Stel n>2. Dan zijn er twee mogelijkheden naargelang de eerste worp kop of munt is.
  • Als je eerst munt gooit, dan is de kans dat je nergens twee keer kop na elkaar hebt in de volgende n-1 worpen gelijk aan P_{n-1}.
  • Gooi je eerst kop, dan moet de tweede worp munt zijn, want anders zou je twee keer kop na elkaar hebben. De kans dat je nergens twee keer kop na elkaar hebt in de volgende n-2 worpen gelijk aan P_{n-2}.
  • Uit de vorige twee punten vinden we tenslotte dat

        \[P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\]

  • Dit kan je herleiden tot 2^nP_n=2^{n-1}}P_{n-1}+2^{n-2}P_{n-2}. Of via S_n=2^nP_n:

        \[S_n=S_{n-1}+S_{n-2}\]

  • Dit is de rij van Fibonacci, waarbij S_n het n+2 de getal in de rij van Fibonacci is. Dus S_n=F_{n+2}. De gezochte kans op twee opeenvolgende keren kop ergens in de rij van n worpen, met n>2 is dan X=1-P_n=1-\frac{F_{n+2}}{2^n}.

Bewijs door inductie

Geplaatst op door

Vaak bestaat een probleem erin aan te tonen dat een bepaalde eigenschap geldt voor elk natuurlijk getal. Hiervoor gebruiken we het principe van de  volledige inductie 

  •  Basisstap: Men bewijst P(1)
  • Inductiehypothese: Men bewijst voor elke k dat als P(k) geldt, dan ook P(k+1) geldt.

Er bestaat ook een andere vorm, die we de sterke inductie noemen:

  • Basisstap: Men bewijst P(1) .
  • Inductiehypothese: Men bewijst voor elke k dat als P(1),P(2),\ldots,P(k) gelden, dan ook P(k+1) geldt.

Voor elk natuurlijk getal n geldt :

    \[1^2+2^2+\ldots+n^2=\frac{1}{6}n(n+1)(2n+1)\]

  • De geldigheid van de formule voor n=1 is duidelijk, want  1^2=\frac{1}{6}.1.(1+1)(2+1). Dit is de basisstap.
  • De inductiehypothese : stel dat de formule ook geldt voor n=k. Dan is: 

        \begin{align*}1^2+2^2+\ldots+k^2+(k+1)^2=&(1^2+2^2+\ldots+k^2)+(k+1)^2\\=& \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\\=&\frac{1}{6}(k+1)(2k^2+7k+6)\\=&\frac{1}{6}(k+1)(k+2)(2k+3) \end{align*}

    en dit is precies de formule voor n=k+1


					

		
		
	


				
					
	

		

						
Pariteit

			
						

				Geplaatst op   door  			

			
					


				

			
Het feit dat een gegeven even of oneven is kan belangrijk zijn om de oplossing van het probleem te vinden. Het even of oneven zijn van een getal noemen we de pariteit  van het getal. Deze heuristiek wordt dikwijls gebruikt in combinatie met kleuringen of het invariantie principe.




Neem 2017 punten op een cirkel en verbind ze tot ze een 2017-hoek vormen. Elke zijde van deze 2017-hoek krijgt een ‘lading’: +1 of -1. Bewijs dat er altijd een hoekpunt moet zijn, zodat het product van de ladingen van de zijden die samenkomen in dat punt, gelijk is aan +1.


    

  • Neem een willekeurige zijde en geef die lading +1. Dit kan, want als alle ladingen -1 zouden zijn is het gestelde zeker al bewezen. Het rechtse eindpunt van de zijde noemen we H_1.
    • 

  • Ga rechtsom en neem de volgende zijde. Is de lading +1 dan is H_1 een hoekpunt dat aan de voorwaarde voldoet. Dus veronderstel dat de lading -1 is.
    • 

  • Je gaat zo steeds verder. Ofwel vindt je twee maal na elkaar eenzelfde lading, en dan is de stelling bewezen. Ofwel alterneren de ladingen +1 en -1 elkaar. Omdat 2017 oneven is zal de laatste zijde lading +1 hebben en is de stelling ook dan bewezen.
    • 

  • Je kan het probleem ook oplossen door P_i te definiëren als het product van de ladingen die in hoekpunt H_i samenkomen. Het product van alle P_i’s moet +1 zijn, omdat alle zijden twee keer geteld worden in dit product. Omdat we een oneven aantal hoekpunten hebben kunnen niet alle P_i’s gelijk zijn aan -1. Er is dus minstens één hoekpunt, zodat het product van de ladingen van de zijden die samenkomen in dat punt, gelijk is aan +1.
    • 


					

		
		
	


				
					
	

		

						
Contradictie

			
						

				Geplaatst op   door  			

			
					


				

			
Redeneren door  tegenspraak gaat uit van de veronderstelling dat de conclusie niet juist is en probeert door argumenteren te komen tot iets wat in tegenspraak is met gegeven is (de indirecte methode) of iets wat in tegenspraak is met iets waarvan we weten dat het waar is (reductio ad absurdum).




Bewijs dat de onderstaande reeks divergeert  


      \[1+\frac{1}{2}+\frac{1}{3}+\cdots\]




    

  •  We veronderstellen dat de reeks niet divergeert maar dus convergeert naar de waarde r.
    • 

  •  Dus r=(1+\frac{1}{2})+(\frac{1}{3}+ \frac{1}{4})+(\frac{1}{5}+ \frac{1}{6})+\cdots.
    • 

  •  De eerste term van elk groepje van twee termen is groter dan de tweede, dus kunnen we schrijven dat

          \[r> (\frac{1}{2}+ \frac{1}{2})+ (\frac{1}{4}+ \frac{1}{4})+ (\frac{1}{6}+ \frac{1}{6})+\cdots = 1+\frac{1}{2}+ \frac{1}{3}+\cdots=r\]
    

    .
    • 

  • Dus is r>r en dat is onmogelijk. Bijgevolg is de harmonische reeks niet convergent, maar wel divergent.
    •