E’ stato inventato un nuovo sistema di rappresentazione dei numeri. Si utilizzano due simboli: # e @. Il simbolo # in fondo ad una sequenza significa aggiungere un’unità, mentre il simbolo @ significa moltiplicare per 7. Ad esempio la sequenza #@##@# rappresenta il numero 64. Qual è il minor numero di simboli per rappresentare il numero 1000?
La soluzione più completa pervenutami è quella di Frigate :
Regole per la costruzione di rappresentazioni minime (col minor numero di simboli):
1) Una rappresentazione minima inizia sempre con il simbolo #.
esempio:
# # #
@ # # #
@ @ # # #
@ … @ # # #
sono rappresentazioni dello stesso numero.
La prima contiene il numero minimo di simboli.
2) Data una rappresentazione minima, quella del numero successivo si ottiene aggiungendo il simbolo #.
esempio:
# # @
la successiva e’
# # @ #
3) Se applicando la regola 2) si ottiene una rappresentazione in cui compare la sequenza ‘ @ # # # # # # # ‘, questa viene sostituita con la coppia ‘ # @ ‘.
Infatti, ‘ @ # # # # # # # ‘ corrisponde all’ espressione ‘ y*7+7 ‘ che puo’ essere sostituita da ‘ (y+1) * 7 ‘.
esempio:
# @ # # @ # # # # # # # e # @ # # # @
rappresentano lo stesso numero, ma la seconda e’ in forma minima.
esempio:
# # @ # # # # # # @ # # # # # # #
diventa
# # @ # # # # # # # @
poi
# # @ # # # # # # # @
diventa
# # # @ @
4) Un numero della forma x = 7^n, verra’ rappresentato nel seguente modo:
# @ @ …. @ dove i simboli @ sono n.
esempio:
il numero 7 si puo’ rappresentare come
# # # # # # #
si puo’ vedere come
@ # # # # # # #
quindi per la regola 3) si ha
# @
esempio:
il numero 7^3 = 343 si puo’ rappresentare come
# # # # # # @ # # # # # # @ # # # # # # #
diventa
# # # # # # @ # # # # # # # @
diventa
# # # # # # # @ @
si puo’ vedere come
@ # # # # # # # @ @
diventa
# @ @ @
5) Dalle precedenti regole segue che una rappresentazione minima puo contenere una sequenza di simboli # consecutivi, al piu’ di lunghezza 6.
Volendo trovare la rappresentazione minima di un numero X, evidenziamo il quoziente e il resto della divisione di X per 7:
X = Q * 7 + R
Tenendo conto della regola 5) e di quanto detto in precedenza, la rappresentazione minima di X si ottiene applicando ricorsivamente la seguente formula:
M( X ) = M( Q ) | @ | #( R )
dove
#( R ) indica un numero di simboli # pari a R.
M( X ) indica la rappresentazione minima di X.
M( Q ) indica la rappresentazione minima di Q.
Adesso, sfruttando la formula prcedente, calcoliamo la rappresentazione minima di X = 1000.
X = 1000 —> Q = 142, R = 6
da cui
M( 1000 ) = M( 142 ) | @ | #( 6 )
X = 142 —> Q = 20, R = 2
da cui
M( 142 ) = M( 20 ) | @ | #( 2 )
X = 20 —> Q = 2, R = 6
da cui
M( 20 ) = M( 2 ) | @ | #( 6 )
X = 2 —> Q = 0, R = 2
da cui
M( 2 ) = M( 0 ) | @ | #( 2 ) = #( 2 )
Componendo i risultati si ha:
M( 1000 ) = #( 2 ) | @ | #( 6 ) | @ | #( 2 ) | @ | #( 6 )
ovvero
M( 1000 ) = # # @ # # # # # # @ # # @ # # # # # #
La soluzione di RobertoC75 :
##@######@##@######
I simboli @ trovati a sinistra del primo # non hanno influenza sul numero poiche’ andrebbero a moltiplicare 0 * 7.
(((1+1)*7 +1+1+1+1+1+1)*7 +1+1)*7 +1+1+1+1+1+1 = 1000
Per trovare la soluzione ho scritto un piccolo algoritmo, lasciando al calcolatore l’onere di controllare tutte le possibili combinazioni (in fondo il sistema @# e’ un sistema binario). Altre soluzioni richiedono ovviamente piu’ simboli.
La soluzione diBooDoo :
Il numero è ##@######@##@######
Per ottenerlo sono partito dalla fine effettuando le due operazioni di divisione tra interi e di modulo tra 1000 e 7 ottenendo 142 e 6.
A questo punto ho iniziato a scrivere il numero dalla fine inserendo 6 simboli # e 1 simbolo @ (@######); ho quindi reiterato le stesse operazioni tra 142 e 7 ottenendo 20 e 2.
Ho quindi aggiunto, da destra verso sinistra 2 # e 1 @ (@##@######); ho quindi reiterato le stesse operazioni tra 20 e 7 ottenendo 2 e 6 e il numero è diventato @######@##@######.
Per finire tra 2 e 7 ho ottenuto 0 e 2 ed il numero finale è ##@######@##@######.
Continuando a rifletterci ho trovato un secondo metodo risolutivo molto più elegante;
Scrivendo il numero 1000 in base 7 si ottiene 2626 che si può riscrivere utilizzando il nostro sistema di numerazione proprio come ##@######@##@###### dove indico le cifre con un uguale numero di simboli # e il simbolo @ è un separatore.
Faccio un altro esempio 49 in base 7 diventa 100 e nel nostro sistema #@@ dove il valore 0 sorrisponde a 0 simboli #.