Un popolo di smemorati

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
mpxavi96
Messaggi: 72
Iscritto il: 19 feb 2012, 17:16

Un popolo di smemorati

Messaggio da mpxavi96 » 14 ago 2015, 20:27

Partiti da Treia, Ellisseo e i suoi compagni vengono spinti da una bufera nella terra dei Rotofagi, popolo di gente smemorata. Per tenere con precisione conto delle entrate giornaliere il re dei Rotofagi introduce su consiglio di Ellisseo un sistema a prova di amnesia. Vengono eletti 20 uomini, a ciascuno dei quali viene assegnato un ufficio. Ogni giorno all’impiegato del primo ufficio viene comunicato l’ammontare delle entrate giornaliere: egli deve annotare tale numero sul proprio registro. All’impiegato dell'ufficio k, per 2≤k≤20, viene poi richiesto di annotare ogni giorno sul proprio registro la somma di tutti i numeri annotati dall’impiegato dell’ufficio k−1 fino al giorno precedente (il primo giorno annotano tutti 0, non avendo alcun numero da sommare). Curiosamente, i numeri che vengono comunicati al primo impiegato sono proprio i quadrati perfetti: 1 il primo giorno, 4 il secondo giorno, 9 il terzo, e così via. L’impiegato del ventesimo ufficio, annoiato dal compito assegnatogli, cerca dapprima di fattorizzare 9973 scoprendo che è un primo, quindi si chiede in quale giorno, per la prima volta, scriverà un numero positivo multiplo di 9973. Qual è la risposta alla sua domanda?

Avatar utente
Lasker
Messaggi: 423
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Un popolo di smemorati

Messaggio da Lasker » 14 ago 2015, 22:52

Definiamo per ogni coppia ordinata $(n,k)\in \mathbb{N}^2$ l'ammontare $A_{n,k}$ annotato dall'impiegato del $k$-esimo ufficio durante l'$n$-esimo giorno di lavoro.
Chiaramente per le ipotesi del problema vale $A_{n,1}=n^2\ \ \forall \ n\in\mathbb{N}$, o meglio, $A_{n,1}=2{n\choose 2}+{n\choose 1}\ \ \forall \ n\in\mathbb{N}$ (vedremo presto perché conviene scriverlo in questa maniera). Chi è dunque $A_{n,2}$? Sfruttando la condizione sulle somme, si ottiene:
$$A_{n,2}=\sum_{i=0}^{n-1} A_{i,1}=\sum_{i=0}^{n-1} \left[2{i\choose 2}+{i\choose 1}\right]=2\sum_{i=0}^{n-1}{i\choose 2}+\sum_{i=0}^{n-1}{i \choose 1}=2{n\choose 3}+{n\choose 2}$$
Utilizzando una ben nota identità fra somme di binomiali (la regola della "mazza da hockey" :mrgreen: ) abbiamo ottenuto un'espressione molto simile ad $A_{n,1}$!
Continuando ora esattamente allo stesso modo con $A_{n,3}$ e avanti così (volendo si dimostra formalmente per induzione, ma in una GaS basta convincersene... il tutto si fa allo stesso modo shiftando di $1$ i "$k$" dei due binomiali, senza difficoltà ulteriori), si arriva ad $A_{n,20}=2{n\choose 21}+{n\choose 20}$. E adesso conti, sviluppando il binomiale, per vedere qual è il più piccolo $n$ che rende l'espressione multipla di $9973$
$$2\cdot\frac{n(n-1)(n-2)...(n-20)}{21!}+\frac{n(n-1)(n-2)...(n-19)}{20!}=\frac{n(n-1)(n-2)...(n-19)}{20!}\left[\frac{2(n-20)}{21}+1\right]$$
Visto che $9973$ è primo, il grosso fattore raccolto è per la prima volta multiplo di $9973$ solo quando $n=9973$. Le nostre speranze di trovare una risposta significativa risiedono dunque nell'altro pezzo, ed in particolare nel suo numeratore!
$$\textrm{fattore interessante}=\frac{2(n-20)}{21}+1=\frac{2n-40+21}{21}\Rightarrow 9973\mid 2n-19$$
Visto che cerchiamo la soluzione intera positiva $n$ più piccola, imponiamo che valga proprio $2n-19=9973$, equazione che risolta dà il valore $n=4996$.

Ovviamente l'anno scorso in gara questo non è voluto venire (forse anche per via dell'asterisco minaccioso :( ), peccato perché alla fine non è che ci volesse poi tanto...

PS: magari sarebbe carino raccogliere i link ai vari problemi delle vecchie finali delle GaS da qualche parte, come per i problemi dei test SNS, visto che non esistono vere e proprie soluzioni ufficiali (su internet trovo giusto i risultati numerici, e molti problemi non sono per nulla banali)
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

matpro98
Messaggi: 441
Iscritto il: 22 feb 2014, 18:42

Re: Un popolo di smemorati

Messaggio da matpro98 » 15 ago 2015, 18:02

Io avevo cominciato un lavoro del genere, scrivendo le soluzioni in LaTeX per le GaS, esattamente per il motivo che di ufficiali non se ne trovano

Rispondi