Hej allesammans,
Tack för en fin seminarieträff i fredags! Nedan följer lite generella lösningsmetoder för uppgifterna
Uppgift 1:
- - - - - - - -
a) Att en graf är hamiltonsk innebär att det finns en hamiltoncykel. D.v.s. en väg som passerar varje hörn exakt en gång och kommer tillbaka till det hörn man började på.
Det är värt att poängtera att grafen kan ses som en slags kub i R3. Det går att visa att grafen är bipartit vilket innebär att dess hörn kan färgläggas med exakt två färger (OBS! En färgläggning är sådan att inga två närliggande hörn blir tilldelad samma färg). Låt säga att vi färglägger hörnen med blå och röd färg. Då kommer antalet blåa hörn = antalet röda hörn. Eftersom grafen även är enkel och sammanhängande följer det från känd sats att grafen även är hamiltonsk.
b) Denna graf är också bipartit men antalet blåa hörn != antalet röda hörn. Eftersom grafen även här är enkel och sammanhängande följer det från känd sats att grafen ej är hamiltonsk.
(Notera att man behöver ha läst en del grafteori för att förstå lösningen ovan. Baserat på vår diskussion från förra seminariet kommer jag undvika grafteori i fortsättningen!)
Uppgift 2:
- - - - - - - -
Visa först basfallet n=1. För induktionssteget bör man extrahera den sista termen för att kunna använda induktionsantagandet. Efter detta är det bara att förenkla m.h.a. algebra.
Uppgift 3:
- - - - - - - -
a) Varje lösning till ekvationen x1 + x2 + x3 +x4 = 520 kan tolkas som en binär sekvens med exakt 3 nollor och 520 ettor. Före den i:e nollan (1<=i <=3) har vi x_{i} antal 1:or och efter den i:e nollan har vi x_{i+1} antal 1:or. Så t.ex. om x1 = 1 och x2 = 3 skulle den binära sekvensen inledas med 10111. Notera även att varje binär sekvens med exakt 3 nollor och 520 ettor motsvarar en lösning till ekvationen. Därför är antalet lösningar till ekvationen ovan = antalet sätt att omordna den binära sekvensen. Det räcker med att positionera nollorna då detta helt bestämmer vart ettorna placeras. Antalet sätt att positionera nollorna är C(523, 3) och detta är därmed svaret till uppgiften.
b) Inför variabelbytet y1 = x1 -5 , y2 = x2 - 10 , y3 = x3 -15 , y4 = x4 - 20. Notera nu att det blir samma typ av problem som i den föregående deluppgiften.
Återkommer strax med nästa veckas problem. Ha det gott och ta hand om er!
Med vänliga hälsningar,
Emil