AIME 1991

[Megathorybos]

Dalle American Invitational Mathematics Examination:

Dato un numero razionale, scrivetelo come una frazione ridotta ai minimi termini e calcolate il prodotto di numeratore e denominatore. Per quanti numeri razionali, compresi fra 0 e 1, 20! sarà la soluzione?

[GioacchinoA]

Il problema tradotto diventa:
Trovare tutte le coppie $ (x,y) $ di numeri naturali tali che $ (x,y)=1 $ e che risulti $ xy=20! $. consideriamo la coppia $ (x,y) $ uguale alla coppia $ (y,x) $ così da eliminare il problema del razionale compreso fra $ 0 $ e $ 1 $. Infatti fra $ x $ e $ y $ uno è maggiore e quindi una delle due frazioni $ \dfrac{x}{y} $,$ \dfrac{y}{x} $ sarà compresa fra $ 0 $ e $ 1 $.

Risolviamo il caso generale. Nelle stesse ipotesi trovare il numero di coppie $ (x,y) $ tali che si verifichi $ xy=k $.
Possiamo fattorizzare $ k=p_1^{a_1}p_2^{a_2}...p_n^{a_n} $. Ora i due numeri $ x $ e $ y $ si devono "distribuire i fattori" nel senso che uno stesso fattore $ p_i $ non può capitare sia in $ x $ e $ y $. Dunque se un numero si prende un fattore primo se lo prende con tutta la sua potenza. Inoltre se un numero si prende alcuni fattori, l'altro si prende tutti gli altri.
Dunque il problema è partizionare i fattori primi $ p_i $ fra i due numeri.

Quindi conto tutti i numeri con $ 0 $ fattori primi, $ 1 $ fattore primo....,$ n $ fattori primi. Questi sono $ {n \choose 0}+{n \choose 1} +...+ {n \choose n} = 2^n $. Così facendo però includo due volte la coppia $ (x,y) $. Dunque dividendo per due ottengo $ 2^{n-1} $ dove $ n $ è il numero di fattori primi di k.

Nel nostro caso $ k=20! $ e come fattori primi ha $ 2,3,5,7,11,13,17,19 $ per cui $ 20! $ sarà la soluzione per $ 2^7 $ numeri = $ 128 $ numeri.

Spero che tu abbia capito

[Megathorybos]

Esatto!

[exodd]

è uguale ad uno dei problemi delle gare a squadre, non mi ricordo di quale anno, ma mi ricordo che il tema era harry potter... infatti era un gioco a cui giocavano fred e george..