Kombinatorik: Inklusion och Exklusion
Uppgiften är "Bestäm antalet positiva heltal mindre än 10 000 000, där summan av siffrorna är 31.". Jag resonerade först att frågan menade alla tal som kan summeras under 31 alltså alla tal från 1 till 30. Jag har tänkt mig att ett fall är då 2 tal summeras till 31 d.v.s. . Sedan beräknar jag antalet kombinationer med upprepning . För tre variablar blir det . Samma sätt kan göras för alla då 1 < n < 31. d.v.s. . Det verkar som att jag ska lösa uppgiften genom att anta ekvationen och att . Jag förstår inte riktigt hur frågan leder till denna lösningen? Vad är det som säger att jag ska beräkna alla möjliga heltals lösningar för just 7 x så att summan blir 31?
Summan av siffrorna i ett tal, eller vanligare siffersumman, är just det: summan av alla siffror som ingår i det talet. Man brukar lära sig redan på högstadiet att ett tal är delbart med 3 och talets siffersumma är delbart med 3.
Smaragdalena skrev:Summan av siffrorna i ett tal, eller vanligare siffersumman, är just det: summan av alla siffror som ingår i det talet. Man brukar lära sig redan på högstadiet att ett tal är delbart med 3 och talets siffersumma är delbart med 3.
Så siffersumman 10 miljoner blir 1+0+0+0+0+0+0+0 = 1 men vad har jag för nytta med detta. Sedan vet jag att alla möjliga val av till kan väljas på 10 miljoner sätt. Jag förstår inte hur detta hänger ihop med frågan.
Vill du fortfarande ha hjälp med denna kan jag köra ett försök.
Det är en hyfsat komplicerad uppgift.
Idén är alltså att första siffran är x1, andra x2 osv. Eftersom talet har max 7 siffror får vi sju variabler.
Vi ska alltså lösa x1+x2+x3+x4+x5+x6+x7=31 under villkoret att 0≤x≤9.
Poängen är att om vi tar bort restriktionen och bara räknar antalet lösningar till:
x1+x2+x3+x4+x5+x6+x7=31
så har vi ett kombinatoriskt standardproblem. Kan du lösa det?
Sedan kommer det kluriga steget: att ta bort lösningar där något xi >9.
Smutsmunnen skrev:Vill du fortfarande ha hjälp med denna kan jag köra ett försök.
Det är en hyfsat komplicerad uppgift.
Idén är alltså att första siffran är x1, andra x2 osv. Eftersom talet har max 7 siffror får vi sju variabler.
Vi ska alltså lösa x1+x2+x3+x4+x5+x6+x7=31 under villkoret att 0≤x≤9.
Poängen är att om vi tar bort restriktionen och bara räknar antalet lösningar till:
x1+x2+x3+x4+x5+x6+x7=31
så har vi ett kombinatoriskt standardproblem. Kan du lösa det?
Sedan kommer det kluriga steget: att ta bort lösningar där något xi >9.
Detta är min lösning till problemet med principen om inklusion och exklusion.
Ser rätt ut.
Bra jobbat, inte helt lätt uppgift!
