Determinare per quali interi positivi m, esiste un intero positivo n tale che:
$ \displaystyle \frac{\tau(n^2)}{\tau(n)}=m $
Dove $ \tau(x) $ e' il numero di divisori interi positivi di x (inclusi 1 e x).
IMO3 (1998), ma non vi lasciate intimorire!
IMO3 (1998), ma non vi lasciate intimorire!
"Sei la Barbara della situazione!" (Tap)
... ma neanche da sottovalutare, visto che in 4 ore e mezza non credo che l'avrei finito 
(sì, ho dormito poco stanotte)
Ciònonostante la soluzione non è complicata, anzi, si arriva quasi ad una formula esplicita per n.
Cominciamo: fattorizzando n come $ ~ n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} $, osserviamo che per trovare un divisore di n, basta che scegliamo gli esponenti di ciascun primo che divide n, in modo tale che siano nonnegativi e minore dell'esponente che divide n. In poche parole:
$ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $
e anche:
$ ~ \tau(n^2) = (2a_1+1)(2a_2+1)\cdots (2a_k+1) $
Osserviamo che in queste formule abbiamo tenuto solo gli esponenti, e dimenticato che primi c'erano sotto. Infatti questi non centrano una cippa. Anzi, visto che i primi sono infiniti, per ogni k-upla $ ~ (a_i) $ possiamo trovare un n per cui $ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $.
Quindi il problema diventa: trovare tutti gli interi positivi m che si possono scrivere come:
$ \displaystyle m = \frac{(2a_1-1)(2a_2-1)\cdots (2a_n-1)}{a_1a_2\cdots a_n} $
per opportuni interi positivi $ ~n, a_1,\ldots,a_n $. (sì, ho sostituito $ ~ a_i+1 $ con $ ~ a_i $, ed ora ho il sospetto che questo mi abbia in fondo aggiunto difficoltà al problema, ma non posso più farne a meno).
Chiaramente il numeratore è dispari. Quindi gli $ ~ a_i $ sono tutti dispari, e anche m, proprio lui, è dispari. Il claim è: tutti gli m dispari si scrivono in questo modo.
Cominciamo con un lemmino. Detta $ ~ f(x) = 2x-1 $, allora $ ~ f^n(x) = 2^n(x-1) + 1 $, e detta $ ~ f^{-1}(x) = \frac{x+1}2 $, si ha $ ~ f^{-n}(x) = \frac{x-1}{2^n} + 1 $.
Diomostrazione: una volta azzeccate le formule giuste, l'induzione deve funzionare.
Ora siamo pronti per scrivere ogni m dispari. Il passo "furbo" è scrivere $ ~ m = 2^kd - 1 $, con d dispari. Ora, posto $ ~ r = d(2^k-1) $, calcoliamo quanto fa la frazione legale:
$ \displaystyle \frac{f(r)}{r} \cdot \frac{f^2(r)}{f(r)} \cdots \frac{f^k(r)}{f^{k-1}(r)} $.
Si semplifica di nuovo tutto, e basta calcolare $ ~ \frac{f^k(r)}{r} $, cioè, sviluppando r ed usando la formula, $ ~ \frac{2^k(2^kd - d -1) + 1}{d(2^k-1)} = \frac{2^kd(2^k-1) - (2^k-1)}{d(2^k-1)} $$ \displaystyle = \frac{2^kd-1}{d} = \frac{m}{d} $.
Quindi, per riuscire a fare $ ~ m = 2^kd-1 $ mi basta fare d. Ma anche d è dispari, e ovviamente $ ~ d < 2^kd -1 $, quindi il problema è risolto grazie all'induzione
(commento: questa soluzione era moltissimo "calata dall'alto", come ci sono arrivato è una storia molto lunga
)
(sì, ho dormito poco stanotte)Ciònonostante la soluzione non è complicata, anzi, si arriva quasi ad una formula esplicita per n.
Cominciamo: fattorizzando n come $ ~ n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} $, osserviamo che per trovare un divisore di n, basta che scegliamo gli esponenti di ciascun primo che divide n, in modo tale che siano nonnegativi e minore dell'esponente che divide n. In poche parole:
$ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $
e anche:
$ ~ \tau(n^2) = (2a_1+1)(2a_2+1)\cdots (2a_k+1) $
Osserviamo che in queste formule abbiamo tenuto solo gli esponenti, e dimenticato che primi c'erano sotto. Infatti questi non centrano una cippa. Anzi, visto che i primi sono infiniti, per ogni k-upla $ ~ (a_i) $ possiamo trovare un n per cui $ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $.
Quindi il problema diventa: trovare tutti gli interi positivi m che si possono scrivere come:
$ \displaystyle m = \frac{(2a_1-1)(2a_2-1)\cdots (2a_n-1)}{a_1a_2\cdots a_n} $
per opportuni interi positivi $ ~n, a_1,\ldots,a_n $. (sì, ho sostituito $ ~ a_i+1 $ con $ ~ a_i $, ed ora ho il sospetto che questo mi abbia in fondo aggiunto difficoltà al problema, ma non posso più farne a meno).
Chiaramente il numeratore è dispari. Quindi gli $ ~ a_i $ sono tutti dispari, e anche m, proprio lui, è dispari. Il claim è: tutti gli m dispari si scrivono in questo modo.
Cominciamo con un lemmino. Detta $ ~ f(x) = 2x-1 $, allora $ ~ f^n(x) = 2^n(x-1) + 1 $, e detta $ ~ f^{-1}(x) = \frac{x+1}2 $, si ha $ ~ f^{-n}(x) = \frac{x-1}{2^n} + 1 $.
Diomostrazione: una volta azzeccate le formule giuste, l'induzione deve funzionare.
Ora siamo pronti per scrivere ogni m dispari. Il passo "furbo" è scrivere $ ~ m = 2^kd - 1 $, con d dispari. Ora, posto $ ~ r = d(2^k-1) $, calcoliamo quanto fa la frazione legale:
$ \displaystyle \frac{f(r)}{r} \cdot \frac{f^2(r)}{f(r)} \cdots \frac{f^k(r)}{f^{k-1}(r)} $.
Si semplifica di nuovo tutto, e basta calcolare $ ~ \frac{f^k(r)}{r} $, cioè, sviluppando r ed usando la formula, $ ~ \frac{2^k(2^kd - d -1) + 1}{d(2^k-1)} = \frac{2^kd(2^k-1) - (2^k-1)}{d(2^k-1)} $$ \displaystyle = \frac{2^kd-1}{d} = \frac{m}{d} $.
Quindi, per riuscire a fare $ ~ m = 2^kd-1 $ mi basta fare d. Ma anche d è dispari, e ovviamente $ ~ d < 2^kd -1 $, quindi il problema è risolto grazie all'induzione
(commento: questa soluzione era moltissimo "calata dall'alto", come ci sono arrivato è una storia molto lunga
)Toh, la mia stessa soluzione, non fosse che io, per amore dell'inutile, anziche' mandare gli a_i+1 in a_i, ho distinto il caso m=4k+1 e m=4k-1...
Solo c'e' un errore nella dimostrazione, hai dimenticato di dimostrare che:
$ \displaystyle \frac{\tau(n^2)}{\tau(n)}=1 $ e' risolvibile...
Comunque era bellino dai...
(magari se so che ti faccio passare le notti insonni la prossima volta li posto in tarda mattinata..)
Solo c'e' un errore nella dimostrazione, hai dimenticato di dimostrare che:
$ \displaystyle \frac{\tau(n^2)}{\tau(n)}=1 $ e' risolvibile...
Comunque era bellino dai...
(magari se so che ti faccio passare le notti insonni la prossima volta li posto in tarda mattinata..)
"Sei la Barbara della situazione!" (Tap)
No beh, una volta capito che l'insieme era "moltiplicativo", io mi son messo a cercare solo i primi
I primi 4k+1 ok, tranquillissimi, i primi 4k+3, megabastardi
Dopo un sacco di tempo ho trovato una strategia per fare i primi 8k+3, ma, benedetto sia Dirichlet, restavano gli 8k+7
Una volta fatti i 16k+7 mi ci stavo avvicinando, ma quando hai fatto 31, lì sì che hai concluso!! (chi lo moltiplicherebbe mai di nuovo per 31?)
Sìsì, carino comunque
edit: corollario: per ogni intero positivo dispari m, esiste un intero k tale che $ ~ m = (\mbox{quasi }2)^k $
I primi 4k+1 ok, tranquillissimi, i primi 4k+3, megabastardi
Dopo un sacco di tempo ho trovato una strategia per fare i primi 8k+3, ma, benedetto sia Dirichlet, restavano gli 8k+7
Una volta fatti i 16k+7 mi ci stavo avvicinando, ma quando hai fatto 31, lì sì che hai concluso!! (chi lo moltiplicherebbe mai di nuovo per 31?)
Sìsì, carino comunque
edit: corollario: per ogni intero positivo dispari m, esiste un intero k tale che $ ~ m = (\mbox{quasi }2)^k $
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara