3 lettere ripetute

[wall98]

(sono anche le ultime lettere di una parola,avendo quindi trovato dei "finali" ripetuti,possiamo supporre che i finali si ripetano cosi all'infinito)

L'intera dimostrazione ruota intorno a questo fatto: é giusto, ma temo vada dimostrato...
Non credo sia troppo difficile, provaci: se non ti dovesse venire in mente niente, qui c'è un hint...

Testo nascosto:

io proverei la dimostrazione per assurdo

La dimostrazione della periodicita dei finali che cercavo di formalizzare era piu o meno quella di Angelo3,si basava sulla congruenza mod 3 di una determinata parola,notava che se la parola è congrua 2 per esempio rimangono due lettere,che sono BC poiche la generazione della nuova parola(e quindi quella del finale)dipende dal finale della precedente...
Per il primo bonus con "sequenza come quella di jigen" intendi $ A $ $ AB $ $ ABC $ $ ABCD $ ecc. vero?

[Ouroboros]

Sì, quella

[wall98]

Per il primo bonus...
la differenza tra $ A $ e $ C $ all' n-esima lettera con modulo di ripetizione $ m $ è data dalla formula
$ \displaystyle \sum_{k=1}^n \left[\frac{n-k}{m}\right]-\left[\frac{n-k-2}{m}\right] $
dove con le parentesi quadre si intende la parte intera..(purtroppo una formula piu compatta non sono riuscito a trovarla,in alternativa si potrebbe fare una somma coi moduli,anche se non mi sembra piu sbrigativa di questa..)
ora si dimostra,allora prima di tutto si va a dire che in una determinata parola le $ A $ occupano le posizioni determinate dalla formula $ 1+mk_1 $ mentre le $ C $ dalla formula $ 3+mk_2 $ sotto il vincolo
$ 1+mk_1\le n $
$ 3+mk_2\le n $
(ovviamente è tutto intero)
la differenza da noi cercata equivale alla differenza tra il massimo che assume $ k_1 $ e il massimo che assume $ k_2 $ sotto i vincoli
e questo massimo è $ \displaystyle k_1=\left[\frac{n-1}{m}\right] $ e $ \displaystyle k_2=\left[\frac{n-3}{m}\right] $
da cui la differenza $ \displaystyle \left[\frac{n-1}{m}\right]-\left[\frac{n-3}{m}\right] $
per la parola precedente i vincoli sono
$ 1+mk_1\le n-1 $
$ 3+mk_2\le n-1 $
e si ricava
$ \displaystyle \left[\frac{n-2}{m}\right]-\left[\frac{n-4}{m}\right] $
si itera questo processo n volte...
da cui la formula,è giusta?


EDIT:Ci sarebbe un altro tipo di soluzione che afferma
1 se n è congruo a 1 modulo m,allora la formula è $ \displaystyle 2\left[\frac{n}{m}\right]+1 $
2 se n è congruo a 2 modulo m,allora la formula è $ \displaystyle 2\left[\frac{n}{m}\right]+2 $
3 in tutti gli altri casi è (come il punto 2) $ \displaystyle 2\left[\frac{n}{m}\right]+2 $
4 se n è congruo a 0 modulo m,allora è $ \displaystyle 2\left[\frac{n}{m}\right] $
DIMOSTRAZIONE
dobbiamo prima trovare quali sono le parole della sequenza che fanno aumentare la differenza,esse sono tutte quelle parole in cui compare una A ma non la corrsipondente C,sono tutte le parole che terminano per
$ A $
$ AB $
e sono $ \displaystyle 2\left[\frac{n}{m}\right] $
per queste la differenza aumenta di 1,mentre per le altre la differenza è nulla,quindi sono solo queste che influiscono sul risultato che sara appunto $ \displaystyle 2\left[\frac{n}{m}\right] $.Ma allora perche è in contraddizione con le prime tre ipotesi?
1 se n è congruo ad 1 mod m,allora ci sara una nuova parola che termina per A,se il blocco precedente(alla parola) vale $ \displaystyle 2\left[\frac{n}{m}\right] $,qui bisogna aggiungere 1
2 stesso discorso del punto 1,a differenza che c'è una parola che termina per A,e una per AB..quindi $ \displaystyle 2\left[\frac{n}{m}\right]+2 $
3 in tutti gli altri casi "spunta" di nuovo una C che elide la A che prima aveva costretto ad aggiungere,e logicamente la differenza rimane costante è $ \displaystyle 2\left[\frac{n}{m}\right]+2 $ e continua ad esserlo poiche nelle parole che si vanno a creare compare una A e una C(fino a che non ricadiamo nella fine del ciclo modulare ovviamente)
4 il periodo è chiuso,non si aggiunge niente,la formula è $ \displaystyle 2\left[\frac{n}{m}\right] $
PS:non ne sono troppo sicuro di questa dimostrazione,se qualcuno riesce a capire qualcosa di quello che ho scritto puo dirmi se è giusta?

[Ouroboros]

Premetto che la seconda mi sembra migliore della prima perché più accessibile ( anche se magari meno rigorosa)
Nella prima dimostrazione, quando affermi che $ k_1, k_2 $ esprimono il massimo delle A e delle C nella parola, dimentichi che potrebbero assumere anche il valore 0... infatti, secondo questa definizione che tu hai dato, nella prima parola (A), considerato quindi n=1 e m qualunque, il massimo $ k_1 $ é 0, quindi ci sono zero A... in realtà il valore di A e C é rispettivamente $ k_1 +1, k_2 +1 $, ma dipende dai casi (ad esempio sempre nella prima parola il numero di C é zero, infatti non esiste un $ k_2 $ naturale che risolva la disequazione... quindi nella mia formula conta come -1, andrebbe un po' aggiustata...)
Per la seconda soluzione io semplicemente la sintetizzerei in $ [\frac{n}{m}]+k $, con k che assume i valori 0, 1 o 2 seguendo i casi che hai descritto
Io avevo pensato a questa seconda soluzione perché poi é molto facile generalizzare

[wall98]

In un estremo tentativo di difesa della prima dimostrazione,non ho mai detto che $ k_1,k_2 $ esprimono le A e C,bensi che la loro differenza è uguale ad A-C,ma lo ammetto non ci avevo pensato
Poi $ k_2 $ puo essere -1,nessuno lo vieta,infatti scegliendo come hai detto tu n=1 viene fuori proprio -1 e siccome -(-1)=1 funziona anche per il caso N=1
PS: in effetti la seconda dimostazione è molto generalizzabile,si potrebbe anche provare a risolvere il bonus del bonus..

[Ouroboros]

In un estremo tentativo di difesa della prima dimostrazione,non ho mai detto che $ k_1,k_2 $ esprimono le A e C,bensi che la loro differenza è uguale ad A-C

D'accordo, però va comunque aggiustata... a me viene in mente solamente di aggiungere alla sommatoria il solito parametro k che può assumere i valori 0, 1 e 2 a seconda dei casi ( ma a questo punto si ricade nei moduli ed é meglio usare l'altra dimostrazione)
Se ti viene in mente qualcosa per aggiustare la prima dimostrazione... altrimenti prova il bonus del bonus!

[wall98]

Riporto qui il testo del bonus del bonus....
Date m lettere distinte e un intero n,determinare,in funzione di 2 lettere qualsiasi scelte arbitrariamente nell'insieme m,la differenza tra il numero di volte che compare nella sequenza la lettera che compare di piu e quella che compare di meno (le lettere sono intese in ordine alfabetico)

innanzitutto dobbiamo determinare quale delle due lettere appare prima,poniamo wlog che x appare prima di y (sono incognite,non lettere)
riciclando la dimostrazione 2 del precedente problema,si vedeva che le parole che influivano sulla differenza tra le A e le C erano quelle che terminavano per A e per AB,perche poi veniva ABC e la differenza si annullava,le parole erano due perche definendo le lettere per la propria posizione si ha che C=3 e A=1 $ 3-1=2 $ cioè tutte le parole che possiamo costruire in successione con A senza C, facciamo una cosa del tutto analoga,sia $ x_1 $ la posizione di $ x $ e $ y_1 $ la posizione di $ y $ ,dalla dimostrazione 2 si evince che le parole che variano la differenza sono $ \displaystyle (y_1-x_1)\left[\frac{n}{m}\right] $
E qua si ricade nelle ipotesi di prima con numeri diversi
$ \displaystyle (y_1-x_1)\left[\frac{n}{m}\right]+k $ e bisogna analizzare i valori k
1 se $ n $ è congruo a $ 0 $ Mod m il periodo è chiuso,e k è effettivamente $ 0 $
3 se $ n $ è congruo alla posizione di x,allora k=1 perche viene inserita per la prima volta il termine x
vediamone un esempio per spiegare meglio con x=C,m=6,y=F,n=9
$ A $
$ AB $
$ ABC $
$ ABCD $
$ ABCDE $
$ ABCDEF $
$ ABCDEFA $
$ ABCDEFAB $
$ ABCDEFABC $
$ ABCDEFABCD $
$ ABCDEFABCDE $
in questa piramide è rappresentata appunto la sequenza,si vede che la parte intera di n fratto m ci da quante volte si ripete il periodo,e quella parte quindi l'abbiamo calcolata,ci si puo dunque concentrare sui tre termini successivi,si vede che il termine x appare tre passaggi dopo,e quindi è congruo a 3 mod m(6)
4 dall' esempio precedente si vede che la differenza aumentava man mano che (una volta comparsa la C) si costruivano altre parole,questo perche la C veniva ripetuta senza che ci fosse una F a bilanciare,quindi possiamo vedere che k aumenta di 1 ad ogni parola fino ad arrivare alla prima parola contenente $ y $,e da quel punto in poi la differenza è stabile fino ad arrivare al modulo,poiche prima di esso non compariranno altre x e y
2infine possiamo notare che prima di arrivare al termine x(partendo dal modulo)la differenza rimane costante ed è la formula chiusa $ \displaystyle (y_1-x_1)\left[\frac{n}{m}\right] $ con k pari a 0 poiche non è stato ancora aggiunto niente...
Ricapitolando..
1 se $ n\equiv 0\pmod{m} $ il periodo è chiuso,e la differenza è $ \displaystyle (y_1-x_1)\left[\frac{n}{m}\right] $
2 se n mod m$ <x_1 $ la differenza è $ \displaystyle (y_1-x_1)\left[\frac{n}{m}\right] $ (questo ingloba anche il punto 1)
3 se $ x_1\le $ n mod m$ <y_1 $ la k è crescente di 1 ad ogni passaggio,partendo da 1 per arrivare a $ n mod m $,quindi $ k=n-x_1 $
4 se n mod m$ \ge y_1 $ k è $ y_1-x_1 $ perche è quanto k ha potuto "guadagnare" durante il punto 3, perche guadagna 1 in $ y_1-x_1 $ passaggi

PS:non guardate l'ordine dei punti,ho dovuto riordinare alla fine e ho fatto un po di casino
EDIT:ho trovato una formula per il punto tre

[Ouroboros]

A parte una piccola cosa (nel punto 3 delle conclusioni hai scritto $ k=n-x_1 $, in realtà non é n bensì n mod m...) sembra tutto giusto. Ottimo!
Rimarrebbe da fare lo stesso con la mia sequenza ( ma oggi non ci ho provato )... sempre che sia fattibile

[wall98]

Hai ragione,brutta disattenzione causa stanchezza
riguardo la tua sequenza penso tentero domani.ciao