Dirichlets lådprincip
"Visa att om 7 tal väljes godtyckligt från mängden {1, 2, 3,..., 12} så finns minst två vars summa är 13".
Hur löser jag denna uppgift?
Kika på vilka kombinationer som är giltiga:
Det finns totalt sex stycken kombinationer av tal som är giltiga. Vad händer om vi väljer sju tal?
Om vi väljer sju tal upprepas något av de som du har skrivit ovan och då tillhör minst två samma delmängd. Nu är jag väldigt osäker och jag hoppas du förstår vad jag menar.
Det pepparkvarn visar är att oavsett om du väljer de sju lägsta talen kommer alltid ett par ge summan 13. Detta, då de sju lägsta talen inkluderar 6 och 7. Jag är däremot inte säker på hur man visar det rent matematiskt, men en förklaring kanske räcker?
Tänk maximal otur! Vi ska försöka välja sju tal mellan ett och tolv, så att inga två tal kan bilda summan tretton. Det första talet vi väljer är ett, det andra är två, sedan tre, sedan fyra, fem och sex. Så långt är allt lugnt. Men vi har endast valt sex stycken tal. Om vi väljer vårt sjunde tal som sju, har vi att 6 + 7 = 13 vilket inte är tillåtet, om vi väljer åtta som vårt sjunde tal, har vi att 5 + 8 = 13, vilket inte är tillåtet. Detsamma gäller för 9, 10, 11 och 12.
Vi kan också börja välja uppifrån: Första talet vi väljer är tolv, sedan väljer vi elva, sedan tio, nio, åtta och sju. Men så fort vi väljer vårt sjunde tal får vi problem, eftersom vi då, oavsett hur vi väljer, har två tal vars summa är tretton.
Om du vill kan du tänka att det finns sex stycken talpar med summan tretton i det givna intervallet:
För att undvika att få något tal med denna summa, får vi inte välja mer än ett tal från varje talpar. Om vi väljer fem kan vi inte välja åtta. Om vi väljer tre kan vi inte välja tio, och så vidare. Eftersom vi har sex talpar ger det totalt sex tal vi kan välja, innan vi får någon kollision. Eftersom vi ska välja sju tal...
