Mattoncini
Ripropongo un vecchio problema che avevo proposto quasi un anno fa. Vediamo se c’è qualcuno con qualche idea…
Immaginiamo di costruire una colonna con dei mattoncini lego. Vogliamo costruirla in modo che non ci siano mai ripetizioni di colore, nemmeno parziali, e di avere mattoncini sono di tre colori. Quanto sarà alta al massimo la nostra colonna?
Faccio alcuni esempi per spiegare il quesito:
-avendo solo mattoncini rossi
il primo è ovviamente rosso, ma non posso mettere il secondo poiché avrei una ripetizione: R R. Quindi la soluzione in questo caso è 1
-avendo mattoncini rossi e gialli
il primo R e il secondo obbligatoriamente G: R-G a questo punto posso metere solo il rosso (altrimenti avrei R-G-G, con ripetizione G G) quindi ottengo R-G-R, e qui mi fermo, infatti se mettessi R avrei ripetizione R R se mettessi G avrei ripetizione R-G R-G. Quindi la soluzione in questo caso è 3
-la soluzione per tre colori è più elevata (io non la so), posso però dire che la più bassa colonna è di 6 mattoncini e poi avrei sempre ripetizioni. Avendo mattoncini rossi, gialli e verdi ottengo:
R-G-R-V-R-G-R
Un altro R implica R R, un altro G implica R-G R-G, e un altro V implica R-G-R-V R-G-R-V. Quasta è la più corta cioè la più bassa ma quale è la più alta?
WonderP.
Immaginiamo di costruire una colonna con dei mattoncini lego. Vogliamo costruirla in modo che non ci siano mai ripetizioni di colore, nemmeno parziali, e di avere mattoncini sono di tre colori. Quanto sarà alta al massimo la nostra colonna?
Faccio alcuni esempi per spiegare il quesito:
-avendo solo mattoncini rossi
il primo è ovviamente rosso, ma non posso mettere il secondo poiché avrei una ripetizione: R R. Quindi la soluzione in questo caso è 1
-avendo mattoncini rossi e gialli
il primo R e il secondo obbligatoriamente G: R-G a questo punto posso metere solo il rosso (altrimenti avrei R-G-G, con ripetizione G G) quindi ottengo R-G-R, e qui mi fermo, infatti se mettessi R avrei ripetizione R R se mettessi G avrei ripetizione R-G R-G. Quindi la soluzione in questo caso è 3
-la soluzione per tre colori è più elevata (io non la so), posso però dire che la più bassa colonna è di 6 mattoncini e poi avrei sempre ripetizioni. Avendo mattoncini rossi, gialli e verdi ottengo:
R-G-R-V-R-G-R
Un altro R implica R R, un altro G implica R-G R-G, e un altro V implica R-G-R-V R-G-R-V. Quasta è la più corta cioè la più bassa ma quale è la più alta?
WonderP.
Risposte
Scusa WonderP vediamo se ho capito come funziona: posso fare una colonna R-G-R-V-R-G-V-R?
Ciao, Ermanno.
Ciao, Ermanno.
sapevo che l'avresti postato prima o poi. ci ho pensato un po' su. non avendo algoritmi ho provato a vedere che succede con tutti i tentativi. avevo notato anche io (con dispiacere) che c'è una sequenza minima pari a 7 che non permette di andare avanti (lì per lì mentre mi costruivo il mio albero speravo si potesse dimostrare per induzione che era sempre possibile creare una sequenza di lunghezza n+1 da una di lunghezza n) poi vedendo come si espandevano all'inizio i rami mi sembrava di aver trovato una relazione coi numeri di fibonacci (ma anche lì mi sono fermato quando ho trovato un 11 al posto del 13).
più che altro, siamo sicuri che non si possa costruire una sequenza infinita?
più che altro, siamo sicuri che non si possa costruire una sequenza infinita?
non ho collaudato il metodo, però ho pensato a questo:
invece di partire da un mattoncino e metterci di seguito tutti gli altri, partiamo da un mattoncino e aggiungiamo mattoncini contemporaneamente a sinistra e a destra;il modo in cui aggiungiamo mattoncini è il seguente:
supponiamo di iniziare da R, aggiungiamo in questo modo una prima sequenza V-G-R
(R-G-V)-R-(V-G-R)
ho messo fra parentesi la stringa V-G-R...
possiamo continuare in questo modo, aggiungendo sempre stringhe da tre, in tutte le possibili combinazioni(cioè sei combinazioni in tutto)...io non l' ho ancora fatto, ma potreste verificare se la stringa ottenuta è corretta?
invece di partire da un mattoncino e metterci di seguito tutti gli altri, partiamo da un mattoncino e aggiungiamo mattoncini contemporaneamente a sinistra e a destra;il modo in cui aggiungiamo mattoncini è il seguente:
supponiamo di iniziare da R, aggiungiamo in questo modo una prima sequenza V-G-R
(R-G-V)-R-(V-G-R)
ho messo fra parentesi la stringa V-G-R...
possiamo continuare in questo modo, aggiungendo sempre stringhe da tre, in tutte le possibili combinazioni(cioè sei combinazioni in tutto)...io non l' ho ancora fatto, ma potreste verificare se la stringa ottenuta è corretta?
per leonardo, sì va bene... dopo R-G-R-V-R-G-V-R puoi solo aggiungere V, poiché se aggiungi G ottieni la ripetizione V-R-G. R ovviamente non si po'.
Maverick... non sono per nulla sicuro cha la sequenza non sia infinita, ma mi sembrerebbe strano se lo fosse e non sabrei da che parte iniziare a dimostrarlo.
jack, non ci avevo mai pensato, ma non si rischia di escludere alcune possibilità? Comunque la stringa scritta da te è corretta. Affermi però che ci sono sei blocchi... perché usarli solo una volta? Rischio di avere un problema invece che con 3 variabili, con 6. Inoltre perché blocchi da 3? e non da 2, cioè da n-1 elementi? C'è da ragionarci sopra...
WonderP.
Maverick... non sono per nulla sicuro cha la sequenza non sia infinita, ma mi sembrerebbe strano se lo fosse e non sabrei da che parte iniziare a dimostrarlo.
jack, non ci avevo mai pensato, ma non si rischia di escludere alcune possibilità? Comunque la stringa scritta da te è corretta. Affermi però che ci sono sei blocchi... perché usarli solo una volta? Rischio di avere un problema invece che con 3 variabili, con 6. Inoltre perché blocchi da 3? e non da 2, cioè da n-1 elementi? C'è da ragionarci sopra...
WonderP.
Per ora questi sono i risultati del mio primo tentativo:
La procedura che volevo utilizzare è questa.
Chiamo f(n,k) il numero di stringhe di lunghezza n che possiedono questa proprietà: presa una qualsiasi sottostringa di elementi consecutivi di lunghezza m con 0
Analizzando ora f(n,k) forse si giunge a qualcosa. Per ora:
---- f(n,1)=3 * 2^(n-1)------
La tesi equivale a dire che nn esistono numeri consecutivi uguali nella stringa.
Immaginiamo di possedere f(n-1,1). Cioè una stringa di lunghezza (n-1) che rispetta le condizioni. Si può aggiungere in fondo un termine in fondo in 2 modi. Quindi
f(n,1) = f(n-1,1) * 2. Dato che f(1,1)=3 per induzione si mostra che f(n,1)=3*2^(n-1).
---- f(n,2)=Fib(n) * 6 ----per n>=3
Immaginiamo di avere una stringa di lunghezza n che rispetti le condizioni. Distinguiamo 2 casi, indicando con s(n) l’elemento di ordine n della stringa.
[1] se s(n) = s(n-2); s(n+1) può essere scelto solo in un modo, dovendo essere diverso sia da s(n-1) che da s(n);
[2] se s(n) <> s(n-2); s(n+1) può essere scelto in 2 modi;
Questo ci serve per passare da f(n-1,2) a f(n,2). Incominciamo però già a pensare a f(n+1,2) osservando che dividendo ancora i casi come prima:
[1] in questo caso sarà s(n+1)<>s(n-1), cioè andando avanti si troverebbe il 2° caso;
[2] qui sarà nella metà dei casi s(n+1)<>s(n-1) e nell’altra s(n+1)=s(n-1), a seconda di quale dei due elementi si scelga;
Quindi, osservo che f(3,2)=12, con 6 elementi nel primo caso e due nel secondo.
Chiamo X_n e Y_n le stringhe di n elementi che rispettando le condizioni rispettivamente con il primo e e con il secondo caso (per esempio X_3=Y_3=6). Per quanto detto prima (pongo per esempio i casi piccoli):
f(4,2)=2*Y_3 + X_3------------------X_4=Y_3=6------Y_4=X_3+Y_3 = 2*6
f(5,2)=2 * Y_4 + X_4 =3 * Y_3+2*X_3------------X_5=Y_4=X_3+Y_3 =2*6------Y_5=X_4+Y_4=X_3+2*Y_3 = 3*6
la formula ricorsiva rispettata è data dal sistema (sempre per le osservazioni di prima)
X_3=Y_3 = 6 e per n>=3 :
X_(n+1)=Y_n
Y_(n+1)=X_n+Y_n
Ricavando dalla prima X_n=Y_(n-1) si vede che la serie Y_n rispetta quella dei numeri di fibonacci, traslata in questo modo (il tutto deriva da come sono fatti i termini iniziali):
Y_n=Fib(n-1)*6
Inoltre X(n)=Y_(n-1)=Fib(n-2)*6
Ma è f(n+1,2)=2*Y_n+X_n=6*[2*Fib(n-1)+Fib(n-2)] = 6* Fib(n+1), da cui la formula sopra, che si può esplicitare con la formula di Binet…
----------------------------------------------------
p.s.: Fib(n) è definito qua come Fib(0)=0---Fib(1)=1
<> vuol dire ‘diverso da’
Ora delle osservazioni:
1) NON HO CONTROLLATO CON RISULTATI NUMERICI LE CONSIDERAZIONI FATTE SOPRA;
2) l’approccio sembra destinato all’insuccesso. I metodi ed i risultati per k piccoli sembrano molto diversi: generalizzare pare problematico;
3) lascio a voi altre considerazioni
…saluti!
La procedura che volevo utilizzare è questa.
Chiamo f(n,k) il numero di stringhe di lunghezza n che possiedono questa proprietà: presa una qualsiasi sottostringa di elementi consecutivi di lunghezza m con 0
Analizzando ora f(n,k) forse si giunge a qualcosa. Per ora:
---- f(n,1)=3 * 2^(n-1)------
La tesi equivale a dire che nn esistono numeri consecutivi uguali nella stringa.
Immaginiamo di possedere f(n-1,1). Cioè una stringa di lunghezza (n-1) che rispetta le condizioni. Si può aggiungere in fondo un termine in fondo in 2 modi. Quindi
f(n,1) = f(n-1,1) * 2. Dato che f(1,1)=3 per induzione si mostra che f(n,1)=3*2^(n-1).
---- f(n,2)=Fib(n) * 6 ----per n>=3
Immaginiamo di avere una stringa di lunghezza n che rispetti le condizioni. Distinguiamo 2 casi, indicando con s(n) l’elemento di ordine n della stringa.
[1] se s(n) = s(n-2); s(n+1) può essere scelto solo in un modo, dovendo essere diverso sia da s(n-1) che da s(n);
[2] se s(n) <> s(n-2); s(n+1) può essere scelto in 2 modi;
Questo ci serve per passare da f(n-1,2) a f(n,2). Incominciamo però già a pensare a f(n+1,2) osservando che dividendo ancora i casi come prima:
[1] in questo caso sarà s(n+1)<>s(n-1), cioè andando avanti si troverebbe il 2° caso;
[2] qui sarà nella metà dei casi s(n+1)<>s(n-1) e nell’altra s(n+1)=s(n-1), a seconda di quale dei due elementi si scelga;
Quindi, osservo che f(3,2)=12, con 6 elementi nel primo caso e due nel secondo.
Chiamo X_n e Y_n le stringhe di n elementi che rispettando le condizioni rispettivamente con il primo e e con il secondo caso (per esempio X_3=Y_3=6). Per quanto detto prima (pongo per esempio i casi piccoli):
f(4,2)=2*Y_3 + X_3------------------X_4=Y_3=6------Y_4=X_3+Y_3 = 2*6
f(5,2)=2 * Y_4 + X_4 =3 * Y_3+2*X_3------------X_5=Y_4=X_3+Y_3 =2*6------Y_5=X_4+Y_4=X_3+2*Y_3 = 3*6
la formula ricorsiva rispettata è data dal sistema (sempre per le osservazioni di prima)
X_3=Y_3 = 6 e per n>=3 :
X_(n+1)=Y_n
Y_(n+1)=X_n+Y_n
Ricavando dalla prima X_n=Y_(n-1) si vede che la serie Y_n rispetta quella dei numeri di fibonacci, traslata in questo modo (il tutto deriva da come sono fatti i termini iniziali):
Y_n=Fib(n-1)*6
Inoltre X(n)=Y_(n-1)=Fib(n-2)*6
Ma è f(n+1,2)=2*Y_n+X_n=6*[2*Fib(n-1)+Fib(n-2)] = 6* Fib(n+1), da cui la formula sopra, che si può esplicitare con la formula di Binet…
----------------------------------------------------
p.s.: Fib(n) è definito qua come Fib(0)=0---Fib(1)=1
<> vuol dire ‘diverso da’
Ora delle osservazioni:
1) NON HO CONTROLLATO CON RISULTATI NUMERICI LE CONSIDERAZIONI FATTE SOPRA;
2) l’approccio sembra destinato all’insuccesso. I metodi ed i risultati per k piccoli sembrano molto diversi: generalizzare pare problematico;
3) lascio a voi altre considerazioni
…saluti!
Leggo ora bene il tuo primo post, Wonderp...
La più bassa mi pare che sia alta un mattoncino, no?
Forse vuoi dire la più bassa combinazione tale che nn si possano aggiungere + mattoncini?
Cmq i due problemi riguardo al max sono equivalenti: trovare la colonna max tale che rispetti le condizioni equivale a trovare la colonna max che rispetti le condizioni e tale che nn si possa aggiungere un mattoncino in più...
La più bassa mi pare che sia alta un mattoncino, no?
Forse vuoi dire la più bassa combinazione tale che nn si possano aggiungere + mattoncini?
Cmq i due problemi riguardo al max sono equivalenti: trovare la colonna max tale che rispetti le condizioni equivale a trovare la colonna max che rispetti le condizioni e tale che nn si possa aggiungere un mattoncino in più...
Faccio un po' fatica a seguirti, ma vediamo di capirci un passo alla volta:
k, che cosa è? infatti non riesco a "vedere" perché f(1,1)=3
WonderP.
k, che cosa è? infatti non riesco a "vedere" perché f(1,1)=3
WonderP.
Bene!
Ho affrontato il problema da un punto di vista più... semplicistico (ch'è la mia filosofia di vita).
Dopo aver osservato i tuoi esempi, WonderP, letto dei dubbi di Maverick e perso i sensi davanti alla dimostrazione di Thomas, ho iniziato a giocare col Lego e ne ho dedotto che bisogna ragionare con un semplice, appunto, calcolo di combinazioni di coppie dei colori interessati alla costruzione della colonna. Una volta trovate le coppie di colori, le si mette in fila e poi si aggiunge un ultimo mattoncino di colore identico al primo della serie.
Matematicamente parlando abbiamo: (nc*(nc-1)/2)*2+1 ==> (nc*(nc-1))+1 ==> dove nc è il numero di colori utilizzati...
... e praticamente abbiamo:
--------------------------------------------------------------------
numero colori:............ 1 (R)
combinazioni:............. 0
numero mattoncini:........ 1
risultato:................ R
--------------------------------------------------------------------
numero colori:............ 2 (RG)
combinazioni:............. 1 (RG)
numero mattoncini:........ 3
risultato:................ R-G-R
--------------------------------------------------------------------
numero colori:............ 3 (RGV)
combinazioni:............. 3 (RG-RV-GV)
numero mattoncini:........ 7
risultato:................ R-G-R-V-G-V-R
--------------------------------------------------------------------
numero colori:............ 4 (RGVB)
combinazioni:............. 6 (RG-RV-RB-GV-GB-VB)
numero mattoncini:........ 13
risultato:................ R-G-R-V-R-B-G-V-G-B-V-B-R
--------------------------------------------------------------------
numero colori:............ 5 (RGVBM)
combinazioni:............. 10 (RG-RV-RB-RM-GV-GB-GM-VB-VM-BM)
numero mattoncini:........ 21
risultato:................ R-G-R-V-R-B-R-M-G-V-G-B-G-M-V-B-V-M-B-M-R
---------------------------------------------------------------------
numero colori:............ 7 (RGVBMIN)
combinazioni:............. 21 (RG-RV-RB-RM-RI-RN-GV-GB-GM-GI-GN-VB-VM-VI-VN-BM-BI-BN-MI-MN-IN)
numero mattoncini:........ 43
risultato:................ R-G-R-V-R-B-R-M-R-I-R-N-G-V-G-B-G-M-G-I-G-N-V-B-V-M-V-I-V-N-B-M-B-I-B-N-M-I-M-N-I-N-R
------------------------------------------------------------------------------------------------------------------
Ecc... ecc... ecc...
Va da sé che non genera ripetizioni, mentre non sono altrettanto certo che sia LA soluzione...
Attendo riscontri! ^_^
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
Ho affrontato il problema da un punto di vista più... semplicistico (ch'è la mia filosofia di vita).
Dopo aver osservato i tuoi esempi, WonderP, letto dei dubbi di Maverick e perso i sensi davanti alla dimostrazione di Thomas, ho iniziato a giocare col Lego e ne ho dedotto che bisogna ragionare con un semplice, appunto, calcolo di combinazioni di coppie dei colori interessati alla costruzione della colonna. Una volta trovate le coppie di colori, le si mette in fila e poi si aggiunge un ultimo mattoncino di colore identico al primo della serie.
Matematicamente parlando abbiamo: (nc*(nc-1)/2)*2+1 ==> (nc*(nc-1))+1 ==> dove nc è il numero di colori utilizzati...
... e praticamente abbiamo:
--------------------------------------------------------------------
numero colori:............ 1 (R)
combinazioni:............. 0
numero mattoncini:........ 1
risultato:................ R
--------------------------------------------------------------------
numero colori:............ 2 (RG)
combinazioni:............. 1 (RG)
numero mattoncini:........ 3
risultato:................ R-G-R
--------------------------------------------------------------------
numero colori:............ 3 (RGV)
combinazioni:............. 3 (RG-RV-GV)
numero mattoncini:........ 7
risultato:................ R-G-R-V-G-V-R
--------------------------------------------------------------------
numero colori:............ 4 (RGVB)
combinazioni:............. 6 (RG-RV-RB-GV-GB-VB)
numero mattoncini:........ 13
risultato:................ R-G-R-V-R-B-G-V-G-B-V-B-R
--------------------------------------------------------------------
numero colori:............ 5 (RGVBM)
combinazioni:............. 10 (RG-RV-RB-RM-GV-GB-GM-VB-VM-BM)
numero mattoncini:........ 21
risultato:................ R-G-R-V-R-B-R-M-G-V-G-B-G-M-V-B-V-M-B-M-R
---------------------------------------------------------------------
numero colori:............ 7 (RGVBMIN)
combinazioni:............. 21 (RG-RV-RB-RM-RI-RN-GV-GB-GM-GI-GN-VB-VM-VI-VN-BM-BI-BN-MI-MN-IN)
numero mattoncini:........ 43
risultato:................ R-G-R-V-R-B-R-M-R-I-R-N-G-V-G-B-G-M-G-I-G-N-V-B-V-M-V-I-V-N-B-M-B-I-B-N-M-I-M-N-I-N-R
------------------------------------------------------------------------------------------------------------------
Ecc... ecc... ecc...
Va da sé che non genera ripetizioni, mentre non sono altrettanto certo che sia LA soluzione...
Attendo riscontri! ^_^
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
V-R-V-G-R-G-V-R-V
se non sbaglio soddisfa le nostre condizioni ed è più lunga di sette lettere...non sto dicendo che è la più lunga ottenibile, ma solo che l' ipotesi di spirale euclidea non mi spiega la mia stringa...
io non ho ancora avuto il lampo di genio per trovare la soluzione, ma non so perchè, mi sa che dietro c'è del calcolo combinatorio...
ciao
se non sbaglio soddisfa le nostre condizioni ed è più lunga di sette lettere...non sto dicendo che è la più lunga ottenibile, ma solo che l' ipotesi di spirale euclidea non mi spiega la mia stringa...
io non ho ancora avuto il lampo di genio per trovare la soluzione, ma non so perchè, mi sa che dietro c'è del calcolo combinatorio...
ciao
Mi pare che ci siano un paio di ripetizioni, però....
1) (V-R)-V-G-R-G-(V-R)-V
2) V-(R-V)-G-R-G-V-(R-V)
Oppure ho capito male il problema?
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
1) (V-R)-V-G-R-G-(V-R)-V
2) V-(R-V)-G-R-G-V-(R-V)
Oppure ho capito male il problema?
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
Sì, forse ho frainteso il problema.
Ma prima di continuare, mi dite se è corretta questa?
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V
Se non lo è, perché?
Così mi chiarisco le idee.
nel frattempo, vi auguro un buon fine anno e, naturalmente, uno strepitoso inizio anno! ^_^
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
Ma prima di continuare, mi dite se è corretta questa?
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V
Se non lo è, perché?
Così mi chiarisco le idee.
nel frattempo, vi auguro un buon fine anno e, naturalmente, uno strepitoso inizio anno! ^_^
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
@ spirale euclidea: quando sono off-line leggo la tua sol (ora nn posso restare molto)...cmq dubito che 7 sia il max per 3 colori. Se lo è, nn vedo la dimostrazione...(anzi, ora vedo una stringa di 8 lettere di jack, ma nn ho controllato). Cmq, a quanto ho capito, le ripetizioni devono essere perlomeno consecutive...
@Wonderp: ho definito la f(n,k) in questo modo:
prendi una stringa di lunghezza n: se nn ci sono ripetizioni di lunghezza 1, allora è buona per k=1. Se nn ci sono ripetizioni di lunghezza 1 e nn ci sono ripetizioni di lunghezza 2, allora è buona anche per k=2. Se nn ci sono ripetizioni di lunghezza 1 e nn ci sono ripetizioni di lunghezza 2 e nn ci sono ripetizioni di lunghezza 3, allora è buona anche per k=3...La funzione conta queste stringhe 'buone' di lunghezza precisamente n....
In sostanza pensavo di trovare qualcosa dallo studio di questa funzione, che conta le funzioni che soddisfano parzialmente le ipotesi (considerando le ripetizioni fino ad una certa lunghezza, insomma)..
Così f(1,m)=3 perchè esistono solo 3 tipi di colonne di un mattoncino, una per ogni colore, e perchè nn possono esistere mai ripetizioni di nessuna lunghezza in una simile colonna.
@tutti: nn è che qualcuno ha trovato con PC o a mano una stringa abbastanza alta: ad impressione io la penso come Maverick: direi che il limite max è infinito!
@Wonderp: ho definito la f(n,k) in questo modo:
prendi una stringa di lunghezza n: se nn ci sono ripetizioni di lunghezza 1, allora è buona per k=1. Se nn ci sono ripetizioni di lunghezza 1 e nn ci sono ripetizioni di lunghezza 2, allora è buona anche per k=2. Se nn ci sono ripetizioni di lunghezza 1 e nn ci sono ripetizioni di lunghezza 2 e nn ci sono ripetizioni di lunghezza 3, allora è buona anche per k=3...La funzione conta queste stringhe 'buone' di lunghezza precisamente n....
In sostanza pensavo di trovare qualcosa dallo studio di questa funzione, che conta le funzioni che soddisfano parzialmente le ipotesi (considerando le ripetizioni fino ad una certa lunghezza, insomma)..
Così f(1,m)=3 perchè esistono solo 3 tipi di colonne di un mattoncino, una per ogni colore, e perchè nn possono esistere mai ripetizioni di nessuna lunghezza in una simile colonna.
@tutti: nn è che qualcuno ha trovato con PC o a mano una stringa abbastanza alta: ad impressione io la penso come Maverick: direi che il limite max è infinito!
Cmq io mi indirizzerei verso un tentativo di sol + costruttiva(tipo il metodo di spirale_euclidea)... ma chissà qual è la via giusta? Bisognerà aspettare fino all'anno nuovo? Nel mio caso direi proprio di SI. Auguroni!
Ciao Spirale, la soluzione da te trovata inizialmente è quella che soddisfa le condizioni minime, cioè risponde alla domanda: quanto è lunga la colonna più bassa che si può fare con nc colori di mattoncini prima di essere obbligati a fermarsi.
Quella scritta ( V-R-V-G-R-G-V-R-V ) da jack è corretta, infatti non ci devono essere ripetizioni VICINE, di fila.
Quella che hai scritto: R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V è corretta.
Qualche anno fa, provai "a mano" a trovare la più lunga. Arrivato a 60 (o 80 non ricodro) mi sono accorto che potevo ripeterla completamente (tranne l'ultimo, ovviamente, altrimenti ci sarebbe stata ripetizione). Il numero, quindi, suppongo sia abbastanza elevato, se si osserva l'ultima stringa scritta da spirale si nota che le mosse obbligate (cioè che sono costretto a mettere uno e un solo colore) sono poche e la stringa che si sarebbe ripetuta è di solo pochi mattoncini... mi spiego svolgendo il ragionamento.
La stringa "finale" è R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V
partiamo dall'inizio:
R (posso mettere G o V, quindi due colori, che indico con >2)
R-G (posso entrabe, >2)
R-G-V >2
R-G-V-R >2
R-G-V-R-V >1 infatti non posso mettere R altrimenti alla fine avrei ripetuto V-R, questa è una mossa obbligata che mi fa ripetere una stringa di lunghezza 2, lo incio così >1;2. Andiamo avanti
R-G-V-R-V-G >2
R-G-V-R-V-G-V >1;2 (ripeterei V-G)
R-G-V-R-V-G-V-R >2
R-G-V-R-V-G-V-R-G >2
R-G-V-R-V-G-V-R-G-V >1;3 (questo è il primo caso in cui avrei una ripetizione di tre colori, G-V-R, quindi mossa obbligata ">1" a causa di una ripetizione di 3 mattoncini ";3")
R-G-V-R-V-G-V-R-G-V-G >2
R-G-V-R-V-G-V-R-G-V-G-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G >1;2 (G-R)
R-G-V-R-V-G-V-R-G-V-G-R-G-V >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G >1;3 (R-G-V)
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V >2
Come si può notare i punti in cui eravamo "in difficoltà", dove c'era una mossa obbligata (>1;...) cono pochi e la lunghezza della ripetizione sempre piccola.
Piccolo ragionamento osservando le soluzioni minimali. Con G indico la soluzione che sto cercando, cioè il numero massimo di mattoncini. Dopo la stringa dovrei scrivere >0;(G+1)/2, cioè non ho più possibilità di mettere mattoncini (">0") e ripeto tutta la prima metà della stinga. Se osservate le minimali infatti, prendendo quella con tre colori, la soluzione è 7
e dopo
R-G-R-V-R-G-R scrivo >0;(7+1)/2 cioè >0;4 ripeterei R-G-R-V.
A dire il vero avrei anche una ripetizione da 2. Infatti per finire il tutto, cioè quando mi trovo con le spalle al muro e >0 scritto, ho due cose che si ripetono, una per bolccare un colore e una per bloccare l'altro (il terzo è sempre bloccato)
Ma mi sa che ho messo anche troppa carne a fuoco... andiamo avanti per piccoli step...
WonderP.
Quella scritta ( V-R-V-G-R-G-V-R-V ) da jack è corretta, infatti non ci devono essere ripetizioni VICINE, di fila.
Quella che hai scritto: R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V è corretta.
Qualche anno fa, provai "a mano" a trovare la più lunga. Arrivato a 60 (o 80 non ricodro) mi sono accorto che potevo ripeterla completamente (tranne l'ultimo, ovviamente, altrimenti ci sarebbe stata ripetizione). Il numero, quindi, suppongo sia abbastanza elevato, se si osserva l'ultima stringa scritta da spirale si nota che le mosse obbligate (cioè che sono costretto a mettere uno e un solo colore) sono poche e la stringa che si sarebbe ripetuta è di solo pochi mattoncini... mi spiego svolgendo il ragionamento.
La stringa "finale" è R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V
partiamo dall'inizio:
R (posso mettere G o V, quindi due colori, che indico con >2)
R-G (posso entrabe, >2)
R-G-V >2
R-G-V-R >2
R-G-V-R-V >1 infatti non posso mettere R altrimenti alla fine avrei ripetuto V-R, questa è una mossa obbligata che mi fa ripetere una stringa di lunghezza 2, lo incio così >1;2. Andiamo avanti
R-G-V-R-V-G >2
R-G-V-R-V-G-V >1;2 (ripeterei V-G)
R-G-V-R-V-G-V-R >2
R-G-V-R-V-G-V-R-G >2
R-G-V-R-V-G-V-R-G-V >1;3 (questo è il primo caso in cui avrei una ripetizione di tre colori, G-V-R, quindi mossa obbligata ">1" a causa di una ripetizione di 3 mattoncini ";3")
R-G-V-R-V-G-V-R-G-V-G >2
R-G-V-R-V-G-V-R-G-V-G-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G >1;2 (G-R)
R-G-V-R-V-G-V-R-G-V-G-R-G-V >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G >1;3 (R-G-V)
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R >2
R-G-V-R-V-G-V-R-G-V-G-R-G-V-R-G-R-V >2
Come si può notare i punti in cui eravamo "in difficoltà", dove c'era una mossa obbligata (>1;...) cono pochi e la lunghezza della ripetizione sempre piccola.
Piccolo ragionamento osservando le soluzioni minimali. Con G indico la soluzione che sto cercando, cioè il numero massimo di mattoncini. Dopo la stringa dovrei scrivere >0;(G+1)/2, cioè non ho più possibilità di mettere mattoncini (">0") e ripeto tutta la prima metà della stinga. Se osservate le minimali infatti, prendendo quella con tre colori, la soluzione è 7
e dopo
R-G-R-V-R-G-R scrivo >0;(7+1)/2 cioè >0;4 ripeterei R-G-R-V.
A dire il vero avrei anche una ripetizione da 2. Infatti per finire il tutto, cioè quando mi trovo con le spalle al muro e >0 scritto, ho due cose che si ripetono, una per bolccare un colore e una per bloccare l'altro (il terzo è sempre bloccato)
Ma mi sa che ho messo anche troppa carne a fuoco... andiamo avanti per piccoli step...
WonderP.
Ora noto una cosa. Spirale, tu hai scritto
--------------------------------------------------------------------
numero colori:............ 3 (RGV)
combinazioni:............. 3 (RG-RV-GV)
numero mattoncini:........ 7
risultato:................ R-G-R-V-G-V-R
--------------------------------------------------------------------
in realtà questa serie si può allungare, sono in condizione >2
WonderP.
--------------------------------------------------------------------
numero colori:............ 3 (RGV)
combinazioni:............. 3 (RG-RV-GV)
numero mattoncini:........ 7
risultato:................ R-G-R-V-G-V-R
--------------------------------------------------------------------
in realtà questa serie si può allungare, sono in condizione >2
WonderP.
Forse ho trovato qualcosa in più, ma TUTTA da controllare.
Se esiste una sequenza di 5 che si ripete, allora ne esiste anche una da 2 che si ripete! Ergo, se nn esiste una da due che si ripete, nn ne esiste neanche una da 5. Questo risultato l'ho ottenuto ponendo la serie da 5 uguale a
abcdeabcde
inserendo dentro la condizione che nn vi siano ripetizioni da 2 e/o da 1 si trovano contraddizioni (controllatelo anche voi: l'ho fatto 2 volte ma magari continua a sfuggirmi qualcosa...appena lo fate scrivetelo per favore!).
Questo spero si possa estendere anche a condizioni maggiori di 5 (l'avevo fatto ma mi è venuta appena in mente un errore che ora nn ho voglia di provare a sistemare!)... La conclusione che vorrei ottenere è questa: se nn esistono ripetizioni da 1,2,3,4 allora il tutto rispetta le condizioni. Questo andrebbe contro la serie da 80 di Wonderp ma spero sinceramente che lui abbia fatto qualche errore!:) [scherzoooo]
Insomma f(n,x)=costante per x>=4...
ps:vi informo passo dopo passo così che possiate contribuire, contraddire, dibattere!
Se esiste una sequenza di 5 che si ripete, allora ne esiste anche una da 2 che si ripete! Ergo, se nn esiste una da due che si ripete, nn ne esiste neanche una da 5. Questo risultato l'ho ottenuto ponendo la serie da 5 uguale a
abcdeabcde
inserendo dentro la condizione che nn vi siano ripetizioni da 2 e/o da 1 si trovano contraddizioni (controllatelo anche voi: l'ho fatto 2 volte ma magari continua a sfuggirmi qualcosa...appena lo fate scrivetelo per favore!).
Questo spero si possa estendere anche a condizioni maggiori di 5 (l'avevo fatto ma mi è venuta appena in mente un errore che ora nn ho voglia di provare a sistemare!)... La conclusione che vorrei ottenere è questa: se nn esistono ripetizioni da 1,2,3,4 allora il tutto rispetta le condizioni. Questo andrebbe contro la serie da 80 di Wonderp ma spero sinceramente che lui abbia fatto qualche errore!:) [scherzoooo]
Insomma f(n,x)=costante per x>=4...
ps:vi informo passo dopo passo così che possiate contribuire, contraddire, dibattere!
012102 012102
ma allora dove stà la provvidenza? oh no!
ma allora dove stà la provvidenza? oh no!
Per cominciare Buon Anno a tutti!
Prendendo esempio da Thomas, vorrei condividere anch'io la strada che sto seguendo, affiché vi si possa "...contribuire, contraddire, dibattere!"
Avendo finalmente compreso qual'è l'obbiettivo del problema proposto da WonderP, sono convinto che la serie sia infinita. Dal punto di vista pratico non sarà possibile fornire l'esatta sequenza dei 'mattoncini', ma sarà possibile, da punto di vista matematico, fornirne una formula. Intendo affrontare prima il caso in discussione (l'uso di 'mattoncini' di tre colori diversi) e poi tenterò di generalizzare per un numero arbitrario di colori.
L'idea/intuizione che sto seguendo è la seguente.
Prendo un numero M di mattoncini per ogni colore nC (in questo caso nC=3) per costruire una colonna di N mattoncini (N=M*nC).
So che avrò un numero P di permutazioni possibili (P=N!). Da questo numero P bisognerà sottrarre tutte quelle permutazioni che conterranno le ripetizione di sequenze/combinazioni {S}. Sto cercando di stimare il numero di queste sequenze. Alla fine il risultato sarà il numero di permutazioni possibili che non contengono ripetizioni di sequenze. Aumentando N, aumentano P ed S; resta da stabilire se dalla loro differenza si ottiene sempre un numero maggiore di zero, e quindi la possibilità di costruire all'infinito una colonna senza ripetizioni di sequenza.
Credo che l'ultima osservazione di Thomas, rientri in questa esposizione, quindi...
A tutti noi, buon lavoro! ^_^
------------
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
Prendendo esempio da Thomas, vorrei condividere anch'io la strada che sto seguendo, affiché vi si possa "...contribuire, contraddire, dibattere!"
Avendo finalmente compreso qual'è l'obbiettivo del problema proposto da WonderP, sono convinto che la serie sia infinita. Dal punto di vista pratico non sarà possibile fornire l'esatta sequenza dei 'mattoncini', ma sarà possibile, da punto di vista matematico, fornirne una formula. Intendo affrontare prima il caso in discussione (l'uso di 'mattoncini' di tre colori diversi) e poi tenterò di generalizzare per un numero arbitrario di colori.
L'idea/intuizione che sto seguendo è la seguente.
Prendo un numero M di mattoncini per ogni colore nC (in questo caso nC=3) per costruire una colonna di N mattoncini (N=M*nC).
So che avrò un numero P di permutazioni possibili (P=N!). Da questo numero P bisognerà sottrarre tutte quelle permutazioni che conterranno le ripetizione di sequenze/combinazioni {S}. Sto cercando di stimare il numero di queste sequenze. Alla fine il risultato sarà il numero di permutazioni possibili che non contengono ripetizioni di sequenze. Aumentando N, aumentano P ed S; resta da stabilire se dalla loro differenza si ottiene sempre un numero maggiore di zero, e quindi la possibilità di costruire all'infinito una colonna senza ripetizioni di sequenza.
Credo che l'ultima osservazione di Thomas, rientri in questa esposizione, quindi...
A tutti noi, buon lavoro! ^_^
------------
Tutto quanto l'universo è armonia e numero, con una sola eccezione: l'uomo!
Nn solo l'ultima osservazione, ma quello è il mio obiettivo fin dal primo post!! Il problema è che agire per differenza (cioè togliere dal totale le sequenze cattive) mi pare mooolto complicato (ma è pur sempre una via da tentare....anzi credo proprio che tornerò su questa impervia via quando ci riproverò*!). Del resto la via + costruttiva da mè finora seguita che sarebbe studiare le caratteristiche della funzione f(n,k) (ovverosia provare a contare le sequenza buone) è altrettanto complicato!
Per ora sò solo il valore di f(n,1)---f(n,2) e che f(n,4) = f(n,5) ma i tipi di risultati ottenuti mi scoraggiano!!
[faccio notare che la mia funzione nn è una inutile cavolata: la tesi equivale a dire che f(2n,n)>0 per ogni n]
* anche se per ora rimango dubbioso: alcune sequenze possiedono molte ripetizioni ed è difficile levarle solo una volta. Mi viene in mente il principio di inclusione-esclusione ma nn credo sarei in grado di applicarlo. Del resto come dici tu, spirale, magari basta solo una stima ma questi sono ragionamenti pensati su internet che forse nn dovrei manco scrivere!
Per ora sò solo il valore di f(n,1)---f(n,2) e che f(n,4) = f(n,5) ma i tipi di risultati ottenuti mi scoraggiano!!
[faccio notare che la mia funzione nn è una inutile cavolata: la tesi equivale a dire che f(2n,n)>0 per ogni n]
* anche se per ora rimango dubbioso: alcune sequenze possiedono molte ripetizioni ed è difficile levarle solo una volta. Mi viene in mente il principio di inclusione-esclusione ma nn credo sarei in grado di applicarlo. Del resto come dici tu, spirale, magari basta solo una stima ma questi sono ragionamenti pensati su internet che forse nn dovrei manco scrivere!
Eccomi ritornato dal gozzovigliare capodannifero!
Thomas scrivi:
"Se esiste una sequenza di 5 che si ripete, allora ne esiste anche una da 2 che si ripete! Ergo, se nn esiste una da due che si ripete, nn ne esiste neanche una da 5. Questo risultato l'ho ottenuto ponendo la serie da 5 uguale a
abcdeabcde"
che non ho ben compreso. Ho invefe afferrato il significato di f(n,k) ma quello che aggiongi "la tesi equivale a dire che f(2n,n)>0 per ogni n" mi pare corretto. Assomiglia un po' a quello che avevo scritto io con ">0;(G+1)/2"
provo a scriverne una sufficientemente lunga per fare qualche ragionamento...
GVBGVRGVRVRGVGRVGVRGRVGRGVGRVGRVGRGVRGRVGVRVGRVGVR...
mi pare corretta e in più posso tranquillamente ripeterla dall'inizio (cambiando l'ultima cifra...)
WonderP.
Thomas scrivi:
"Se esiste una sequenza di 5 che si ripete, allora ne esiste anche una da 2 che si ripete! Ergo, se nn esiste una da due che si ripete, nn ne esiste neanche una da 5. Questo risultato l'ho ottenuto ponendo la serie da 5 uguale a
abcdeabcde"
che non ho ben compreso. Ho invefe afferrato il significato di f(n,k) ma quello che aggiongi "la tesi equivale a dire che f(2n,n)>0 per ogni n" mi pare corretto. Assomiglia un po' a quello che avevo scritto io con ">0;(G+1)/2"
provo a scriverne una sufficientemente lunga per fare qualche ragionamento...
GVBGVRGVRVRGVGRVGVRGRVGRGVGRVGRVGRGVRGRVGVRVGRVGVR...
mi pare corretta e in più posso tranquillamente ripeterla dall'inizio (cambiando l'ultima cifra...)
WonderP.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo