Categorie archieven: Bewijstechnieken

Kleuringen

Geplaatst op door

Soms kan het nuttig zijn om een rooster in te  kleuren  en daardoor te bewijzen dat een bepaalde situatie al dan niet mogelijk is. Deze heuristiek wordt dikwijls gebruikt wanneer je een schaakbord moet opvullen met bepaalde vormen.

Voorbeeld: Kan een 10 x 10 schaakbord opgevuld worden met 25 tetrominos van de vorm 

Oplossing:

  • Geef elk vakje van het schaakbord een uniek adres door het rijnummer en kolomnummer van het vakje te noteren. Zo een adres is dan van de vorm (i,j) \text{ waarbij } 1 \leq i,j \leq 10.
  • Kleur (i , j ) met de kleur t = i +j \text{ mod4 } zodat t \in \{1,2,3,4\}. Hierbij is1 = blauw; 2 = geel; 3 = rood; 4 = groen.
  • Elke tetromino zal door de schikking van de kleuren (cijfers) precies 4 vakjes met vier verschillende kleuren bedekken.
  • Aangezien er op het bord 25 keer blauw (1), 26 keer geel (2) 25 keer rood (3) en 24 keer groen (4) voorkomt zal het niet mogelijk zijn om het bord te vullen met 25 tetromino’s

					

		
		
	


				
					
	

		

						
Invariantieprincipe

			
						

				Geplaatst op   door  			

			
					


				

			
De problemen die we nu zullen bestuderen gaan over processen die zich in een aantal toestanden kunnen bevinden. Laten we voor een gegeven probleem die toestanden even t_{begin},t_1,... noemen. De overgang van de ene toestand naar de andere toestand is eenduidig vastgelegd door een aantal spelregels. Uiteindelijk is de vraag of het mogelijk is van toestand t_0 naar een eindtoestand t_{eind} te gaan door de regels te gebruiken. Een strategie om aan te tonen dat dit onmogelijk is, is gebruik te maken van een functie f die gedefinieerd is op de verschillende toestanden van het probleem en die bij de overgang van de ene toestand naar de andere niet van waarde verandert. De functie blijft invariant gedurende het hele proces. Als uiteindelijk blijkt dat f(t_{begin}) \neq f(t_{eind}) kunnen we besluiten dat het onmogelijk is om van de begintoestand naar de eindtoestand te komen door gebruik te maken van de spelregels.


Een voorbeeld:


Een draak heeft 100 hoofden. Een ridder kan er 15,17,20 of 5 afhakken. maar als hij dat doet, dan groeien er onmiddellijk 24,2,14 of 17 nieuwe hoofden bij. Als alle hoofden er af zijn dan is de draad dood. Kan de ridder de draak doden?





				
Spoiler

				


Definieer de functie f die het aantal hoofden berekent modulo 3. Dan is f(t_{begin})=1. Als de ridder 15 hoofden afhakt, dan komen er 24 bij, dus -15+24=+9. De andere gevallen geven ons: -17+2=-15, -20+14=-6 en -5+17=+12. Het aantal hoofden dat verdwijnt of er bij komt is steeds een veelvoud van 3, dus verandert het aantal hoofden, modulo 3 niet. Met andere woorden f is invariant. Hieruit volgt dat f(t_{eind})=1 Maar als de draak dood is, zijn alle hoofden er af en zou f(t_{eind})=0. De draak kan dus niet verslagen worden.



			


 

					

		
		
	


				
					
	

		

						
Oneindige afdaling

			
						

				Geplaatst op   door  			

			
					


				

			
Een bewijs door  oneindige afdaling  is een manier van bewijzen die kan worden toegepast bij aftelbare welgeordende verzamelingen, meestal de natuurlijke getallen. Men bewijst het niet bestaan van een element uit een verzameling met een bepaalde eigenschap, door aan te tonen dat als er zo een element zou bestaan, er ook een kleiner element moet bestaan met die eigenschap. Zo ontstaat een oneindige keten van elementen kleiner dan het veronderstelde element, terwijl er maar eindig veel van dergelijke elementen zijn. Fermat was één van de eersten die deze methode veelvuldig gebruikte.




Een voorbeeld:


Vind alle oplossingen in positieve gehele getallen van x^2+y^2=3(z^2+w^2)


Bewijs:


Stel (x,y,z,w) een oplossing van de gegeven vergelijking waarbij x minimaal is. Omdat 3 een deler is van het rechterlid , moet 3 ook een deler zijn van x^2+y^2. Omdat kwadraten 0 of 1 modulo 3 zijn, kan x^2+y^2 alleen maar deelbaar zijn door 3 als x en y zelf deelbaar zijn door 3. Dus x=3x' en y=3y'. Ingevuld geeft dit 3(x'^2+y'^2)=z^2+w^2. Analoog vinden we dat z=3z' en w=3w', waardoor x'^2+y'^2=3(z'^2+w'^2). Dus is (x',y',z',w') ook een oplossing van de gegeven vergelijking met x'<x. Dit levert een tegenspraak en dus heeft de vergelijking geen oplossingen in de verzameling van de positieve gehele getallen.

					

		
		
	


				
					
	

		

						
Extremaal principe

			
						

				Geplaatst op   door  			

			
					


				

			
In essentie betekent deze methode niet meer of minder dan het bekijken van de  meest extreme situatie die zich kan voordoen of zou moeten kunnen voordoen. Als je ooit om een of andere reden het niet bestaan van bepaalde objecten wil aantonen, bijvoorbeeld van het maximum van een verzameling, zal deze techniek zeker een nuttig hulpmiddel zijn. Je bepaalt een verzameling objecten en selecteert een object waarbij een bepaalde eigenschap minimaal of maximaal is. Werk verder tot je een tegenspraak krijgt.


Bekijken we eens een voorbeeld: In een groep van n personen zijn er steeds twee die binnen deze groep evenveel vrienden hebben. We veronderstellen dat vriendschap wederzijds is.


vrienden


Veronderstel dat ze allemaal een verschillend aantal vrienden hebben. Vermits er n personen zijn en omdat iemand maximaal n-1 vrienden kan hebben, hebben die n personen respectievelijk 0,1,2,...,n-1 vrienden. Bekijken we het extreme geval dat iemand dus n-1 vrienden heeft. Met andere woorden hij is met iedereen bevriend. Maar omdat vriendschap wederzijds is, heeft iedereen dus minstens 1 vriend. Bijgevolg is er niemand met 0 vrienden. Dit geeft onze tegenpraak en bijgevolg zijn er minstens twee personen met evenveel vrienden.