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"
) 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)