Curiosità olimpiche 3 - La genesi di un problema

On March 5, 2017

Continua la rubrica Curiosità olimpiche, analizzando la genesi del problema presentato nella seconda puntata.

C'è un esercizio, problema o dimostrazione che secondo voi ha un qualcosa di unico? Segnalateceli!

3 - LA GENESI DI UN PROBLEMA

Dopo la pubblicazione della seconda puntata, ho parlato con Francesco Morandin, che mi ha svelato i retroscena della genesi del problema con risposta 42. Se non l'avete letta o se non avete ancora risolto l'esercizio proposto, fatelo prima di continuare a leggere. In questa puntata, svelando la genesi del problema, daremo un ulteriore aiuto per la risoluzione.

Come abbiamo già commentato, spesso nei dati dei problemi, siano esercizi delle gare individuali o delle gare a squadre, è l'anno corrente. Per farsi venire delle idee sui problemi, i collaboratori delle Olimpiadi spesso sviscerano a fondo le proprietà di tale numero.

L'anno corrente, all'epoca, era il 2009. La prima immediata osservazione è che

2009 = 7^2 \cdot 41\,.

Dalla scomposizione in fattori primi di un numero naturale n si possono ricavare moltissime informazioni, come quanti sono i suoi divisori o quanti sono i numeri naturali minori di n coprimi con n: tale valore viene indicato con \phi(n). La funzione \phi è detta funzione \phi di Eulero o funzione toziente.

Parte tecnica. Se non si vuole affrontarla si può saltare fino alla prossima scritta in rosso. Data la scomposizione in numeri primi di n

n = p_1^{\alpha_1}\cdot \cdots \cdot p_k^{\alpha_k}

si ha che

\phi(n) = \left((p_1-1)p_1^{\alpha_1-1}\right)\cdot \cdots \cdot \left((p_k-1)\cdot p_k^{\alpha_k-1}\right)\,.

Ciò può essere provato come mostrato qui oppure utilizzando il teorema cinese del resto e l'osservazione che se p è un numero primo allora i numeri non comprimi con p^\alpha sono tutti e soli i multipli di p, ovvero p^{\alpha-1} tra 1 e p^\alpha.

Riprendi da qui.  Pertanto

\phi(2009) = 6 \cdot 7 \cdot 40 = 42 \cdot 40\,.

Osservato che 42 divide esattamente \phi(2009), il problema era quasi nato. Con questo suggerimento, riuscite a risolvere l'esercizio?

Per arrivare al problema, mancava solo un'ultima osservazione, ovvero il fatto che

\phi(2009) = 6 \cdot 7 \cdot 40 = 42 \cdot 40 = 8 \cdot \frac{21\cdot 20}{2}

\phi(2009) è esattamente 8 volte un numero triangolare. I numeri triangolari sono collegati alle coppie di oggetti e il problema è servito!

Alberto Saracco

Leave a Reply

Your email address will not be published. Required fields are marked *

this site uses the awesome footnotes Plugin