Matematikern John Conway föreslog en vacker numerisk gåta.
Det finns ett 10-siffrigt tal, med de unika siffrorna abcdefghij, som följer reglerna:
- a är delbart med 1
- ab är delbart med 2
- abc är delbart med 3
- abcd är delbart med 4
- abcde är delbart med 5
- abcdef är delbart med 6
- abcdefg är delbart med 7
- abcdefgh är delbart med 8
- abcdefghi är delbart med 9
- abcdefghij är delbart med 10
Den stora frågan är: vilket är talet?
Både Quanta Magazine och The Guardian utmanar och visar läsaren hur man kan lösa gåtan med papper och penna.
Vi kan också använda programmering för att få datorn att lösa problemet åt oss. I denna artikel visar jag hur man kan använda rekursion och programmeringsspråket Python för just detta.
Rekursion är en teknik där problemet upprepade gånger delas upp i mindre liknande uppgifter.
Man använder ofta samma funktion flera gånger med mer begränsad input i varje steg. Varje anrop kan visualiseras i ett träddiagram. Rekursion tvingar oss att gå längre ned på varje gren. Till slut nås slutet av grenen, ett så kallat basfall, och funktionen returnerar ett värde vilket får programmet att vända om och röra sig tillbaka upp på grenen igen.
I denna gåta börjar vi med ett val av siffror, 0–9, som vi enbart får använda en gång.
I takt med att vi använder en siffra, och därmed bygger vårt tal, minskar vi antalet tillgängliga siffror som är kvar att använda i nästa runda. I varje iteration når vi antingen ett rekursionsfall eller basfall. I rekursionsfallet kontrollerar vi om vi har ett giltigt tal enligt instruktionerna och lägger till en ny siffra till talet. Om vi når ett basfall har vi antingen hittat svaret, eller kommit till en återvändsgränd.
Låt oss säga att vi bara får använda de tre siffrorna 1, 2 och 3. Sökträdet kan då visualiseras som i figuren nedan:
I detta fall hittar vi två lösningar: 123 och 321. Vi kan kontrollera att båda dessa stämmer:
123:
- 1 är delbart med 1, då 1/1 = 1
- 12 är delbart med 2, då 12/2 = 6
- 123 är delbart med 3, då 123/3 = 41
321:
- 3 är delbart med 1, då 3/1 = 3
- 32 är delbart med 2, då 32/2 = 16
- 321 är delbart med 3, då 321/3 = 107
Låt oss översätta denna kunskap till python. Vi börjar med att definiera vår uppsättning startsiffror.
Härnäst definierar vi vår funktion som rekursivt bygger numret. Varje gång funktionen körs kommer en ny siffra läggas till, vilket minskar antalet tillgängliga siffror allt eftersom.
Funktionen måste också veta om den stött på ett basfall. Den måste kontrollera om talet följer reglerna och att det inte börjar med noll. Här är reglerna:
- Talet är inkorrekt om det inte är delbart med sin egen längd (som exempel: 12 måste vara delbart med 2 och 123 delbart med tre).
- Ett tal med två eller fler siffror kan inte börja med 0.
- Talet är korrekt om alla siffror är använda.
Låt oss lägga till dessa kontroller i toppen av funktionen.
Allt som återstår är att köra koden. Vi börjar med en tom sträng och låter funktionen fylla i resten! Funktionen returnerar falskt om ingen lösning hittas. Annars får vi tillbaka den korrekta lösningen.
Vi måste också lägga till en if-sats för att ignorera det första fallet av en tom sträng. Det gör vi enkelt med följande rad:
Det är allt! Testa att köra koden och se svaret på denna gåta ploppa ut!
Svar: 3816547290
Testa att köra koden med färre siffror och hitta fler lösningar.
Intressant nog fungerar pusslet bara med siffrorna [0], [0, 1], [0, 1, 2], [0, 1, 2, 3, 4, 5, 6, 7, 8], och [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. För att hitta alla lösningar, spara resultatet i en lista istället för att returnera det. Den färdiga koden nedan ger alla lösningar.
Färdig kod
Sammanfattning
Trots att matematik med penna och papper kan ge vackra och robusta bevis, kan att experimentera med kod vara ett snabbt sätt att hitta möjliga lösningar. John Conway efterlämnade en serie roliga gåtor vilka alla är grymma möjligheter att öva sin problemlösningsförmåga. Och återigen kan Python ofta komma till undsättningen!
Källor som användes i den här artikeln
Bellos, Alex; Did you solve it? John Horton Conway, playful maths genius; The Guardian ; 2020; https://www.theguardian.com/science/2020/apr/20/did-you-solve-it-john-horton-conway-playful-maths-genius,
Pradeep, Mutalik; Celebrating the Playful Magic of John Horton Conway; Quanta Magazine ; 2020; https://www.quantamagazine.org/three-math-puzzles-inspired-by-john-horton-conway-20201015/,
Pradeep, Mutalik; How to Solve Our Three John Conway-Inspired Puzzles; Quanta Magazine ; 2020; https://www.quantamagazine.org/how-to-solve-our-three-john-conway-inspired-puzzles-20201120/,