Hej!
I fredags hade vi mycket intressanta diskussioner om seminarieuppgifterna och engagemanget var top notch! Nedan följer några allmäna lösningsstrategier till uppgifterna. Jag utelämnar detaljer för att ni själva skall få öva på att komma fram till rätt svar. Om ni har några frågor eller funderingar så kan ni som vanligt höra av er till mig så hör jag av mig så fort det går.
Uppgift 1:
- - - - - - - -
a) Problemet går ut på att räkna antalet uppåt-höger stigar i ett 2D rutnät där man startar från koordinat (0, 0) och vill ta sig till
koordinat (5 ,7). Alla sådana stigar kan ses som en sekvens av uppåt eller höger "drag". Alltså något i stil med
"HUUUHHHUUUUH". Där "H" representerar ett höger drag och "U" ett uppåt drag och där bokstaven längst ut till vänster representerar det första draget, bokstaven näst längst till vänster det andra draget o.s.v.
Antalet sätt att omordna sekvensen ges av binomialkoefficienten C(12, 5) (Varför?)
b) Vi kan definiera 4 mängder.
X := Alla möjliga uppåt-höger stigar.
A := Mängden av uppåt-höger stigar som passerar (1,3)
B:= Mängden av uppåt-höger stigar som passerar (4,5).
Y:= Mängden av uppåt-höger stigar som varken passerar (1,3) eller (4,5).
Vi är klara om vi kan bestämma |Y| (storleken på mängden Y).
Notera att Y är komplementet till A U B. Från vilket det följer att
|Y| = |X| - |A∪B| (1)
och enligt känd sats vet vi att
|A U B| = |A| + |B| - |A∩B|
från vilket det följer att (1) kan ersättas med
|Y| = |X| -|A| - |B| +|A∩B|. (2)
Vi har sen tidigare räknat ut |X| så det kvarstå att räkna ut |A| , |B| samt |A∩B|.
Jag utelämnar uträkningarna men notera att det blir precis samma typ av uträkning som i den föregående deluppgiften.
För t.ex. |A| kan ni först räkna antalet uppåt-höger stigar från (0,0) till (1,3) och sedan från (1,3) till (5,7). Multiplikationsprincipen ger sedan svaret.
Uppgift 2:
- - - - - - - -
Visa först basfallet n=1. Anta sedan påståendet vara sant för något n= p>=1 och visa att det även gäller för n = p+1. För induktionssteget kan det komma till nytta att extrahera den sista termen från summan så att induktionsantagandet kan användas direkt på den kvarstående summan. Notera sedan att nämnaren i den extraherade termen är en ändlig aritmetisk summa. Efter förenkling kan ni enkelt slå ihopp dessa genom att bilda gemensam nämnare och med lite yttligare förenkling bör ni landa på det vi vill visa.
Uppgift 3:
- - - - - - - -
a) Notera först att varje positivt heltal "x" kan uttryckas på följande form
x = 10^(n) * x_{n} + 10^(n-1) *x_{n-1}+ ...+ 10*x_{1}+ x{0} (OBS! Allt innanför "{}" är subscript och allt innanför "()" är exponent)
Vad kan vi nu säga om x mod 10?
b) Efter 2^(x) steg hamnar Emil på samma bokstav som om han tog "r" steg från position "A" där
"r" är den rest som fås då 2^(x) delas med 5. Om vi räknar ut denna rest "r" för varje heltal 20<=x<=30
så kan vi kolla hur många av utfallen som leder till att resten blir antingen 1 eller 4. Dessa motsvarar då de utfall som leder till att Emil
antingen hamnar på "B" eller "E". Eftersom "x" valdes likformigt på heltalsintervallet så gäller framförallt att
Sannolikheten att springa för all evighet = (Antalet värden på x som ger att 2^x är kongruent med 1 eller 4 mod 5) / 11
(Notera att det är division med 11 eftersom det finns 11 heltal på intervallet 20 <=x <=30) .
Jag återkommer strax med problem för kommande seminarie som inträffar nu på fredag. Ha det gott och ta hand om er!
Med vänliga hälsningar
Emil