Eräässä kuningaskunnassa kuningas pitää luvuista, joilla on seuraava ominaisuus: kun luvun ensimmäisen ja viimeisen numeron paikat vaihdetaan, jakojäännös kahdella, kolmella, kuudella ja seitsemällä jaettaessa ei muutu. Kuningas päättää uudistaa maassa käytettävän lukujärjestelmän mieltymystensä mukaiseksi ja päättää, että jatkossa kaikki luvut on ilmaistava k-kantaisessa lukujärjestelmässa, missä k on positiivinen kokonaisluku. Mikä on pienin k, jonka kuningas voi valita, jotta kaikki kokonaisluvut tässä lukujärjestelmässä ilmaistuna olisivat hänen mieleensä?
Pulmatehtävä
Anonyymi
6158
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 6
Vanhimmat
Tarkoittaako tehtävä sitä, että kun jaetaan kahdella niin jakojäännös on molemmissa tapauksissa sama, esim. 1 ja kun jaetaan kolmella, jakojäännös om kummallakin kerralla esim. 2? Vai tarkoitetaanko sitä että kaikissa jaoissa on sama jakojäännös, siis esim. 0 tai sitten 1?
Hyvä kysymys, kyseessä on tuo ensimmäinen vaihtoehto. Kysymys olisi ehkä ollut selkeämpi, jos siinä olisi lukenut "tai seitsemällä" eikä "ja seitsemällä".
Järjestelmän kaksinumeroisille luvuille täytyy päteä (q=2,3,6,7)
a_1 * k a_0 ≡ a_0 * k a_1 (mod q)
Asetetaan a_1 =1 ja a_0 = 0, jolloin
k ≡ 1 (mod q)
Kiinalaisen jäännöslauseen mukaan ensinnäkin q=6 seuraa jos yhtälö toimii q=2 ja q=3:lle, joten 6 voidaan unohtaa. Ja ratkaisu yhtälöryhmälle (modulot q=2,3,7) saadaan
k = 3*7*(1)*1 2*7 * (2) * 1 2*3*(-1)*1
= 43
ja yleinen ratkaisu on siis 43 n*42, missä n kokonaisluku.
Toisessa muodossahan se voidaan antaa 1 42n, ja tuo ratkaisu k=1 olisi tietysti voitu nähdä heti. Mutta k=1 on lukujärjestelmän kantalukuna hieman huono. Noh sehän olisi tukkimiehen kirjanpito eli niin monta viivaa kuin esitettävä luku on, tai nolliako ne olisi? Hieman oudolta tuntuu, kun ne turhat nollathan haluaisi pyyhkiä pois ja näin jokainen luku olisi vain 0. Sitä paitsi käytimme jo ylhäällä merkkejä 0 ja 1, joten oletetaan k>1.
Valitaan siis ratkaisu k=43 ja huomataan, että se toimii, koska ensimmäinen merkki n-pituisessa luvussa x=(a_n...a_0)_k antaa kontribuution
a_n * k^n ≡ a_n * 1^n = a_n,
joten modulo q (=2,3,7 ja 6 toimii sillä 2 ja 3 toimii) ei ole itse asiassa väliä missä paikassa mikäkin merkki on, joten niitähän saa permutoida miten haluaa.
Näinhän tämä tietysti ratkeaa! Hyvä havainto, että myös tukkimiehen kirjanpito toimii, sitähän kuningas ei ole tajunnut sulkea pois.
a = b (m) tarkoittaa että a on kongruentti b:n kanssa modulo m eli että m l (a - b).
Olkoon k-järjestelmässä ( k kokonaisluku > 1) luku
X = a(n) k^n ... a(1) k a(0) ja olkoon
X' = a(0) k^n a(n-1) k^(n-1) ... a(n)
X - X' = ( a(n) - a(0) ) (k^n - 1)
Täytyy olla X = X' (2) ja (3) ja (6) ja (7).(Koska luvut a(i) voivat olla mitä hyvänsä kokonaislukuja < k niin jotta tehtävän ehdot täyttyvät täytyy olla niin, että
k^n - 1 = 0 (2)
k^n - 1 = 0 (3)
k^n - 1 = 0 (6)
k^n - 1 = 0 (7)
Näin ollen siis 42 l ( k^n - 1) eli k^n - 1 = a*42 eli k^n = a*42 1. Pienin näistä on luku missä a = 1 ja n = 1 eli k = 43.
Sanotaan nyt vielä varmuuden vuoksi että jos 42 l (43^n - 1) sillä ihan yleisesti
(x-1) l (x^n - 1).
Viimeisessä lauseessa sana "jos" liikaa.