Multipli che si specchiano

[Cammy87]

Trovare tutti gli $ n $interi positivi tali che, se $ k $è un intero divisibile per $ n $, allora anche il numero che si ottiene scrivendo le cifre di $ k $ all'inverso (cioè da destra verso sinistra, come se si guardasse il numero allo specchio) è divisibile per $ n $.

E' abbastanza semplice! [A meno che non abbia fatto qualche errore ]

[Ani-sama]

$ k $ è un qualunque intero? Come prime risposte banali mi vengono $ n=3 $ e $ n=9 $, perché chiaramente un numero è divisibile per $ 3 $ o $ 9 $ in base alla somma delle sue cifre e non alla disposizione delle stesse, poi per altri numeri non so, penso sia sufficiente vedere i vari criteri di divisibilità... anche se ho come il sentore che 3 e 9 siano gli unici... magari (anzi, quasi sicuramente) mi sbaglio, eh... ed è anche tardi...

[Alex89]

Credo anche n=11, perchè i numeri sono divisibili per 11 se il valore assoluto della differenza tra le cifre che occupano posto pari e le cifre che occupano posto dispari è divisibile per 11. Questa differenza rimane invariato anche se il numero viene scritto al contrario.
Infatti supponiamo che un intero di 6 cifre, xyzabc sia divisibile per 11.

Quindi: |x+z+b-c-a-y|=11*k con k intero non negativo. Indichiamo x+z+b=m e c+a+y=n. L'uguaglianza di prima diventa |m-n|=11*k

Scritto all'inverso sarà: cbazyx e quindi la differenza sarà pari a |c+a+y-x-b-z| che è uguale a |n-m|, che per una proprietà dei valori assoluti (che |a-b|=|b-a|)
è uguale a |m-n|.

Quindi credo che n=11 sia una soluzione fattibile.

[Alex89]

E unendo quanto detto prima da me e da Ani-sama anche 33 e 99?

[Cammy87]

Ok! Le uniche soluzioni che ho trovato sono proprio $ 3 $,$ 9 $,$ 11 $,$ 33 $,$ 99 $e... $ 1 $!!!

Non penso ce ne siano altre, ma non so come dimostrarlo, se non considerando i criteri di congruenza degli altri numeri, ma non ho bene l'idea di come farlo.

[darkcrystal]

Secondo me c'è anche almeno 101, ma anch'io non so come dimostrarlo...
Posto un abbozzo di soluzione:
per ogni numero n esiste un multiplo formato da una serie di uni seguita da una serie di zeri (poi lo dimostro ).
Prendiamo il più piccolo multiplo di n di questo tipo.
Scrivendo al contrario le cifre di questo numero, si ottiene un altro numero dello stesso tipo (formato cioè da una serie di uni e una serie - vuota - di zeri). Questo numero "riflesso", essendo minore o uguale al precedente (può avere meno cifre) può essere divisibile per n se e solo se è uguale al suo riflesso: in altri termini se esiste un multiplo di n formato da sole cifre 1.
Però qui mi sono arenato, non essendo in grado di trovarli tutti...
Quanto alla dimostrazione della prima parte, basta prendere gli n+1 numeri formati da 1,2,3,4...n,n+1 cifre 1: ce ne saranno due congrui tra loro modulo n, e perciò la differenza sarà un multiplo di n, costituito da una serie di uni seguita da una serie di zeri.

[Pigkappa]

97465 è multiplo di 101, 56479 no

[darkcrystal]

Ah grazie!

[ficus2002]

...se esiste un multiplo di n formato da sole cifre 1.
Però qui mi sono arenato, non essendo in grado di trovarli tutti...

però questa è una condizione solo necessaria, ma non in generale sufficiente. Infatti, 111111 è un multiplo n=7, ma non tutti i multipli d 7 sono rivoltabili allo specchio: per esempio 21 e multiplo di 7 ma 12 no.

Con questa osservazione, però, escludiamo tutti i numeri la cui ultima cifra non è primo con 10 (infatti questi numeri non hanno multipli formati da solo 1).

Volevo aggiungere un'ultima cosa: se n soddisfa alle proprietà richieste, allora la sua prima cifra da destra non supera la cifra delle unità. Se queste coincidono, allora la sua seconda cifra da destra non supera la cifra delle decine...e cosi' via

Quanto alla dimostrazione della prima parte, basta prendere gli n+1 numeri formati da 1,2,3,4...n,n+1 cifre 1: ce ne saranno due congrui tra loro modulo n, e perciò la differenza sarà un multiplo di n, costituito da una serie di uni seguita da una serie di zeri.

Grande! forte questa dimostrazione!

[darkcrystal]

...se esiste un multiplo di n formato da sole cifre 1.
Però qui mi sono arenato, non essendo in grado di trovarli tutti...

però questa è una condizione solo necessaria, ma non in generale sufficiente.

Si, si, ovviamente la intendevo come condizione necessaria, per poter escludere un po' di valori. Del resto è anche vero che escludendo un n si escludono tutti i suoi multipli, quindi penso che siamo abbastanza vicini alla soluzione... ma ci manca ancora qualcosa!
Ciao a tutti!

