Riduzioni sulla lavagna
Inviato: 17 set 2014, 14:07
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
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