Un popolo di smemorati

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Lasker
Messaggi: 439
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: 459
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