[Cammy87]

Mi viene in mente che per costruire il criterio di congruenza $ \pmod n $, bisogna considerare i resti delle potenze di $ 10 $. Pensavo quindi che affinchè un numero soddisfi le richieste deve avere un criterio di congurenza simmetrico.
Provo a spiegarmi meglio:
$ 10 \equiv{-1}\pmod{11} $
$ 10^2 \equiv{+1}\pmod{11} $ ... e così via quindi un numero $ abcd $ è multiplo di 11 se $ -a+b-c+d=11k $. E' un'espressione simmetrica(se $ k=0 $ posso cambiare i segni) , quindi se un numero è multiplo di 11 lo è anche il suo simmetrico.
Lo stesso vale per 3, 9, 33 e 99, mentre, per esempio, la congruenza modulo 7 è data da $ +5a+4b-c+2d+3e+f $ e non c'è simmetria a meno di casi particolari, come un numero formato da 6 cifre 1.
Non ho la più pallida idea, però, di come poter dimostrare che non ci siano altri numeri che diano criteri di congruenza di tale genere!!

[ficus2002]

sembrerebbe vero anche con 111, 333, 999, 1111, 3333, 9999...

[Marco]

Trovare tutti gli $ \scriptstyle n $interi positivi tali che, se $ \scriptstyle k $è un intero divisibile per $ \scriptstyle n $, allora anche il numero che si ottiene scrivendo le cifre di $ \scriptstyle k $ all'inverso (cioè da destra verso sinistra, come se si guardasse il numero allo specchio) è divisibile per $ \scriptstyle n $.

Ciao. A me non è parso facillimo... ma forse sono io che non vedo la soluzione facile...

Ecco la mia: i numeri per cui è vero sono tutti e soli i divisori di 99. La parte "tutti" è facile e sostanzialmente l'avete già postata. La parte "soli":

Sia $ \scriptstyle n $ un intero per cui la proprietà è vera, ossia per cui scrivendo a specchio ogni suo multiplo, si ottiene ancora un multiplo di $ \scriptstyle n $. Indicherò l'operazione di specchiatura sovrascrivendo una barra.

Lemma 1: Siano $ \scriptstyle n $ un intero positivo, $ \scriptstyle k $ il numero di cifre di $ \scriptstyle n $ e $ \scriptstyle t $ un qualunque intero positivo. Allora esiste $ \scriptstyle N $, multiplo di $ \scriptstyle n $ tale che, cancellandogli le ultime (=meno significative) $ \scriptstyle k $ cifre, si ottiene il numero $ \scriptstyle t $.

Dim.: Se $ \scriptstyle t 10^k $ è divisibile per $ \scriptstyle n $, ho finito. Altrimenti, sia $ \scriptstyle q $ il quoziente della divisione di $ \scriptstyle t 10^k $ per $ \scriptstyle n $. Allora $ \scriptstyle n(q + 1) $ è un multiplo che va bene. []

Corollario: Ogni intero positivo $ \scriptstyle n $ ha un multiplo, la cui cifra più significativa è 1.

Claim 1: Se $ \scriptstyle n $ verifica la proprietà, allora non è divisibile né per 2, né per 5.

Dim.: Per il Corollario, esiste un multiplo di $ \scriptstyle n $, che chiamo $ \scriptstyle N $, che inizia per 1. Allora $ \scriptstyle \bar N $ finisce per 1. Deve essere multiplo di $ \scriptstyle n $, ma per i criteri di divisibilità, non può essere multiplo né di 2, né di 5. []

Claim 2: Se $ \scriptstyle n $ verifica la proprietà, allora è un divisore di 99.

Siano $ \scriptstyle A $ e $ \scriptstyle B $ due multipli di $ \scriptstyle n $. Indichiamo con $ \scriptstyle a $ l'ultima cifra di $ \scriptstyle A $ e con $ \scriptstyle a' $ la penultima; indichiamo con $ \scriptstyle b $ la prima cifra di $ \scriptstyle B $ e con $ \scriptstyle b' $ la seconda. Abbiamo provato che l'ultima cifra di $ \scriptstyle n $ è diversa da zero.

Lemma 2: Se $ \scriptstyle n $ è un intero la cui ultima cifra è diversa da zero, allora è possibile scegliere due multipli di $ \scriptstyle n $, $ \scriptstyle A $ e $ \scriptstyle B $, tali che:
- hanno entrambi $ \scriptstyle k $ cifre, con $ \scriptstyle k > 1 $
- $ \scriptstyle a + b > 9 $
- $ \scriptstyle a' \neq 9 $, $ \scriptstyle b' \neq 9 $

Dim.: Dopo.

Si tratta di un enunciato "ad orologeria". Ma serve per garantire che certe specchiature prendano la forma giusta. L'idea è di creare una somma di multipli di $ \scriptstyle n $, con un solo riporto in una posizione ben determinata. Ecco come:

