Riduzioni sulla lavagna

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Riduzioni sulla lavagna

Messaggio da Gottinger95 » 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 :)
Ultima modifica di Gottinger95 il 18 set 2014, 19:46, modificato 1 volta in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Avatar utente
Tess
Messaggi: 256
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Riduzioni sulla lavagna

Messaggio da Tess » 18 set 2014, 17:35

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
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Riduzioni sulla lavagna

Messaggio da ma_go » 18 set 2014, 19:42

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.

Avatar utente
Tess
Messaggi: 256
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Riduzioni sulla lavagna

Messaggio da Tess » 20 set 2014, 11:33

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$?

Rispondi