111. Multipli di n con somma delle cifre n
111. Multipli di n con somma delle cifre n
Per ogni intero $n>0$ dimostrare che esiste un intero $f(n)>0$ tale che $n\mid f(n)$ e $s(f(n))=n$ (dove $s(x)$ indica la somma delle cifre di $x$).
The only goal of science is the honor of the human spirit.
Re: 111. Multipli di n con somma delle cifre n
Ok, ci sono quasi... Anzitutto possiamo escludere i casi più banali, quelli a una cifra, dove poniamo semplicemente $f(n)=10n$ e siamo a posto. Ora, ogni potenza di 10 con esponente naturale è congrua a un determinato valore modulo n. Esempio: n=7 ci dà che 1 è congruo a 1, 10 è congruo a 3, 100 è congruo a 2 e così via. Supponiamo (1) che per ogni n esistano infinite potenze di 10 congrue a 1. Gli $f(n)$ richiesti si potranno ricavare semplicemente scegliendo 0 come valore del coefficiente delle potenze congrue a un valore diverso da 1, e 1 come coefficiente di quelle che sono congrue a 1, in modo che nella scrittura del numero $f(n)$ in base decimale tale cifra compaia esattamente n volte. Ed ecco qua. Ora devo dimostrare la supposizione (1).
Re: 111. Multipli di n con somma delle cifre n
Ok, la (1) era falsa, basta prendere un multiplo di 2 o 5 per rendersi conto che non puoi ottenere tanti multipli nella forma 9999...99 quanti vuoi (è indispensabile perché la potenza di 10 risulti congrua a 1), però posso sostituirla con un'altra... in fondo non è necessario che la congruenza sia esattamente 1, l'importante è che sia sempre la stessa. Esempio: n=12, per ogni potenza di 10 con esponente maggiore di 1 ho la congruenza a 4, e anche solo attribuendo coefficiente 1 a tutte le potenze congrue a 4 mi assicuro la divisibilità del numero per 12 (ovviamente suppongo di mantenere 0 come coefficiente delle potenze non congrue a 4. La soluzione è vicina...
Re: 111. Multipli di n con somma delle cifre n
Ecco, sì, ci sono: chiamiamo serie congrua la successione delle congruenze modulo n delle potenze di 10 per ogni n. Ad esempio, la serie congrua di 2 è 1-0-0-0-0..., quella di 3 è 1-1-1-1..., quella di 7 è 1-3-2-6... e così via. Vi sono (2) tre classi di interi: quelli che generano serie congrue che terminano con una successione infinita di zeri (potenze di 2 e 5), quelle che ripetono periodicamente una stessa serie (prodotti di fattori diversi da 2 e 5) e quelle "miste" che ripetono una serie periodica solo dopo un iniziale "antiperiodo" riferito alle potenze di 10 minori (se volete posso dimostrarlo). Per gli n appartenenti alla seconda e terza classe, siamo a posto: coefficiente 1 per le congruenze uguali, 0 per quelle diverse. Per gli altri... boh, non ci dovrebbe essere problema, perché arrivati oltre una certa soglia le potenze sono tutte congrue a zero, perciò possiamo manipolarle come ci pare e piace senza influire sulla divisibilità, fino a ottenere un $f(n)$ tale che la somma delle sue cifre valga effettivamente n. Uhm... se aspettate formalizzo anche quest'ultimo aspetto.
Re: 111. Multipli di n con somma delle cifre n
Benissimo, benissimo, allora: se $f(n)$ appartiene alla prima classe, perché sia divisibile per n è sufficiente (3) che lo sia il numero formato dalle sue ultime k cifre (non è importante conoscere con esattezza il valore di k, basti sapere che non è minore del numero di cifre di n). A questo punto, detto N il numero di cifre di n, basterà assegnare 0 al coefficiente delle (k-N) potenze di 10 che precedono le ultime N nella scrittura in base decimale, e alle ultime sostituire il numero stesso. Ad esempio, un $f(n)$ che termini con ...00016 è divisibile per 16, e così via. Poiché la somma delle ultime k cifre, in questo modo, non potrà mai superare n stesso (è evidente, poiché n ha più cifre), potremo far coincidere tale somma con n semplicemente manipolando i coefficienti delle potenze maggiori, che non influiscono sulla divisibilità.
c.v.d.
c.v.d.
Re: 111. Multipli di n con somma delle cifre n
Guarda ho letto tutto e credo l'idea l'hai capita, ma non potresti scriverla per bene dall'inizio? Basterebbero al massimo due righe..
The only goal of science is the honor of the human spirit.
Re: 111. Multipli di n con somma delle cifre n
Argh! In due righe non ce la farei mai... comunque, ecco il riassunto del mio ragionamento:
In base decimale ogni numero è rappresentato come somma di singole potenze di dieci, ognuna moltiplicata per un coefficente intero compreso tra 1 e 9. Ogni potenza di 10 è congrua a un dato valore modulo n. Chiamiamo serie congrua di n la successione di tali valori modulo n per ogni n, partendo da $10^0$ e andando in ordine crescente (es.: n=7, la serie congrua è 1-3-2-6...). Si può dimostrare che esistono due classi di serie congrue:
I- Le serie che terminano con una successione periodica di cifre diverse da zero (n contiene fattori diversi da 2 e 5)
II- Le serie che iniziano con una serie di cifre non nulle e terminano con una successione infinita di zeri (n è un prodotto di soli fattori 2 e 5)
Nel primo caso è possibile trovare $f(n)$ seguendo un semplice algoritmo: assegno valore 1 ai coefficienti di n potenze di 10 che abbiano la stessa congruenza (è possibile, perché ve ne sono infinite) e valore 0 a tutti gli altri. In questo modo la somma delle cifre di $f(n)$ sarà proprio n, e il numero sarà certamente divisibile per n. Questo perché la somma dei resti della divisione per n delle singole potenze di 10, ognuna contata esattamente una volta, sarà un multiplo di n.
Nel secondo caso scegliamo un numero che termini con una successione di cifre che presa isolatamente rappresenti n stesso, e la facciamo precedere da una serie di zeri sufficientemente lunga da garantire che le potenze di 10 precedenti non influiscano sulla divisibilità per n di $f(n)$ (perché congrue a 0 modulo n). Un esempio: 34536483700000016 è divisibile per 16. Ora che abbiamo garantito la divisibilità per n di $f(n)$, ci è sufficiente far sì che la somma delle sue cifre sia effettivamente uguale a n.
Se n è minore di 10, come $f(n)$ scegliamo 10n e siamo a posto. Se è maggiore o uguale a 10, la somma delle cifre a destra della successione di zeri è minore di n, perciò possiamo scegliere arbitrariamente (e ovviamente senza influire sulla divisibilità) quelle a sinistra in modo che sommate alle prime diano proprio n.
In base decimale ogni numero è rappresentato come somma di singole potenze di dieci, ognuna moltiplicata per un coefficente intero compreso tra 1 e 9. Ogni potenza di 10 è congrua a un dato valore modulo n. Chiamiamo serie congrua di n la successione di tali valori modulo n per ogni n, partendo da $10^0$ e andando in ordine crescente (es.: n=7, la serie congrua è 1-3-2-6...). Si può dimostrare che esistono due classi di serie congrue:
I- Le serie che terminano con una successione periodica di cifre diverse da zero (n contiene fattori diversi da 2 e 5)
II- Le serie che iniziano con una serie di cifre non nulle e terminano con una successione infinita di zeri (n è un prodotto di soli fattori 2 e 5)
Nel primo caso è possibile trovare $f(n)$ seguendo un semplice algoritmo: assegno valore 1 ai coefficienti di n potenze di 10 che abbiano la stessa congruenza (è possibile, perché ve ne sono infinite) e valore 0 a tutti gli altri. In questo modo la somma delle cifre di $f(n)$ sarà proprio n, e il numero sarà certamente divisibile per n. Questo perché la somma dei resti della divisione per n delle singole potenze di 10, ognuna contata esattamente una volta, sarà un multiplo di n.
Nel secondo caso scegliamo un numero che termini con una successione di cifre che presa isolatamente rappresenti n stesso, e la facciamo precedere da una serie di zeri sufficientemente lunga da garantire che le potenze di 10 precedenti non influiscano sulla divisibilità per n di $f(n)$ (perché congrue a 0 modulo n). Un esempio: 34536483700000016 è divisibile per 16. Ora che abbiamo garantito la divisibilità per n di $f(n)$, ci è sufficiente far sì che la somma delle sue cifre sia effettivamente uguale a n.
Se n è minore di 10, come $f(n)$ scegliamo 10n e siamo a posto. Se è maggiore o uguale a 10, la somma delle cifre a destra della successione di zeri è minore di n, perciò possiamo scegliere arbitrariamente (e ovviamente senza influire sulla divisibilità) quelle a sinistra in modo che sommate alle prime diano proprio n.
Re: 111. Multipli di n con somma delle cifre n
Penso va bene, anche se devi imparare a spiegarti meglio e almeno a scrivere il perchè la successione dei resti di $10^x$ e' periodica modulo $n$.
Ad ogni modo, questa e' la mia soluzione:
Detto $m:=\displaystyle \frac{n}{2^{\upsilon_2(n)}5^{\upsilon_5(n)}}$ e' sufficiente scegliere $x= \displaystyle 10^n \frac{10^{s(n)\varphi(m)}-1}{10^{\varphi(m)}-1}$. []
Ps. Vai col prossimo
Ad ogni modo, questa e' la mia soluzione:
Detto $m:=\displaystyle \frac{n}{2^{\upsilon_2(n)}5^{\upsilon_5(n)}}$ e' sufficiente scegliere $x= \displaystyle 10^n \frac{10^{s(n)\varphi(m)}-1}{10^{\varphi(m)}-1}$. []
Ps. Vai col prossimo
The only goal of science is the honor of the human spirit.
Re: 111. Multipli di n con somma delle cifre n
Dunque: prendiamo $10^x$ dove possiamo ingrandire x a piacere. Dividiamolo per n. I casi sono due:jordan ha scritto:Penso va bene, anche se devi [...] almeno scrivere il perchè la successione dei resti di $10^x$ e' periodica modulo $n$.
I- n contiene solo fattori 2 e 5. Per gli x più piccoli (precisamente quelli minori del maggiore tra y e z se $n=2^y*5^z$), la divisione non è esatta e dà resto. Da un certo x in poi, la divisione sarà sempre esatta e i resti saranno tutti uguali a zero.
II- n contiene fattori diversi da 2 e 5. $10^x$ non è divisibile per n per alcun x. Nella divisione di $10^x$ per n non comparirà mai il resto zero, né, ovviamente, potrà comparire un resto maggiore o uguale a n. I valori possibili sono perciò tutti e soli gli interi compresi tra 1 e (n-1). Ogni resto, a ogni divisione, ne genera uno e uno solo successivo. Esempio: n=7, suppongo di aver ottenuto resto 6 nella divisione. 60 : 7 = 8 resto 4, ho resto 4.
Esauriti i possibili valori da assegnare al resto, la successione si ripeterà necessariamente identica.
Quanto alla tua soluzione, devo studiarmi un po' di teoria per capirla
