Nedan har ni 3 problem att tänka på för nästa seminarieträff.
Uppgift 1 (Kombinatorik):
- - - - - - - - - - - - - - - - - -
Du befinner dig i en mörk skog med 2 massiva troll som vill käka upp dig. Ditt mål är att hitta till den andra och enda utgången i skogen utan att bli uppkäkad av trollen. Skogen kan ses som ett 2-dimensionellt rutnät med koordinater (x,y) där 0<=x <=5 och 0 <= y <=7. Du börjar vid startposition (x,y) = (0,0) och ditt mål är att ta dig till (5,7). Trollen befinner sig vid positioner (1,3) och (4,5) och på grund av deras feta storlek kommer de aldrig att sig ut ur sina positioner så länge natten pågår. Oavsett vad kommer du alltid att gå uppåt eller åt höger i rutnätet eftersom annars blir restiden alldeles för lång. Om du olyckligtvis hamnar på någon av koordinaterna där trollen befinner sig så är dina dagar på denna jord över.
a) Om det inte fanns troll i skogen, på hur många sätt skulle du kunna ta dig till den andra utgången?
b) Nu till den verkliga situationen. På hur många sätt kan du faktiskt ta dig till den andra utgången givet att trollen är där ute?
(TIPS: Använd ett inklusion-exklusions argument på b. Svaret i a kan också komma till nytta.)
Uppgift 2 (Induktion):
- - - - - - - - - - - - - - - - -
Visa att för varje n>=1 gäller det att
sum_k=1->n 1/(1+2 + ...+ k) = 2n/(n+1).
OBS! Om någon av er inte förstår vad som står ovan så kan ni kontakta mig privat
så kan jag förtydliga m.h.a. latex format.
Uppgift 3 (moduloräkning + lite sannolikhet):
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
a) Visa att ett resten då ett positivt heltal delas med 10 är detsamma som den sista siffran i talet.
b) En konstig individ har bestämt sig för att springa runt ett fält i medurs riktning (som har formen av en pentagon). Individen kommer stanna vid det hörn det hamnar på efter att ha tagit 2^x steg runt periferin av fältet där x är något slumpvalt tal på intervallet 20<=x<=30. Detta är naturligtvis helt omöjligt men ibland ska man våga att testa det omöjliga. Låt oss anta att individen börjar vid hörnet A och att resterande hörn markeras B,C,D,E i medurs riktning. Tyvärr är det så att om denna individ som vi kan kalla "Emil" hamnar på antingen B eller E så måste han springa runt fältet för resten av sitt liv. Vi kan anta att talet x väljs likformigt på intervallet 20 <=x <=30 (d.v.s. alla talen har samma sannolikhet att väljas). Vad är sannolikheten att Emil måste fortsätta springa för all evighet?
Kontakta mig eller Yishao om ni vill ha något förtydligat för er. Ha det gott och ta hand om er så ses vi på fredag!
Med vänliga hälsningar,
Emil