Successione di operazioni modulo
Non sapevo bene dove postare, quindi ho scelto questa sezione.
Ho trovato il seguente problema:
"Siano $m,n\in\mathbb{N}\\{0}$ e siano date n caselle.
Iniziando a contare dalla prima, cancelliamo la casella m-esima, poi, partendo dalla casella successiva a quella, di nuova l’m-esima tra quelle rimaste, procedendo in maniera ciclica quando necessario e passando eventualmente più volte sopra la stessa casella. Ripetiamo questa operazione fino quando rimane una sola casella. Qual’è questa casella?"
Indichiamo tale casella con L(n,m), allora si trova abbastanza facilmente che $L(n+1,m)=(L(n,m)+m) mod n+1$.
Poichè $L(1,m)=0$, si ottiene che in generale:
$L(n,m)= (((((((m mod 2) + m) mod 3) + m) mod 4) + m) mod 5 + ...) mod n $
Che è una successione abbastanza particolare, l'ho cercata sul sito dell'OEIS per diversi valori di m ed n ma non ho trovato nulla. Qualcuno l'ha già incontrata? Esiste una formula diretta per calcolarla (mi sembra molto difficile però) o perlomeno altre relazioni che la riguardano?
Ho trovato il seguente problema:
"Siano $m,n\in\mathbb{N}\\{0}$ e siano date n caselle.
Iniziando a contare dalla prima, cancelliamo la casella m-esima, poi, partendo dalla casella successiva a quella, di nuova l’m-esima tra quelle rimaste, procedendo in maniera ciclica quando necessario e passando eventualmente più volte sopra la stessa casella. Ripetiamo questa operazione fino quando rimane una sola casella. Qual’è questa casella?"
Indichiamo tale casella con L(n,m), allora si trova abbastanza facilmente che $L(n+1,m)=(L(n,m)+m) mod n+1$.
Poichè $L(1,m)=0$, si ottiene che in generale:
$L(n,m)= (((((((m mod 2) + m) mod 3) + m) mod 4) + m) mod 5 + ...) mod n $
Che è una successione abbastanza particolare, l'ho cercata sul sito dell'OEIS per diversi valori di m ed n ma non ho trovato nulla. Qualcuno l'ha già incontrata? Esiste una formula diretta per calcolarla (mi sembra molto difficile però) o perlomeno altre relazioni che la riguardano?
Risposte
Grazie per il link, immaginavo avesse un nome o qualcosa del genere, tra l'altro è un problema che ho trovato in giro, ma da solo non l'avrei mai trovato. Ho capito perchè non c'era sul sito dell'OEIS, perchè iniziavo a contare da 0. Con la sequenza giusta infatti si trova
Se non ricordo male, Tartaglia si era occupato del caso $m=9$ e $n=30$, codificando il modo per far rimanere 15 caselle specifiche* in una frase latina di cui considerare le vocali.
*Si tratta una conta per decidere i 15 da buttare in mare in un cerchio di 30, e l'obiettivo è disporli in modo da salvare quelli di religione giusta
*Si tratta una conta per decidere i 15 da buttare in mare in un cerchio di 30, e l'obiettivo è disporli in modo da salvare quelli di religione giusta
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo