Lösning till gåta vecka 22
Vi människor läser vanligtvis från vänster till höger och uppifrån och ner. Ödlor är inte lika snabba på att läsa, men de kan göra det på fler olika sätt. Ödlan kan läsa en bokstav och sedan förflytta sig ett steg ner, upp, till höger eller till vänster för att fortsätta läsa.
På hur många sätt kan en ödla läsa ordet FJÄRIL här nedan?
Diskussion:
Man kan förstås bara sätta igång och försöka räkna alla sätten. Det är en helt okej metod för att ta reda på svaret, men det finns ingen garanti på att man räknar rätt och inte glömmer någonting. Egentligen går uppgiften ut på att skapa just den garantin, att alla fall är medräknade. Det kallas att man gör systematisk undersökning.
Men det är krånglig att göra en direkt systematisk uppräkning. Det finns 11 stycken F att börja läsa på, redan där 11 fall som vi måste hålla koll på. Vid flera av F:en har vi två vägval, vi måste nämligen välja något J. Och så vidare … och det går förstås att komma fram till rätt svar men det blir mycket krångel.
Det underlättar att notera att bilden är symmetrisk. För varje F utom det längst upp finns ett motsvarande på andra sidan pyramiden. Det finns exakt lika många sätt att läsa FJÄRIL från de speglade F:n. Därför räcker det att räkna ut antalet sätt från de första 5 F:en och sedan multiplicera det med två och sedan addera ett sätt till (från det mittersta F:et går det att bara läsa neråt). Efter det kan man notera mer symmetri som underlättar beräkningar. Det slutar med att man bara måste räkna antalet sätt från de första tre F:en. Det blir totalt 1+5+10+10+5+1+5+10+10+5+1=63 sätt.
Vi kontrollerar detta på ett annat sätt.
Lösning:
Notera att antalet sätt att läsa ordet FJÄRIL är samma som antalet sätt att läsa ordet LIRÄJF (vi låter ödlan läsa baklänges). Och annorlunda formulerat, det är lika med antalet sätt att komma från bokstaven L till kanten av pyramiden, gående till nästa bokstav i ordet LIRÄJF varje gång.
Vi löser ett lite större problem. Nämligen, för varje ruta, sätt ut ett tal som berättar om hur många sätt det finns att ta sig till den rutan om man börjar i L. I början får vi följande bild, ty det finns bara ett sätt att komma till varje I från L:et:
Om vi nu ska forsätta vandra till R:en, så kan vi hamna i vissa R från två olika I. Därför ska antalet sätt adderas där och vi får totala antalet sätt att läsa LIR och sluta i ett specifikt R. Just här är det kanske inte så svårt att räkna dem sätten från början, men metoden blir mer användbar senare:
Forsätt att fylla ut tabellen på det sättet. Varje nytt tal blir summan av talen som kommer ”precis innan”, till exempel på höger sida blir det summan av talet under och talet till vänster (om nu båda finns). Till slut fås tabellen:
Återigen, antalet sätt totalt att läsa ordet LIRÄJF är 1+5+10+10+5+1+5+10+10+5+1=63.
För dig som har orkat läsa så här långt kommer en extrafråga. Vad kommer svaret att vara om vi har ett längre ord istället för FJÄRIL? Låt säga att vi har en pyramid av samma sort, men ett ord som har n olika bokstäver.
Jag måste säga att det här var ett väldigt roligt problem. :) Speciellt lösningen på den. Mycket snyggt sätt att drastiskt förenkla problemet och snyggt sätt att redovisa lösningen på. Bara snyggt, snyggt, snyggt…
:) Pascals triangel är bland det snyggaste som finns!
Man kan också tänka på följande sätt: Vi noterar att om ödlan någonsin läser till höger så kan den aldrig läsa till vänster och tvärsom.
Vi räknar antalet sätt ödlan kan läsa på när den inte läser åt höger någon gång. Då har den 5 chanser att svänga vänster (1 för varje bokstav utom första). Varje gång så gör den ett val på två möjligheter och vi får 2^5 möjligheter totalt. Tillsammans med gångerna då vi inte läser åt vänster så har vi totalt 64 möjligheter. Nu har vi räknat en möjlig läsväg 2 ggr då att läsa rakt upp läser vänster eller höger så den finns i båda möjligheterna. Denna drar vi av och får 63 olika sätt att läsa på.
Samma argument ger då att med n bokstäver så får vi 2*2^(n-1)-1=2^n-1 möjligheter.
Man ser också varför pascals triangel kommer fram, exempelvis den tredje röda siffran från höger är 10 och står för att välja att läsa åt vänster 2 ggr av 5 möjliga, dvs 5 över 2 om man känner till binomialkoefficienter.
Mmm, man kan ju tänka så att börjar man i toppen på pyramiden finns endast en möjlighet. Väljer man F:et till vänster om det så vet vi att vi måste göra fem drag för att komma till L, varav 1 åt höger och 4 ner. Låt oss basera våra tankegångar på hur många gånger man måste svänga ner. Alla möjliga lösningar för att ta sig från detta F till L får vi genom att välja hur vi ska placera ut nedåtgångarna. Antalet sätt är C(5,4). Tar vi F:et till vänster om detta måste vi fortfarande göra fem drag åt höger eller ner, men endast 3 ska var ner så antalet möjligheter är C(5,3). På samma sätt kan man göra med alla F och vi får återigen Pascals triangel. Sedan adderar vi allt. Det är ett lite mindre snyggt sätt, men funkar.