2000 – 17

Considerate le seguenti definizioni:

  • un simbolo è una cifra o una lettera;
  • un codice è una sequenza (stringa) di simboli che inizia e termina con una lettera, che contiene almeno una cifra, e che non contiene mai due cifre consecutive;
  • dato un codice, un suo sottocodice è una sua sottostringa che sia a sua volta un codice;
  • un codice è minimo se non contiene sottocodici (a parte lui stesso).

Dire quali delle seguenti affermazioni sono vere (è possibile che più di una affermazione sia vera: occorre indicarle tutte):

  1. ogni codice ha lunghezza maggiore o uguale a 3;
  2. nessun codice contenente più di due lettere è minimo;
  3. ogni codice ha lunghezza minore o uguale a 36;
  4. il numero di sottocodici minimi di un codice dato è uguale al numero di cifre che esso contiene;
  5. il numero di sottocodici minimi di un codice dato è minore o uguale alla metà del numero di lettere che esso contiene;
  6. nessun codice di lunghezza maggiore di 3 è minimo.

Soluzione: —