Fången (2 poäng).
Kungen tänker på tre stycken tvåsiffriga tal: a, b och c. Fången måste hitta på tre tal själv och säga dem högt: X, Y och Z. Därefter säger kungen högt summan aX+bY+cZ. Då måste fången gissa rätt på vilka tre tal kungen tänkte från början, annars blir han avrättad.
Vilka tal X, Y och Z ska fången säga för att behålla livet?
Speciellt tal (5 poäng). Existerar det ett naturligt tal, som är större än 101000, som inte är delbart med 10 och som har åtminstone två olika siffror, och om man byter plats på dessa två siffror så förändrar inte talet mängden av sina primtalsdelare?
Visa lösningar
Fången (Lisas lösning):
Jag skulle rekommendera honom att välja talen X=10000, Y=100 och Z=1. Då kommer fången kunna räkna ut talen a, b och c genom att bara dela upp siffrorna i resultatet två och två. Antag t.ex. att summan aX+bY+cZ blir 235982. Då räknar fången lätt ut att a=23, b=59 och c=82.
Detta kan jämföras med vårt decimalsystem. Vi vet t.ex. att talet 512=5*100+1*10+2*1. Om talen a, b och c hade varit ensiffriga så hade fången kunnat välja talen 100, 10 och 1. Om dessa tal istället är tvåsiffriga måste vi låta talen X, Y och Z ha dubbelt så många nollor. På så sätt kommer inga siffror att adderas med annat än noll i multiplikationsalgoritmen och kommer alla vara skilda från varandra.
Speciellt tal (Skäggets lösning):
Låt oss finna ett naturligt tal som uppfyller de efterfrågade egenskaperna:
Betrakta talet 13 * 11…111 för någon följd av ettor. Det kommer vara på formen 144…4443.
Talet 31*11…111 för samma följd av ettor är lika med 344…44441, med samma antal fyror som ovan.
Vi observerar att det ena talet kan nås från det andra genom att byta plats på första och sista siffran. Från hur vi konstruerat talen vet vi att de har gemensamt alla primtalsdelare av 11…111. Om de, som vi vill, ska ha exakt samma primtalsdelare så måste både 13 och 31 dela 11…111, det vill säga att produkten av dem, 403, delar 11…111.
Så om vi lyckas visa att det finns någon sådan följd av ettor som delar 403, och som multiplicerat med 13 är större än 101000, då är vi klara.
Betrakta tal på formen 10^6x. Från Dirichlets lådprincip får vi att det garanterat finns två olika sådana tal som är lika modulo 403. Låt 10^6a och 10^6b vara ett sådant par av tal, där a > b. Differensen mellan dem är
10^6a – 10^6b = 99…900…0 = 9 * 11…1 * 10^6b
Eftersom 403 inte delar vare sig 9 eller 10^6b måste 403 dela 11…1. Antalet ettor är 6a-6b, alltså minst 6 stycken.
Alltså finns det en följd av ettor som är större eller lika med 111111 som är delbar med 403, och som därmed även är större än 101000. Därför har 13 gånger denna följd exakt samma primtalsdelare som 31 gånger den, och därmed har vi visat det vi ville.
