Kombinatorik - bestäm antal 5-siffriga tal
Uppgiften jag ska lösa lyder så här:
Bestäm antalet 5-siffriga tal som inte har följden 17,
T.ex. 4713, 1572 är tillåtna 4-siffriga tal, men 1723, 3175, 0254 är inte tillåtna.
Min första fråga är varför 0254 ej är tillåten? Jag har tolkat det så att det egentligen är ett 3-siffriga tal då det inleds med en nolla. Det betyder att nollor inte får förekomma på position 1 från vänster. Inte heller på någon annan position om det skulle föregås av nollor till vänster om sig.
Sedan undrar jag vilken kombinatorisk metod som man använder för att lösa denna typ av problem?
Jag börjar från vänster och tänker: På position 1 finns det 9 val {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Om vi valt 1 på position 1 så kan vi inte välja 7 på position 2, men vi har fortfarande 9 valmöjligheter: {0, 1, 2, 3, 4, 5, 6, 8, 9}.
Om vi på position 1 valt något av talen 2-9 så har vi 10 valmöjligheter: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Än så länge har vi valmöjligheter, stämmer det?
Ska jag fortsätta så här och hur ställer jag upp det på ett smart sätt?
Eller kan någon lägga en länk till ett liknande problem kanske?
På vilken form ska man svara på ett sådant här problem? På potensform? Det blir ett väldigt stort tal kan jag tänka mig.
Lisa Mårtensson skrev:Uppgiften jag ska lösa lyder så här:
Bestäm antalet 5-siffriga tal som inte har följden 17,
T.ex. 4713, 1572 är tillåtna 4-siffriga tal, men 1723, 3175, 0254 är inte tillåtna.
Min första fråga är varför 0254 ej är tillåten? Jag har tolkat det så att det egentligen är ett 3-siffriga tal då det inleds med en nolla. Det betyder att nollor inte får förekomma på position 1 från vänster. Inte heller på någon annan position om det skulle föregås av nollor till vänster om sig.
Sedan undrar jag vilken kombinatorisk metod som man använder för att lösa denna typ av problem?
Jag börjar från vänster och tänker: På position 1 finns det 9 val {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Om vi valt 1 på position 1 så kan vi inte välja 7 på position 2, men vi har fortfarande 9 valmöjligheter: {0, 1, 2, 3, 4, 5, 6, 8, 9}.
Om vi på position 1 valt något av talen 2-9 så har vi 10 valmöjligheter: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Än så länge har vi valmöjligheter, stämmer det?
Ska jag fortsätta så här och hur ställer jag upp det på ett smart sätt?
Eller kan någon lägga en länk till ett liknande problem kanske?
På vilken form ska man svara på ett sådant här problem? På potensform? Det blir ett väldigt stort tal kan jag tänka mig.
Menar du egentligen 4-siffriga tal?
De tillåtna 4713 och 1572 är 4-siffriga.
Svaret på din första fråga är nog ja, om första siffran är 0 så är det inget 4-siffrigt tal.
--------
Om jag förstår frågan rätt så är lösningen enkel och antalet blir inte så stort (det kan ju aldrig bli fler än 1000 stycken).
Jag skulle göra så här:
1. Ta reda på totala antalet 4-siffriga tal, dvs antalet tal mellan (och inklusive) 1000 och 9999.
2. Subtrahera antalet ogiltiga tal:
- Hur många 17xx?
- Hur många y17x?
- Hur många yx17?
(x kan vara vilken siffra som helst men y måste vara någon av siffrorna 1-9)
-----------
Om du verkligen menade 5-siffriga tal så kan du använda samma teknik.
Hej Yngve!
Tack för hjälpen. Nej jag menar 5-siffriga tal, det är så som det står i uppgiften. Och att de exemplifierar med hur det vore om det i stället var 4-siffriga tal som man jobbade med.
Varför kan det inte bli mer än 1 000 tal om det skulle vara ett 4-siffrigt tal?
Det finns ju 4-siffriga tal upp till 9 999, det är nästan 10 000. Likaså för 5-siffriga tal så finns det tal upp till 99 999, vilket är nästan 100 000.
Totala antalet tal mellan 10 000 - 99 999 är skillnaden mellan dessa tal + 1,
99 999 - 10 000 + 1 = 90 000.
Från 90 000 ska jag därefter dra bort följande:
-Antalet 17xxx där x kan vara vilket tal som helst 0-9.
-Antalet y17xx, där y kan vara 1-9, x kan vara 0-9.
-Antalet yx17x, där y kan vara 1-9, x kan vara 0-9.
-Antalet yxx17, där y kan vara 1-9, x kan vara 0-9.
Då var det bara att sätta igång och räkna, eller?
Lisa Mårtensson skrev:Hej Yngve!
Tack för hjälpen. Nej jag menar 5-siffriga tal, det är så som det står i uppgiften. Och att de exemplifierar med hur det vore om det i stället var 4-siffriga tal som man jobbade med.
Totala antalet tal mellan 10 000 - 99 999 är skillnaden mellan dessa tal + 1,
99 999 - 10 000 + 1 = 90 000.
Från 90 000 ska jag därefter
Ja det är 90 000 tal totalt.
En del av dessa är "ogiltiga" pga att de innehåller sekvensen 17.
Kan du följa min tidigare tankegång för att ta reda på hur många dessa ogiltiga tal är?
Yngve, jag har redigerat och börjat med din metod. Kolla!
Lisa Mårtensson skrev:Hej Yngve!
...
Varför kan det inte bli mer än 1 000 tal om det skulle vara ett 4-siffrigt tal?
Det finns ju 4-siffriga tal upp till 9 999, det är nästan 10 000. Likaså för 5-siffriga tal så finns det tal upp till 99 999, vilket är nästan 100 000.
...
Oops, här råkade jag skriva fel. Jag menade 10 000. Bra att du är uppmärksam.
...
Från 90 000 ska jag därefter dra bort följande:
-Antalet 17xxx där x kan vara vilket tal som helst 0-9.
-Antalet y17xx, där y kan vara 1-9, x kan vara 0-9.
-Antalet yx17x, där y kan vara 1-9, x kan vara 0-9.
-Antalet yxx17, där y kan vara 1-9, x kan vara 0-9.
Då var det bara att sätta igång och räkna, eller?
Ja det är bara att sätta igång och räkna.
Jag har räknat som jag tror är rätt, men svaret blir ändå inte korrekt enligt facit. Vad är det som jag tänker fel?
Från 90 000 ska jag därefter dra bort följande:
-Antalet 17xxx där x kan vara vilket tal som helst 0-9. 10*10*10=1 000
-Antalet y17xx, där y kan vara 1-9, x kan vara 0-9. 9*10*10=900
-Antalet yx17x, där y kan vara 1-9, x kan vara 0-9. 9*10*10=900
-Antalet yxx17, där y kan vara 1-9, x kan vara 0-9. 9*10*10=900
Summan av alla ogiltiga tal är 3 700.
90 000-3 700= 86 300.
Men 86 300 är alltså inte rätt svar.
Du har dragit bort exempelvis 51717 mer än en gång.
Ja, jag tänkte att det var något sådant. Att 17 kan ju finnas på fler positioner... 17x17, 1717x, y1717.
Jag får försöka på nytt:
x1717 har dragits bort 2 gånger så vi lägger till 9.
17x17 har dragits bort 2 gånger så vi lägger till 10.
1717x har dragits bort 2 gånger så vi lägger till 10.
Vi lägger sammanlagt till 29 och svaret är att det finns 86 329 5-siffriga tal som inte innehåller 17 i följd.
Det du redan har gjort är användbart, det behöver bara justeras lite till.
