Riduzioni sulla lavagna

[Gottinger95]

Fissiamo un intero \(n \ge 2\). Sulla lavagna ci sono scritti gli elementi di un certo insieme finito \(A\) di naturali.
Possiamo fare solo una mossa: se troviamo un sottoinsieme \(S\) tale che la somma dei suoi elementi è divisibile per \(n\), allora possiamo cancellare un elemento a nostro piacimento del sottoinsieme \(S\). Ridurre \(A\) significa fare in modo, con una certa sequenza di mosse, che non si possa più applicare la mossa.
Chiamiamo grado di riduzione di \(A\) rispetto a \(n\) il minimo intero \(d\) tale che esiste una sequenza di \(d\) mosse che riduce \(A\).

C'è un modo per trovare il grado di riduzione in funzione di \(A, n\)?

P.S. Io la soluzione non la so eh!

EDIT: grazie a Tess! Ho aggiunto il rosso

[Tess]

Come l'hai formulata tu, la domanda non è molto interessante, dato che ci sono solo un numero finito di mosse applicabili ad ogni passaggio e il numero di passaggi è finito (spero almeno che $A$ sia finito...). Quindi dato $A$ e $n$ c'è per forza la sequenza di mosse massimale più corta, e il modo per trovarla è semplicemente elencare tutte le sequenze di mosse, ordinarle per lunghezza e prendere quella minima.

Quindi direi che la domanda non è esattamente questa.

[ma_go]

e invece secondo me la domanda è interessante, anche se troppo generale.
io mi restringerei ad insiemi "sensati": ad esempio, si riescono a stimare $d$ quando $A = \{1,\dots,N\}$ (per qualche $N$ intero)? quando $N = 2n$? $N=n^2$? quando $A = \{1,2,4,\dots,2^N\}$ per qualche $N$?
in ogni caso, penso che anche i problemi semplificati siano parecchio difficili.

[Tess]

Quel che volevo dire era solo che porre una domanda come "in un insieme finito, c'è un minimo?" non era molto interessante.
Devo ammettere invece che dati alcuni valori particolari per $A$ potrebbe diventare un problema interessante, diciamo, una volta che la domanda diventa "determinare (o stimare) il grado di riduzione di questo $A$ in funzione di $n$".

A saper fare le domande giuste si cambia l'aspetto delle cose!

Ormai che ci siamo, propongo un'altra sottovariante del problema (che forse è anche un hint per quelle che dicevi tu): fissato $n$ e $|A|$, al variare di $A$ determinare il minimo grado di riduzione. Domanda che può anche essere espressa come: dato un insieme e un $n$, quante mosse devo aspettarmi di dover fare sempre prima di aver ridotto $A$?