Problema olimpico!!
Ragazzi, vi chiedo di spiegarmi la soluzione a questo problema, tratto dalle Gare di Febbraio del 2006.
"Un numero si dice "moderno" se, in base 10, può essere espresso concatenando " un po' " di scritture decimali di 2006. Per esempio, il numero 200620062006 è moderno, mentre 20062006200 e 202006200606 non lo sono. Quante cifre ha il più piccolo quadrato perfetto moderno positivo?"
Se volete potete risolverlo voi, altrimenti posto la soluzione: proprio là sta il problema, non ho capito la soluzione...
Grazie e spero ke rispondiate presto!
"Un numero si dice "moderno" se, in base 10, può essere espresso concatenando " un po' " di scritture decimali di 2006. Per esempio, il numero 200620062006 è moderno, mentre 20062006200 e 202006200606 non lo sono. Quante cifre ha il più piccolo quadrato perfetto moderno positivo?"
Se volete potete risolverlo voi, altrimenti posto la soluzione: proprio là sta il problema, non ho capito la soluzione...
Grazie e spero ke rispondiate presto!
Risposte
piccolo lemma TdN:
un numero è quadrato sse =0,1(mod4); ovvero se pari deve essere multiplo di 4, se dispari deve dare resto 1 nella divisione per 4. adesso ogni numero di quel tipo è divisibile per 2006, ed ha la forma 2006*10011001... ed è pertanto pari.
ma 2006=2(mod4),100110011001...=1(mod4) quindi il loro prodotto è =2(mod4) ,quindi non è un quadrato perfetto
un numero è quadrato sse =0,1(mod4); ovvero se pari deve essere multiplo di 4, se dispari deve dare resto 1 nella divisione per 4. adesso ogni numero di quel tipo è divisibile per 2006, ed ha la forma 2006*10011001... ed è pertanto pari.
ma 2006=2(mod4),100110011001...=1(mod4) quindi il loro prodotto è =2(mod4) ,quindi non è un quadrato perfetto
Soluzione a dir poco perfetta.
Il mio problema sta qua: come mai un numero è un quadrato se è =0,1(mod4)?
Per esempio, 13=1(mod4), ma non è un quadrato perfetto...
Il mio problema sta qua: come mai un numero è un quadrato se è =0,1(mod4)?
Per esempio, 13=1(mod4), ma non è un quadrato perfetto...
"fedeb":
piccolo lemma TdN:
un numero è quadrato sse =0,1(mod4); ovvero se pari deve essere multiplo di 4, se dispari deve dare resto 1 nella divisione per 4. adesso ogni numero di quel tipo è divisibile per 2006, ed ha la forma 2006*10011001... ed è pertanto pari.
ma 2006=2(mod4),100110011001...=1(mod4) quindi il loro prodotto è =2(mod4) ,quindi non è un quadrato perfetto
Aspetta aspetta: se un numero è un quadrato, allora è congruo a 0 o a 1 in modulo 4, ma non vale il viceversa. Ad esempio $5$ è congruo a $1$ modulo $4$ ma non è certo un quadrato. Cioè, essere congruo a 0 o a 1 in modululo 4 è condizione NECESSARIA, ma non SUFFICIENTE. Vale quindi $n$ è un quadrato => $n equiv 0,1(mod4)$, ovvero $n equiv 2,3 (mod 4) => n$ non è un quadrato. Per il resto la spiegazione di fedeb è corretta.
ok grazie mille.
Quindi per esempio, se fosse stato moderno un numero con le stesse caratteristiche, ma con al posto di "2006" un "2008", sarebbe stato più difficile il problema... capisco.
Quindi per esempio, se fosse stato moderno un numero con le stesse caratteristiche, ma con al posto di "2006" un "2008", sarebbe stato più difficile il problema... capisco.
ha ragionissima alvinlee, mi sono lasciato trasportare da quel ''sse'' molto seducente
quel che volevo dire io è che se un dispari è quadrato allora è =1(mod4)
dimostrazione
$n=2j+1$ è un qualsiasi numero dispari. allora $n^2=4j^2+4j+1=4M+1=1(mod4)$
spero di essermi fatto perdonare con questa prelibatezza di difficilissima comprensione...
quel che volevo dire io è che se un dispari è quadrato allora è =1(mod4)
dimostrazione
$n=2j+1$ è un qualsiasi numero dispari. allora $n^2=4j^2+4j+1=4M+1=1(mod4)$
spero di essermi fatto perdonare con questa prelibatezza di difficilissima comprensione...
se il numero fosse stato composto da 2008, dovevi cercare di dimostrare che nella sua fattorizzazione in primi quel numero aveva almeno un primo con molteplicità dispari (ovvero nessun esponente dei numeri primi che lo compongono poteva essere pari). non l'ho fatto ma non credo che sia difficile...
sempre relativamente a quell'anno, guardati il problema con dimostrazione di TdN; era il primo anno che facevo le oli di febbraio, e guarda che roba mi è capitata... non posso negare di esserci rimasto molto ma molto male...
sempre relativamente a quell'anno, guardati il problema con dimostrazione di TdN; era il primo anno che facevo le oli di febbraio, e guarda che roba mi è capitata... non posso negare di esserci rimasto molto ma molto male...
Ho guardato quel problema di Tdn, fedeb, devo dire che non l'avrei mai dimostrato così 
Un metodo però piuttosto semplice (quello che ho usato io) per arrivare alla soluzione (non per dimostrarla) è il seguente. Il testo chiede di determinare in funzione di $k>=1$ il numero di interi positivi $n$ con le seguenti proprietà: 1) in base dieci si scrivono con $k$ cifre, tutte dispari
2)sono divisibili per $5$, e il quoziente $n/5$, scritto in base 10, ha ancora $k$ cifre, tutte dispari.
Osservi che l'ultima cifra deve essere $5$, perchè affinchè un numero sia divisibile per $5$ deve avere come ultima cifra o $0$ o $5$, ma $0$ non è accettabile perchè le cifre devono essere tutte dispari. Ho quindi una sola scelta per l'ultima cifra. Scriviamo il generico $n=(2a_(k-1) +1)*10^(k-1)+...+(2a_2 +1)*10^2+ (2a_1+1)*10+5$, con $0<=a_i<=4$, per ogni $1<=i<=k-1$. Affinchè $n/5$ abbia ancora $k$ cifre, per ogni $k$deve essere che $((2a_(k-1) +1)*10^(k-1))/5 >= 10^(k-1)$, con $0<=a<=4$, cioè $2<=a<=4$, da cui le possibili cifre dispari per $n$ sono $5$ o $7$ o $9$. Vediamo poi che dividendo per 5 $x*10^(k-1)$, con $x=5,7,9$ otteniamo SEMPRE come prima cifra del quoziente $1$, seguito da un $4$ e poi da $10^(k-2)$ zeri nel caso il numero di partenza fosse un $7$ o seguito da un $8$ e poi da $10^(k-2)$ zeri nel caso il dispari di partenza fosse $9$ (ovviamente se il dispari si partenza era $5$, otteniamo solo $1*10^(k-1)$). Ne segue che il primo numero di $n/5$ è $1$, dispari, e va bene. La seconda cifra sarà invece $0+1=1$, $4+1=5$ ,$8+1=9$, se, nell'ordine, la prima cifra di $n$ era $5$, $7$, o $9$. e così via per le altre cifre, verificando quindi (non mi azzardo a definire questo sgorbio una dimostrazione ) che tutte le cifre di $n/5$ sono dispari, e precisamente sono $1$,$5$ o $9$. Sono dunque rispettate tutte le condizioni del problema, e quindi, ricapitolando, abbiamo, per $n$: una scelta per l'ultima cifra, e $3$ scelte (5,7,9) per le restanti $k-1$ cifre per un totale di $1*3^(k-1)=3^(k-1)$ possibili $n$. Ripeto, una dimostrazione decente la trovate qui http://www.matematicadivertente.com/sec ... lo2006.pdf
P.s in tutto il post ho usato il termine "prima cifra" per indicare la cifra all'inizio della scrittura del numero, mentre per ultima cifra ho inteso proprio l'ultima, quella in fondo a destra, come il bagno.
Un metodo però piuttosto semplice (quello che ho usato io) per arrivare alla soluzione (non per dimostrarla) è il seguente. Il testo chiede di determinare in funzione di $k>=1$ il numero di interi positivi $n$ con le seguenti proprietà: 1) in base dieci si scrivono con $k$ cifre, tutte dispari
2)sono divisibili per $5$, e il quoziente $n/5$, scritto in base 10, ha ancora $k$ cifre, tutte dispari.
Osservi che l'ultima cifra deve essere $5$, perchè affinchè un numero sia divisibile per $5$ deve avere come ultima cifra o $0$ o $5$, ma $0$ non è accettabile perchè le cifre devono essere tutte dispari. Ho quindi una sola scelta per l'ultima cifra. Scriviamo il generico $n=(2a_(k-1) +1)*10^(k-1)+...+(2a_2 +1)*10^2+ (2a_1+1)*10+5$, con $0<=a_i<=4$, per ogni $1<=i<=k-1$. Affinchè $n/5$ abbia ancora $k$ cifre, per ogni $k$deve essere che $((2a_(k-1) +1)*10^(k-1))/5 >= 10^(k-1)$, con $0<=a<=4$, cioè $2<=a<=4$, da cui le possibili cifre dispari per $n$ sono $5$ o $7$ o $9$. Vediamo poi che dividendo per 5 $x*10^(k-1)$, con $x=5,7,9$ otteniamo SEMPRE come prima cifra del quoziente $1$, seguito da un $4$ e poi da $10^(k-2)$ zeri nel caso il numero di partenza fosse un $7$ o seguito da un $8$ e poi da $10^(k-2)$ zeri nel caso il dispari di partenza fosse $9$ (ovviamente se il dispari si partenza era $5$, otteniamo solo $1*10^(k-1)$). Ne segue che il primo numero di $n/5$ è $1$, dispari, e va bene. La seconda cifra sarà invece $0+1=1$, $4+1=5$ ,$8+1=9$, se, nell'ordine, la prima cifra di $n$ era $5$, $7$, o $9$. e così via per le altre cifre, verificando quindi (non mi azzardo a definire questo sgorbio una dimostrazione
) che tutte le cifre di $n/5$ sono dispari, e precisamente sono $1$,$5$ o $9$. Sono dunque rispettate tutte le condizioni del problema, e quindi, ricapitolando, abbiamo, per $n$: una scelta per l'ultima cifra, e $3$ scelte (5,7,9) per le restanti $k-1$ cifre per un totale di $1*3^(k-1)=3^(k-1)$ possibili $n$. Ripeto, una dimostrazione decente la trovate qui http://www.matematicadivertente.com/sec ... lo2006.pdfP.s in tutto il post ho usato il termine "prima cifra" per indicare la cifra all'inizio della scrittura del numero, mentre per ultima cifra ho inteso proprio l'ultima, quella in fondo a destra, come il bagno.
ho trovato la tua dimostrazione eccellente!!!
comunque una piccola nota: una volta dimostrato che il termine noto nella scrittura del numero in base $10$ deve essere $5$, e che gli altri $k-1$ possono essere solo tre distinti, non potevi concludere direttamente dicendo che hai $3^(k-1)$ possibili numeri?? ripeto che per il resto la dimostrazione mi sembra molto chiara,pulita e precisa
comunque una piccola nota: una volta dimostrato che il termine noto nella scrittura del numero in base $10$ deve essere $5$, e che gli altri $k-1$ possono essere solo tre distinti, non potevi concludere direttamente dicendo che hai $3^(k-1)$ possibili numeri?? ripeto che per il resto la dimostrazione mi sembra molto chiara,pulita e precisa
rilancio con un altro problemaccio TdN (sempre dalle gare di febbraio) che io ho trovato abbastanza complicato:
dimostrare che ogni numero $n$ si puo scrivere come $n=a^2+b^2-c^2$ , con opportuni $a,b,c$ interi
dimostrare che ogni numero $n$ si puo scrivere come $n=a^2+b^2-c^2$ , con opportuni $a,b,c$ interi
"fedeb":
rilancio con un altro problemaccio TdN (sempre dalle gare di febbraio) che io ho trovato abbastanza complicato:
dimostrare che ogni numero $n$ si puo scrivere come $n=a^2+b^2-c^2$ , con opportuni $a,b,c$ interi
a,b e c devono essere necessariamente diversi tra loro?
$b^2-c^2$ se prendiamo c e b consecutivi otteniamo la successione dei numeri dispari
$1^2-0^2=1$
$2^2-1^2=3$
$3^2-2^2=5$ ecc
quindi $n^2-(n-1)^2=2n-1$
prendiamo a=0 per ottenere n dispari e a=1 per n pari
dove ho sbagliato?
$1^2-0^2=1$
$2^2-1^2=3$
$3^2-2^2=5$ ecc
quindi $n^2-(n-1)^2=2n-1$
prendiamo a=0 per ottenere n dispari e a=1 per n pari
dove ho sbagliato?
Secondo me non hai sbagliato, Simo 
Giusto per giocare un po', prendo spunto
dalla tua proposta e utilizzo il fatto che ogni
numero intero rientra in una delle seguenti
forme:
4n, 4n+1, 4n+2, 4n+3.
Posso allora scrivere:
4n = n² + 2² - (n-2)²
4n+1 = (n+1)² + 1² - (n-1)²
4n+2 = (2n+1)² + 1² - (2n)²
4n+3 = (2n)² + 2² - (2n-1)²
Ma si può anche trovare qualcos'altro.
Una risposta alternativa al quesito originario
di Gauss91 può essere data anche solo
guardando le ultime due cifre del numero
moderno 20062006...2006, cioè 06: nessun
quadrato terminante con 6 ha la penultima
cifra pari.
E' un esercizio facile ma carino spiegare
perché
Ciao a tutti!
Giusto per giocare un po', prendo spunto
dalla tua proposta e utilizzo il fatto che ogni
numero intero rientra in una delle seguenti
forme:
4n, 4n+1, 4n+2, 4n+3.
Posso allora scrivere:
4n = n² + 2² - (n-2)²
4n+1 = (n+1)² + 1² - (n-1)²
4n+2 = (2n+1)² + 1² - (2n)²
4n+3 = (2n)² + 2² - (2n-1)²
Ma si può anche trovare qualcos'altro.
Una risposta alternativa al quesito originario
di Gauss91 può essere data anche solo
guardando le ultime due cifre del numero
moderno 20062006...2006, cioè 06: nessun
quadrato terminante con 6 ha la penultima
cifra pari.
E' un esercizio facile ma carino spiegare
perché
Ciao a tutti!
"fedeb":
ho trovato la tua dimostrazione eccellente!!!
comunque una piccola nota: una volta dimostrato che il termine noto nella scrittura del numero in base $10$ deve essere $5$, e che gli altri $k-1$ possono essere solo tre distinti, non potevi concludere direttamente dicendo che hai $3^(k-1)$ possibili numeri?? ripeto che per il resto la dimostrazione mi sembra molto chiara,pulita e precisa
Beh, no. Vedere che l'ultimo numero è $5$, e che gli altri siano solo $5,7,9,$, non basta per assicurarti che questo numeraccio, una volta diviso per $5$, abbia ancora tutte le cifre dispari: devi farlo vedere. Inoltre la dimostrazione che vedi al link è ancora più dettagliata: in pratica il concetto di fondo è che trovare che i numeri sono $3^(k-1)$ è la parte "facile", mentre il difficile è dimostrare che sono "tutti e soli". Io ho provato a dare un'idea, semplicemente.
"Bruno":
Una risposta alternativa al quesito originario
di Gauss91 può essere data anche solo
guardando le ultime due cifre del numero
moderno 20062006...2006, cioè 06: nessun
quadrato terminante con 6 ha la penultima
cifra pari.
E' un esercizio facile ma carino spiegare
perché
Ciao a tutti!
Boh, dici che basta dire che, prendendo un generico numero di k cifre $n=a_(k-1)*10^(k-1)+...+a_2*10^2+a_1*10+a_0$, ed elevandolo al quadrato, otteniamo $k*(k+1)/2$ addendi, di cui solo uno, precisamente $a_0^2$, non termina con almeno uno zero? Di conseguenza tutti gli addendi, eccetto $a_0^2$ sono pari, quindi la loro somma sarà pari, e sarà inoltre un multiplo di $10$. L'unico addendo (oltre a $a_0^2$, che non è un multiplo di 10), a terminare con un solo $0$ è $2*a_1*10*a_0$, ed essendo nella forma $20*h$, con $hinZZ$, quindi multiplo di $20$, ha come cifra delle decine un numero pari. Ciò che farà la differenza sarà quindi il numero a due cifre $a_0^2$, che essendo a 2 cifre modificherà la cifra delle decine (pari, ricordiamolo)e delle unità. Ora, gli unici $a_0$, con $0<=a_0<=9$ e $a_0inNN$ tali che $a_0^2$ termini con $6$ si verifica facilmente che sono $4$ e $6$, e i loro quadrati infatti sono $16$ e $36$. Quindi, in entrambi i casi, alla cifra delle decine di $n$, che è pari, viene sommato un dispari ($1$ o $3$), ottenendo ovviamente un dispari,e così scriviamo il felice Q.E.D.
Ci sarà sicuramente un modo più bellino per fare questa dimostrazione, ma ora ho sonno.
Buonanotte...
Più sbrigativamente e tornando sui soliti passi: $sum_(k=2)^n 10^ka_k +10*2t + 6 = 2 (mod 4)$.
Titolo di coda: la striminzita riga di sopra mostra che non esistono quadrati che hanno una penultima cifra pari e poi un 6.
Titolo di coda: la striminzita riga di sopra mostra che non esistono quadrati che hanno una penultima cifra pari e poi un 6.
"Levacci":
Più sbrigativamente e tornando sui soliti passi: $sum_(k=2)^n 10^ka_k +10*2t + 6 = 2 (mod 4)$.
Titolo di coda: la striminzita riga di sopra mostra che non esistono quadrati che hanno una penultima cifra pari e poi un 6.
In realtà basta osservare che $20$ è divisibile per $4$, mentre $10 -= 2mod4$ dopo di che basta seguire le normali regole della somma di classi di resto.
Ma nel caso specifico bastava sapere che per la divisibilità per quattro è interamente determinata dalle ultime due cifre (come 8 dalle ultime 3) e osservare che i quadrati pari devono essere divisibili per 4.
P.S: in realtà 20 e 40 bastano ma per con le centinaia e le migliaia di riazzera.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo