7 svar
96 visningar
matildaallerhed är nöjd med hjälpen!
matildaallerhed 20
Postad: 29 sep 2020

Kombinatorik

Hej! Jag har en uppgift som ser ut såhär:

Vi har två måttskopor, en på 2 dl och en på 3 dl. Med hjälp av dessa ska vi skopa upp 26dl socker. På vilka sätt kan man få ihop denna kvantitet med hjälp av dessa skopor? Vi är intresserade av hur många skopor av varje man ska ta. 

 

Rent spontant tänker jag att jag kan addera ihop så många 3dl jag kan och lägga till 2dl där det behövs och sedan succesivt ta bort 3dl och lägga till 2 dl för att få upp det i 26 totala dl. Något sånt här: 

3+3+3+3+3+3+3+3+2

3+3+3+3+3+3+2+2+2+2

3+3+3+3+2+2+2+2+2+2+2

3+3+2+2+2+2+2+2+2+2+2+2

2+2+2+2+2+2+2+2+2+2+2+2+2

Är det korrekt tänkt? Man är ju endast ute efter hur många skopor av varje som behövs. 

Dock funderar jag på hur jag skulle göra om jag vill veta hur många sätt kan man använda skoporna på. 

Kan det räknas ut med hjälp av multiplikationsprincipen, eller tänker jag tokigt? 

Detta kallas för en diofantisk ekvation, dvs. en ekvation som enbart har heltalslösningar. I just detta fall kan vi komma till +1 dl genom att skopa upp 3 dl socker först, och sedan skopa ut dl socker igen. Om vi upprepar detta 26 gånger har vi fått 26 dl socker. I många fall har en dock inte denna tur, och då behöver vi en algebraisk lösningsmetod. 

Det första vi gör är att definiera vår ekvation så att vi får den på formen ax+by=cax+by=c. Vi kan kalla tvådecilitersmåttet för x, och tredecilitersmåttet för y. Då har vi ekvationen 2x+3y=26. För att lösa denna, genomför vi euklides algoritm, för att hitta sgd(a, b). Om sgd(a,b) inte är en faktor i talet c, finns inga lösningar (Vi kan exempelvis inte skopa upp en deciliter socker om vi har ett tvådeciliters- och ett fyradecilitersmått). När vi fått fram sgd, genomför vi euklides baklänges, och därefter förlänger vi med båda led så att vi får en ekvation som vi kan läsa av värden från. Känner du igen detta, eller är det helt nytt? :)

matildaallerhed 20
Postad: 30 sep 2020

Jo men det har vi kikat lite på. Jag har dock problem med när jag ska göra Euklides algoritm baklänges... 

Först får jag fram:

3=1*2+1

2=2*1+0 

Det ger gcd(3,2)=1

Sen ska jag göra den baklänges och får

1=3-1*2

1=3-2

Men sen då? Där fastnar jag. 

Utifrån gamla anteckningar får jag att "lösning finns om och endast om gcd(a,b) delar c". I det här fallet ska alltså 1 dela 26?  Hur formulerar jag den lösningen? 

För att göra det hela lite tydligare (lägg bara till 1* till trean, så blir det lättare att läsa av lösningen): 

1·3-1·2=1

Nu vill vi att ett av ekvationens led ska vara 26, eftersom vi vill ha 26 dl socker:

26·1·3-26·1·2=26·13·26+2(-26)=26

När vi jämför detta med vår ekvation, kan vi notera följande:

3·26+2(-26)=263·y  + 2·x       =26

En lösning är alltså x = -26, y = 26. 

Hur kan vi göra för att nu hitta fler lösningar? :)

matildaallerhed 20
Postad: 30 sep 2020

Tack! 

Därefter ska jag väl använda mig utav k? 

Då jag med hjälp av lcm(3,2): 
3*26+2(-26)=26
3*26+2(-26)+k(3*2-2*3)=26
3*26+2(-26)+3*2k-2*3k=26 
3*26-3*2k+2(-26)+2*3k=26 
3(26-2k)+2(-26+3k)=26 

och att vi då har x=26-2k och y=(-26)+3k    där k  

Ser detta rätt ut? Jag vet inte om jag gjort rätt med alla tecken och ordningen på allt, det blev lite rörigt... 

Det ser bra ut! Det är vanligt att lägga till/ta bort multiplar av k så att x och y blir så "enkla" som möjligt (dvs. i närheten av noll). Det är inget måste, men det brukar se lite snyggare ut. Om vi provar att lägga på några multiplar av k:

x=26-2ky=(-26)+3k+(k=5)x=16-2ky=(-11)+3k+(k=4)x=8-2ky=1+3k

så får vi ett lite snyggare sätt att skriva på. Som sagt, det är inte obligatoriskt på något sätt, men det är en bra vana att ha när ekvationerna och deras lösningar börjar bli svettigare. :)

matildaallerhed 20
Postad: 1 okt 2020

Tack!! 

Varsågod! :)

Svara Avbryt
Close