Lösning till gåta vecka 17
På hur många sätt kan man skriva talet 2009 som en summa av några positiva nästan lika heltal? Talen kallas nästa lika om deras skillnad är (till beloppet) maximalt 1. Sätten betraktas som samma om det enda som skiljer dem åt är ordningen på termerna.
Diskussion:
Först och främst ska man pröva sig fram till lösningar, för att ”känna på” problemet. Det gäller alltså att komma på några sätt att dela 2009 i några nästan lika stora delar. En första tanke är att dela upp det som en summa av lika stora delar. Hur man göra det beror på vilka tal 2009 är delbart med.
2009 = 7*287 = 7*7*41
Så till exempel har vi uppdelningarna i exakt lika termer
2009 = 287 + 287 + 287 + 287 + 287 + 287 + 287
2009 = 1 + 1 + … + 1 (2009 stycken ettor)
2009 = 41 + 41 + … + 41 (49 stycken 41:or)
2009 = 2009
Men vad händer om vi försöker dela upp i ett visst antal termer, där antalet inte är en delare till 2009? Till exempel två termer? Då delar vi på två så gott det går, resultatet blir 1004 med rest. Men uppdelningen
2009 = 1004 + 1005
funkar ju, för att 1004 och 1005 är nästan lika.
Försök på samma sätt med tre termer. 2009 delat på 3 blir 669 och resten är 2. Då kan vi göra såhär:
2009 = 669 + 670 + 670
Den här idén med rester kommer vi att använda i lösningen.
Lösning:
Enligt villkoren måste varje sätt att summera upp till 2009 innehålla maximalt två sortes termer: ena kan uttryckas som x och andra som x+1. Ifall det fanns andra tal, skulle de inte vara nästan lika med x eller x+1.
Notera nu att för varje antal termer (beteckna antalet med n), så finns det ett sätt att dela upp 2009 i just så många nästan lika termer. Nämligen, dela 2009 med n med rest:
2009 = n*k + r
där k är kvoten och r är resten. Man vet att resten alltid är mindre än det man delade med, således mindre än antalet termer.
Likheten kan skrivas om:
2009 = k + k + … + k + r
där termen k förekommer n gånger. Men för att få just n stycken termer, fördelar vi r stycken ettor på r stycken k-termer. Det kan vi göra eftersom k är mindre än n. Således:
2009 = k + k + … + k + (k+1) + (k+1) + … + (k+1)
där termer av typen k förekommer (n-r) gånger och termer av typen (k+1) förekommer r gånger.
Så nu har vi 2009 stycken sätt att dela upp! Ett sätt för varje antal termer. Men finns det inga andra sätt?
Nej, faktiskt inte. Vi sa ju tidigare att termerna måste vara x och x+1. Har vi ett fixerat antal termer i summan
2009 = x + x + … + x + (x+1) + (x+1) + … + (x+1)
så kan vi inte ändra vare sig några x till x+1 eller tvärtom, för då skulle det hela inte summera upp till 2009.
Således är svaret: 2009 sätt.
Hur gör man med talet 40 som kan skrivas som en summa av fyra positiva heltal om man tar hänsyn till ordningen i vilken man summerar talen?
Hur ser principen ut då?
Lyckades får fram med exempel om talet skrivs med tvåor och/ eller femmor att med hänsyn till ordningen så finns det 1601 olika sätt. Men nu till fallet med 4 positiva heltal, vart börjar jag ?
Menar att du att talen man summerar inte längre behöver vara ”nästan lika”?
Så din fråga är på hur många sätt man kan dela upp 40 i fyra stycken tal och man tar hänsyn till ordningen. T.ex.
40=10+10+10+10
40=20+10+5+5
40=5+10+20+5
är några olika sätt. Förstår jag rätt?
Ja det stämmer. Har bara kommit så långt att det minsta talet i x+y+z+w=40 är ju x=37.
Gör jag rätt om jag sätter intervallet 1 ≤ x,y,z,w ≤ 37?
Ja, du har rätt i att x,y,z och w maximalt kan vara 37. För att få svar på ditt problem, tänk så här:
Föreställ dig fyrtio stycken ettor i rad:
1111111……..11111111
Varje bestämd lösning motsvarar då att vi delar upp de här ettorna, exempelvis
111-11-11111……1111-111
motsvarar lösningen x=3, y=2, z=32, w=3 (vi tar och läser av från vänster till höger, hur många ettor det är i varje del).
1-1-1-1111…..11111
motsvarar lösningen x=1, y=1, z=1, w=37.
Så vår fråga kan omformuleras: på hur många sätt kan vi sätta in strecken bland ettorna? Notera att varje sätt att sätta in streck på motsvarar olika värden på variablerna.
Svaret är resultat från kombinatoriken. Tänk dig att vi har 39 stycken små ”mellanrum” emellan ettorna. Det är där som vi kan sätta in strecken. Vi ska välja just vilka 3 ”mellanrum” skall ha streck i sig.
Svaret blir talet
, som betecknar antalet sätt att välja 3 objekt ur 37 olika (i vilken ordning som objekten väljs ska inte spela någon roll).
Det beräknar man så här:
Ja, nu förstår jag. Hade ett liknande problem då man kunde välja röda,svarta och vita bollar och man ska plocka 3 bollar.
Fick det illustrerat på samma sätt med var man kan sätta in ”strecken”, dvs man omformulerar det precis som här. Det var lite svårt att se det i denna frågan bara, men nu är jag med.
Kan man lösa alla liknande problem på liknande sätt(dvs ordningen inte spelar någon roll är ju ett krav för denna lösningsgång, eller?), och det som gäller är att man bara hittar intervallet k ≤ a,b,c,d… ≤ n och sen omformulerar var vi kan placera strecken mellan dessa variabler, som i vårat fall ger oss 3 ”mellanrum”. Skulle 5 variabler ge oss 4 mellanrum då?
Tack för hjälpen oavsett, har fått mitt aha-moment nu och fortsätter tugga vidare!
Nåja, inte 37 över 3, det var väl ändå 39 över 3 som var rätt svar :)
Justja. skrev fel på slutet. Tack! Klart det ska vara 39 över 3 :)