Keskustelu: Yleinen keskustelu: Pikkupulma: luvun kääntäminen

Toivottavasti jotakuta kiinnostaa pieni pulma, jonka voi ratkaista ilman ohjelmointiakin. Pikku ohjelmalla on ehkä helpompaa. Tarkan todistuksenkin toki saa esittää.

Olkoon luvun kymmenkantainen kääntö sellainen luku, jossa on samat numerot kuin alkuperäisessä luvussa, mutta niiden järjestys on käänteinen. Siten luvun 1093 kääntö on 3901 ja luvun 3500 kääntö on 0053, eli 53.

Etsi sellaiset kokonaislukukertoimet väliltä 2 <= k <= 9, että ne kääntävät jotain vähintään kaksinumeroisia lukuja. Kuvaile myös luvut, jotka ne kertoimet kääntävät.

Toisin sanoen, pitää löytää kerroin k ja kaikki luvut n, siten että k*n = n:n kääntö.

Tapaus yksi on triviaali. Se kääntää kaikki palindromiset luvut, joita on ääretön määrä. Siksi tehtävä alkaa kahdesta.

Vastaus yhden tapauksessa olisi esim. seuraavaa muotoa.

Luku 1 kääntää luvut 11, 22, 33, .., 99, 101, .., koska 1*11 = 11 ja 11 käännettynä on 11 ja tilanne on vastaava kaikilla palindromisilla luvuilla.

Kaipa näitä pulmasia saa postailla, aina kun keksii (tai lainaa jostakin). Paremmat tarjoan joskus Putkapostiin, jos niitä tulee mieleen ;-)

Hauska pikku tehtävä.

Näin itse ratkoin:

Tutkimalla alkeellisin menetelmin miten luvun pituus, sekä ensimmäinen ja viimeinen numero käyttäytyvät kertolaskussa, voidaan äkkiä todistaa kertoimet 2,3,5,6,7,8 mahdottomiksi.

Lyhyenä esimerkkinä tapaus k = 5: Huomataan, että jotta luku 5*n voisi olla ännän kääntö, on ännän ensimmäisen numeron vasemmalta oltava 1 (Muutoin 5*n:ssä olisi yksi numero enemmän kuin n:ssä, mikä ei kävisi päinsä). Tämä on kuitenkin mahdotonta, sillä kääntö 5*n voi päättyä vain numeroihin 0 ja 5, ja käännön viimeinen numero on sama kuin ännän ensimmäinen.

Loput mahdottomat kertoimet menevät saman tapaisesti.

Jäljelle jäävät tapaukset k = 4 ja k = 9, joille löytyy kuin löytyykin kääntyviä änniä. Niiden löytäminen on hieman mutkikkaampaa kuin alun tapausten todistelu, mutta ne löytyvät kuitenkin samankaltaisilla menetelmillä, eli tutkimalla ensimmäistä ja viimeistä numeroa, ja jatkamalla hieman rekursiivisesti sisempiin numeroihin.

Lopputuloksena ainoat mahdolliset k:n arvot ovat 4 ja 9. Arvolla k = 4 kääntyvät luvut ovat muotoa {2178,21978,219978, ...}, ja arvolla k = 9 muotoa {1089, 10989, 109989, ..}.

C++ varmistaa asian:

#include <iostream>
using namespace std;

int reverse(int a)
{
    int uusiluku = 0;

    while (a)
    {
        uusiluku*=10;
        uusiluku+=a%10;
        a/=10;
    }

    return uusiluku;
}

int main()
{
    int k;

    cout<<"Anna kerroin k:";
    cin>>k;

    for (int a = 10; a < 1000000; a++)
    {
        if (a*k == reverse(a))
        {
            cout<<a<<endl;
        }
    }

    return 0;
}

Näinhän se on. Kiitos esimerkkiratkaisusta.