Costruiamo il numero $ \scriptstyle N = 10^{k-1} A + B $. Esso è fatto il modo tale che le cifre di $ \scriptstyle A $ e quelle di $ \scriptstyle B $ siano sfalsate e si sovrappongano solo in corrispondenza della $ \scriptstyle k $-ma cifra. Per come abbiamo scelto $ \scriptstyle A $ e $ \scriptstyle B $, siamo sicuri che in corrispondenza della $ \scriptstyle k $-ma cifra di $ \scriptstyle N $ vi sia una somma con riporto. Inoltre, dato che le cifre adiacenti sono più piccole di 9, siamo certi che il riporto non si propaga a cifre più distanti.

Ne segue che la notazione decimale di $ \scriptstyle N $ è fatta:
$ \scriptstyle N = [ $prime $ \scriptstyle k-2 $ cifre di $ \scriptstyle A] (a'+1) (a+b-10) (b') [ $ultime $ \scriptstyle k-2 $ cifre di $ \scriptstyle B] $

Esso, essendo combinazione intera di $ \scriptstyle A $ e $ \scriptstyle B $, è multiplo di $ \scriptstyle n $, quindi anche il suo specchiato lo è. Scriviamolo:
$ \scriptstyle \bar N = [ $prime $ \scriptstyle k-2 $ cifre di $ \scriptstyle \bar B] (b') (a+b-10) (a'+1) [ $ultime $ \scriptstyle k-2 $ cifre di $ \scriptstyle \bar A] $

Sia ora $ \scriptstyle \hat N = 10^{k-1} \bar B + \bar A $. Ripeto il ragionamento e trovo che è un multiplo di $ \scriptstyle n $, e che si scrive:
$ \scriptstyle \hat N = [ $prime $ \scriptstyle k-2 $ cifre di $ \scriptstyle \bar B] (b'+1) (a+b-10) (a') [ $ultime $ \scriptstyle k-2 $ cifre di $ \scriptstyle \bar A] $

$ \scriptstyle \hat N $ e $ \scriptstyle \bar N $ sono due numeri divisibili per $ \scriptstyle n $, quindi anche la loro differenza lo è:
$ \scriptstyle \hat N - \bar N = 10^k - 10^{k-2} = 99 \cdot 10^{k-2}. $

Però $ \scriptstyle n $ non può avere fattori primi 2 e 5, quindi $ \scriptstyle n \mid 99 $. []

Giusto per scendere un attimo sulla Terra: faccio vedere come costruire un controesempio per $ \scriptstyle n=101 $. Prenderò $ \scriptstyle A = 101 $ e $ \scriptstyle B = 909 $. Si vede che valgono le ipotesi del Lemma 2.

Risulta che $ \scriptstyle N = 101 \cdot 100 + 909 = 11009 $. $ \scriptstyle \bar N = 90011 $ e $ \scriptstyle \hat N = 909 \cdot 100 + 101 = 91001 $. Effettivamente succede che $ \scriptstyle \hat N - \bar N = 990 $.

Questo conclude il problema. Manca la dimostrzione del Lemma 2. Eccola:

Dim.: Troviamo prima $ \scriptstyle A $. Sia $ \scriptstyle A $ un multiplo di $ \scriptstyle n $ con almeno due cifre in più rispetto ad $ \scriptstyle n $.

E' possibile scegliere $ \scriptstyle A $ con l'ultima cifra diversa da 0 e la penultima cifra diversa da 9.

Sono certo che esiste: per esempio, almeno uno tra $ \scriptstyle n $, e $ \scriptstyle 99n $ non ha penultima cifra 9 o ultima cifra 0 (altrimenti la somma non potrebbe finire per 00) [si ricordi che l'ultima cifra di $ \scriptstyle n $ è diversa da 0 per ipotesi].

Per il Lemma 1, esiste $ \scriptstyle B $ che è un multiplo di $ \scriptstyle n $, che inizia per 90 e ha tante cifre quante quelle di $ \scriptstyle A $. $ \scriptstyle A $ e $ \scriptstyle B $ così trovati verificano le ipotesi, e ho finito. []

[Cammy87]

Ciao. A me non è parso facillimo... ma forse sono io che non vedo la soluzione facile...

Ecco la mia: i numeri per cui è vero sono tutti e soli i divisori di 99. La parte "tutti" è facile e sostanzialmente l'avete già postata. La parte "soli":

Hai ragione Marco, la parte facile era soltanto la prima, che era quella che avevo fatto. La parte "soli" è quella che mi creava problemi, ora leggo la tua soluzione, poi ti chiedo se non ho capito qualcosa, grazie. Ciao

[ficus2002]

Ecco la mia: i numeri per cui è vero sono tutti e soli i divisori di 99. La parte "tutti" è facile e sostanzialmente l'avete già postata. La parte "soli":

Bella dimostrazione! ho solo un'obiezione nella dimostrazione del lemma 2:

... Sia $ \scriptstyle A $ un multiplo di $ \scriptstyle n $ con almeno due cifre in più rispetto ad $ \scriptstyle n $...
Sono certo che esiste: per esempio, almeno uno tra $ \scriptstyle n $, e $ \scriptstyle 99n $...

se $ 99n $ finisce con $ 90 $, non si può scegliere $ A=n $ perchè $ A $ deve avere almeno due cifre in più di $ \scriptstyle n $