Categorie archieven: Problem Solving

Bewijzen met verhaaltjes

Geplaatst op door

Deze bewijstechniek bestaat er in ‘een verhaaltje te vertellen. 

Stel ik wil volgende formule “bewijzen”:  voor n\geq p\geq 2

    \[p(p-1)\binom{n}{p}=n(n-1)\binom{n-2}{p-2}\]

Je zou natuurlijk, gebruikmakend van de definitie van de binomiaalgetallen, beide leden kunnen uitrekenen, en vaststellen dat beide resultaten hetzelfde zijn. Maar proberen we dit eens anders in te kleden. Je hebt binnen een politieke partij n kaderleden, waaruit je een dagelijks bestuur van p personen moet kiezen, met hierin een voorzitter en een ondervoorzitter. Dit kan je doen op twee manieren :

  • Kies eerst p personen. Dit kan op \binom{n}{p}. Kies hier uit een voorzitter: p mogelijkheden. Kies dan een ondervoorzitter: p – 1 mogelijkheden. Samen geeft dit dus, als aantal mogelijkheden:

        \[p(p-1)\binom{n}{p}\]

  • Maar je kan eerst een voorzitter kiezen uit de n kaderleden. Dit kan je op n mogelijkheden. Kies vervolgens een ondervoorzitter: n – 1 mogelijkheden. Kies tenslotte nog p-2 ander personen om je dagelijks bestuur te vervolledigen. dit kan op \binom{n-2}{p-2} manieren. Zo krijg je in het totaal als mogelijkheden:

        \[n(n-1)\binom{n-2}{p-2}\]

Hiermee is de gevraagde formule bewezen!

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

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.
    •