Riduzione di insiemi

Problemi enumerativi, teoria dei grafi ...

Moderatore: Moderatori

Riduzione di insiemi

Messaggioda Gottinger95 il mer 17 set 2014, 13:09

Fissiamo un intero \(n \ge 2\). Sulla lavagna ci sono scritti gli elementi di un certo insieme \(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\)?
Gottinger95
 
Messaggi: 16
Iscritto il: lun 12 mag 2014, 21:32

Torna a Combinatoria

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti

cron