Codici in sequenza

[consec]

"La cassaforte su cui Arsenio ha messo gli occhi è dotata di una tastiera con tre tasti che riportano rispettivamente le lettere A,B,C. Il codice segreto, che permette di aprirla, è una sequenza di queste tre lettere (con A, B e C eventualmente ripetute). Se gli ultimi tre tasti schiacciati sono quelli che formano il codice segreto, la cassaforte si apre. Grazie alla soffiata di un complice, Arsenio sa che il codice comincia con A. Arsenio vuole schiacciare meno tasti possibile ma quanti ne dovrà schiacciare per essere sicuro in ogni modo di aprire la cassaforte?"

In pratica i codici possono essere "incastrati" tra loro, ad esempio se si vogliono provare le combinazioni AAA e AAB allora la scrittura AAAB permette di verificarle entrambe con soli 4 caratteri. Il problema chiede il numero minore possibile di caratteri della stringa tale che tutti i 9 codici inizianti per A sono stati esaminati. In spoiler scrivo la risposta, a cui si può arrivare a tentativi, ma sarei interessato a una dimostrazione rigorosa.

19

[Vincent46]

"consec":"La cassaforte su cui Arsenio ha messo gli occhi è dotata di una tastiera con tre tasti che riportano rispettivamente le lettere A,B,C. Il codice segreto, che permette di aprirla, è una sequenza di queste tre lettere (con A, B e C eventualmente ripetute). Se gli ultimi tre tasti schiacciati sono quelli che formano il codice segreto, la cassaforte si apre. Grazie alla soffiata di un complice, Arsenio sa che il codice comincia con A. Arsenio vuole schiacciare meno tasti possibile ma quanti ne dovrà schiacciare per essere sicuro in ogni modo di aprire la cassaforte?"

In pratica i codici possono essere "incastrati" tra loro, ad esempio se si vogliono provare le combinazioni AAA e AAB allora la scrittura AAAB permette di verificarle entrambe con soli 4 caratteri. Il problema chiede il numero minore possibile di caratteri della stringa tale che tutti i 9 codici inizianti per A sono stati esaminati. In spoiler scrivo la risposta, a cui si può arrivare a tentativi, ma sarei interessato a una dimostrazione rigorosa.

19

non so se è davvero rigorosa, ma mi è venuto in mente questo.

è chiaro che le sequenze
ABC, ACB, ACC, ABB
debbono necessariamente comparire nella stringa, e non è possibile concatenarle in alcun modo. mancano da inserire le password AAA, AAB, AAC, ABA, ACA. Ora, dato che, fra queste, in particolare sono anche presenti le stringhe ABA e ACA, è chiaro che da qualche parte dovranno comparire anche le sequenze AB e AC, perché non è possibile concatenarle con sequenze già presenti nella stringa. Allora suppongo, ad esempio, di legarle alle prime due sequenze che già avevo messo nella stringa:
ABABC, ACACB, ACC, ABB. Mi rimangono da inserire le password AAA, AAB, AAC. Tuttavia è possibile inserire ciascuna di esse utilizzando una sola lettera per ognuna, e non è evidentemente possibile fare meglio di così. Questo porta, ad esempio, alla stringa "buona"
AAABABCAACACBACCABB

[consec]

Diciamo che questa è una dimostrazione abbastanza "intuitiva", che immagino sia quella che si chiedeva agli studenti durante la competizione (il problema è tratto dai Giochi Matematici della Bocconi 2014 per studenti di seconda, terza e quarta delle superiori) fattibile perché i casi di analizzare sono comunque pochi. Ero curioso di leggere una dimostrazione che si potesse generalizzare, ossia codici da x lettere che iniziano per una tra y lettere, con y incluso in x, o comunque sempre riferita a questi dati ma formalizzata, magari con la risposta fornita dal problema, così che si possa fare un ragionamento per assurdo. Grazie comunque per la risposta.