"Dire in quanti modi posso mettre in fila i numeri interi da 1 a 10 in modo che siano rispettate le seguenti regole:
1) il primo nemero della fila è sempre 1
2) la differenza tra due numeri che occupano posizioni consecutive nella fila non è mai superiore a 2"
Non sono riuscito nemmeno a capire la formula ricorsiva scritta nel foglio delle risposte (devo ancora comprendere cosa rappresenta [math]X_n) .
Se quancuno potrebbe spiegarmi la formula o darmi un suggerimento per capirla mi farebbe un grande favore. Grazie.
$X_n$ è il numero di modi di mettere in fila gli interi da $1$ a $n$ in modo che siano rispettate le due regole.
Hint: ragiona induttivamente, supponendo di aver già determinato $X_1,\dots,X_{n-1}$. Comincia a costruire una sequenza che fa parte di $X_n$ "con le mani". Il secondo numero della fila può essere 2 oppiure 3. Se è 2, allora quanti modi hai di mettere in fila i numeri successivi, ragionando induttivamente? Se è 3, invece, come può continuare la sequenza? In particolare, quale numero è difficile da piazzare?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
fph ha scritto: ↑28 giu 2025, 04:35
$X_n$ è il numero di modi di mettere in fila gli interi da $1$ a $n$ in modo che siano rispettate le due regole.
Hint: ragiona induttivamente, supponendo di aver già determinato $X_1,\dots,X_{n-1}$. Comincia a costruire una sequenza che fa parte di $X_n$ "con le mani". Il secondo numero della fila può essere 2 oppiure 3. Se è 2, allora quanti modi hai di mettere in fila i numeri successivi, ragionando induttivamente? Se è 3, invece, come può continuare la sequenza? In particolare, quale numero è difficile da piazzare?
Grazie mille Federico (posso chiamarti per nome?) finalmente ci sono arrivato alla soluzione (seppur mi ci sia voluta un intera giornata ). Una domanda un pò più personale, ho trovato su https://fph.altervista.org/oli/index.html la tua prima versione dei barbatrucchi publicata nel lontano 2004 ma ho saputo che negli ultimi anni la stavi ampliando. Potresti dirmi dove posso trovare la versione più recente? Grazie.
P.s. Grazie anche per il tuo aiuto, sopratutto nell'ambito delle dispense e del materiale per la preparazione alle gare.
Problem 3n+1 ha scritto: ↑29 giu 2025, 00:59
Grazie mille Federico (posso chiamarti per nome?)
Certamente!
Purtroppo non ci sono stati aggiornamenti per quella dispensa, mi spiace; tra gli impegni universitari non ci lavoro da parecchio: ora è passato molto tempo e non ho neanche più il sorgente Latex.
Ma nel frattempo fortunatamente è uscito tanto altro materiale, dalle videolezioni dei senior ai libri di U Math.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Non ho visto la soluzione indicata, ma se con [math]X_n si intende il numero di modi in cui si possono allineare n numeri, non mi sembra un punto di partenza comodo. Considero il caso n=10 e solo alla fine ne darò la generalizzazione; poi esporrò un mio dubbio.
Indico con [math]A_k il numero di modi in cui si può continuare quando sono già stati scritti i numeri da 1 a k e l'ultimo di essi è k; trovo direttamente [math]A_9=1 ( posso continuare solo con 10), [math]A_8=2 (posso continuare con 9,10 o con 10,9), [math]A_7=4 (posso continuare con 8,9,10 o con 8,10,9 o con 9,8,10 o con 9,10,8). Penso poi che, in generale, il primo numero che posso scrivere è k+1 o k+2.
a) Se scrivo k+1, continuo in [math]A_{k+1} modi.
b) Se scrivo k+2, ho saltato k+1; posso scriverlo subito o rimqandarlo a dopo.
b1) Se lo scrivo subito, poi posso scrivere solo k+3; continuo in [math]A_{k+3} modi.
b2) Se lo rimando a dopo, devo metterlo all'ultimo posto: infatti potrò scriverlo solo al seguito di k+3 e poi non potrò continuare. Devo quindi salire a numeri alti e poi scendere a k+1 e durante la salita non posso sscrivere due numeri che differiscano di 1 perché impedirebbero la successiva discesa. Devo quindi salire di 2 in 2 fino a 9 o 10, passare dall'uni all'altro di questi e poi scendere: un solo modo.
Perciò [math]A_k=A_{k+1}+A_{k+3}+1
e con questa formula di ricorrenza calcolo [math]A_6=6, A_5=9, A_4=14, A_3=21, A_2=31, A_1=46 . La risposta è quindi 46.
Per generalizzare ad un n qualsiasi, conviene porre [math]A_k=B_h, con h+k=n; il risultato da trovare è allora [math]B_{n-1} e la fomula di ricorrenza diventa [math]B_h=B_{h-1}+B_{h-3}+1
con condizioni iniziali [math]B_1=1; B_2=2; B_3=4
Dubbio. Forse vi siete chiesti perché no uso[math]A_{10}; il motivo è che dopo aver scritto tutti i 10 numeri non posso continuare e quidi porrrei [math]A_{10}=0; se però nella formula di ricorrenza pongo k=7, ne ricavo [math]A_{10}=1. Me ne do una mezza spiegazione pensando che in quel caso il verbo contiuare perde significato, ma non mi convince molto: non starò sbagliando? Ringrazio fin d'ora chi vorrà rispondermi.
.
). Una domanda un pò più personale, ho trovato su 