Kombinatorik

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=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? :)

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:

$$\begin{gathered} 26·1·3-26·1·2=26·1 \\ 3·26+2(-26)=26 \end{gathered}$$

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

$$\begin{gathered} 3·26+2(-26)=26 \\ 3·y + 2·x_{ } =26 \end{gathered}$$

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

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

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 $\in \mathrm{\mathbb{Z}}$

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:

$\left\{\begin{array}{l}x=26-2k\\ y=(-26)+3k\end{array}\right.\stackrel{+(k=5)}{\iff }\left\{\begin{array}{l}x=16-2k\\ y=(-11)+3k\end{array}\right.\stackrel{+(k=4)}{\iff }\left\{\begin{array}{l}x=8-2k\\ y=1+3k\end{array}\right.$

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. :)

Tack!! 

Varsågod! :)