Bravo!!!

"Appunti di Informatica" ha preso una brutta piega... A dire il vero non volevamo trasformarla in una rubrica di giochini numerici. E non la trasformeremo. Questa è l'ultima volta che parleremo di giochini dei lettori. Promesso. Tutto è iniziato su MC n. 61 quando un lettore di Gorizia, tal Antonio Cunei, contestando alcune affermazione del sottoscritto di un paio di numeri prima, concludeva la sua lettera proponendo un giochino numerico. Nelle settimane a seguire, sono giunte in redazione molte lettere di lettori che non solo avevano risolto il gioco, ma riuscivano anche a dimostrare alcune importanti proprietà.

Tra tutte queste, una lettera faceva eccezione: un povero lettore non era riuscito a risolvere il quesito e dopo aver perso buona parte delle sue giornate nei vari tentativi, decise di inviare a noi la sua protesta vendicativa proponendo un altro giochino interamente dedicato al Cunei...

Sul numero 64 pubblicammo le lettere più interessanti, ben certi di sollevare nuovi entusiasmi. Ancora una volta ci hanno scritto in molti... vediamo però cosa è effettivamente successo.

Bravo, chi?

Beh, questo ve lo diremo tra un po'... e non saltate a piè pari  tutta la prima parte dell'articolo. Prima, per correttezza, ricorderemo i quesiti maledetti. Il primo, proposto dal lettore di Gorizia, era formulato così:

E' data la sequenza:

1

11

21

1211

111221

312211

13112221

1113213211

Indicare il prossimo numero della sequenza. Inutile dire che rimandiamo i lettori che non conoscono di già la soluzione al numero 64 di MC.

Come già detto, in quella sede, un lettore che non era riuscito a risolvere l'enigma e per vendicarsi ne proponeva un altro. Diceva:

"Trovare un numero tale che spostando la prima cifra dopo l'ultima si ottiene un numero che è esattamente la metà del primo"

Interrogato il 128 del sottoscritto (ovvero fatto partire uno stupido programmino "ricercatore") non si ottenevano risultati in un tempo ragionevole... ma come ampiamente discusso nella serie di articoli sulla calcolabilità ciò non autorizza a pensare che la soluzione non esista. Ciò che ci ha letteralmente portati fuori strada è stata un'osservazione dell'autore della lettera che diceva di averlo risolto in "modo oscenamente semplice". Fuori strada il sottoscritto, molti lettori intervenuti, nonché il Cunei di cui sopra che non solo non ha risolto il problema, ma inviandoci una cartolina da Monfalcone, che non esitiamo a pubblicare fotograficamente, proclamava:

"Ah, impudente !!! Osare sfidarmi in cotal guisa! A me, a me che ogni giorno litigo con shift in qua e in là!"

Spaccone, vero?

"Bravo!!!" a chi, il numero, l'ha trovato sul serio.

Oscenamente semplice

Quasi tutti i lettori intervenuti, compreso il sottoscritto ("primo lettore" di Appunti di Informatica), sono caduti nel tranello "oscenamente semplice". In effetti la soluzione, come avremo modo di constatare tra poco, è semmai oscenamente complicata. Tutti, sottolineo tutti, quelli che hanno sbagliato, hanno pensato alla numerazione binaria. Forse per quel "esattamente la metà" che implica una divisione per 2. Come noto, infatti, i numeri binari godono della proprietà che shiftandoli di una cifra verso destra otteniamo un numero pari alla metà del primo, shiftandoli verso sinistra otteniamo un numero pari al doppio. Il fattore di divisione o moltiplicazione è, dunque, pari alla base. Si noti che tale proprietà vale per tutti i numeri arabi, in qualsiasi base. Per i decimali il fattore è 10, per gli esadecimali 16 e così via.

Ora,  prendendo qualsiasi numero binario terminante per 0, e intendendo per "prima cifra" quella meno significativa e per "ultima cifra" quella più significativa, abbiamo una banale soluzione del gioco... in base due.

Ad esempio, prendendo il numero binario 100 (4 in decimale), effettuando lo spostamento testé descritto otteniamo 010, o più semplicemente 10, che è la metà del primo (10 binario in decimale è pari a 2).

Ma come ci segnala il lettore Perticarini Paolo di Fermo, è possibile anche intendere per "prima cifra" quella più significativa: nell'esempio da lui inviato, prendendo il numero 1010 binario che vale 10 in decimale ed effettuando la rotazione in verso opposto otteniamo 0101 binario che in decimale vale 5. Complimenti.

Già che ci siamo, segnaliamo la lettera del simpatico Marco Fiorentini di Milano, che segnalandoci la sua soluzione binaria, e specificando che per prima cifra "bisogna" considerare quella meno significativa, non s'è accorto che il suo esempio funziona anche "roteando" al contrario (prima cifra, la più significativa). Pazienza.

Simpaticone!!!

Prima di continuare, vogliamo svelarvi in anteprima il numero maledetto, inserendo in questo punto dell'articolo la lettera di un lettore che non annoveriamo tra i "Bravi!!!" solo perché non ha giustificato la risposta (sembra un esame di università, vero? come sta il tuo primo trenta... è ancora solo?)...

Caro comm. lupo mann. Andrea de Prisco,

ma non avevi altro da fare oltre ad una rivista d'informatica? Che so, una serie di bei servizi su «le mille ricette di miss Borgia» non ti sarebbero graditi di più? No, non è che ce l'ho con te (ti do del tu, ma in questo momento preferirei darti un paio di bei schiaffoni), è solo che sono incavolato nero. Vengo al punto.

Era il fatidico mese di giugno, e preso il primo trenta in vita mia vado a comperare il meritato numero di Me. Toh, si parla di giochi, mi dico sfogliandolo, e vado malauguratamente a leggere per la prima nefasta volta in vita mia «Appunti d'Informatica». E che leggo? Un lettore napoletano che subdolamente scrive «trovare un numero tale che spostando la prima cifra dopo l'ultima si ottiene un numero che è esattamente la metà del primo».

Sottotitolo: soluzione tremendamente semplice. AAAMRGH

Se avessi saputo prima a cosa andavo incontro, avrei preferito suicidarmi con una P38 caricata a supposte. Come un tarlo nel legno, quel numero m 'ha rosicchiato il cervello. E ho il prossimo esame a giorni! Basta, ho detto oggi. Mi faccio una bella dormita mentre affido a Genio (il mio Spectrum, ultimamente ha delle crisi, si crede un IBM) il compito di stanare quel numeraccio malefico. Unica soddisfazione, sapere che c'è chi ci ha passato su una notte intera col 128 (ne sai niente ?). Forse la soluzione sta nei decimali, ho detto. E giù un loop con uno step da voltastomaco: punto zero uno, e me ne sono andato a letto.

Ma dico, in fondo sono solo uno studente di Odontoiatria, non ho mai ucciso nessuno, uso il mio Genio solo per scrivere romanzi di fantascienza; perché mi sono fatto invischiare in questo scherzo da prete?

E sì, perché di scherzo si tratta: manco pensare a dormire, ho notato che in otto (OTTO)fogli di stampa zeppi di numeri che si avvicinavano ad essere l'uno il doppio dell'altro avendo solo una cifra spostata secondo le demoniache regole, ho notato che i numeri comincianti per 19 si avvicinavano più di tutti alla miracolosa soluzione. Così; sfidando il surriscaldato Genio (che, non essendo un computer troppo tagliato per la matematica, s'inventava cifre decimali fantasma di origine misteriosa), con carta e penna ha elaborato il 19. Risultato? Vuoi davvero saperlo? Beccati questo 105263157894736842, che non so neanche come si legge. Scherzo da prete, ripeto, perché Genio s'è rivolto ai sindacati: lui arriva a malapena a comunicarmi otto cifre, e un numero di * DICIOTTTO CIFRE * è sadismo irresponsabile per un computer appena inferiore al Cray. Tornando - per l'ultima volta in vita mia! al bastardo: 105'263'157'894736'842 è perfettamente il doppio del suo cugino con la prin1a cifra spostata in coda, 052'631 '578'947'363'421.

Teoria: che il mostro di Firenze sia semplicemente uno cui ha dato di volta il cervello nella ricerca della soluzione di simili oscenità? Perché se continuate a pubblicare di questi giochi, comincerò ad ululare nelle notti di luna piena.

Scherzi a parte, complimenti per la rivista, ben venga la rubrica di giochi Øma attenzione a non far venire le crisi ai computer! Diciotto cifre! - e di' al Big Boss Nuti che continui a testa bassa contro le scempiaggini della SIP, che funziona.

Ora vado a fare gli impacchi di ghiaccio a Genio.

Oscenamente complicato

Detto questo, veniamo al primo dei due lettori "Bravi!!!". Il suo nome è Mario Pelissetto e abita a Genova. Egli, da bravo "Bravo!!!" non solo ha trovato il numero (in base dieci) che gode della proprietà di cui sopra, ma ha anche fornito il procedimento matematico col quale è pervenuto alla soluzione.

Non vi nascondo che leggendo la sua lettera, più di una volta ho pensato che stesse scherzando... Leggendo:

"Basta trovare quel numero formato da tutti 1 che è esattamente divisibile per 19, moltiplicarlo per 18 e il gioco è fatto..."

chiunque avrebbe pensato lo stesso.

Eppure, la matematica non è un'opinione, ha ragione. Il numero da dividere per 19 è formato da 18 "uno" e il quoziente è:

5847953216374296

moltiplicandolo per 18 abbiamo la prima soluzione (sì, ce ne sono altre) che dovremmo già conoscere:

105263157894736842

Mettendo la sua prima cifra dopo l'ultima, otteniamo:

052631578947368421

che è esattamente la metà del primo. A chi non piace lo zero iniziale (a dire il vero, come conferma anche il "saggio", non si tratta di una vera soluzione) non disperi, le altre soluzioni segnalate sempre dal Pelissetto non soffrono di tale anomalia.

Scommettiamo che siete curiosi di sapere come ha fatto ? Lo ero anch'io, prima di leggere la seconda parte della lettera. In fatti, come dice il lettore, "la logica c'è..."

Dimostrazione

Lasciamo a lui la parola: "Chiamiamo X il numero che vogliamo individuare, C la sua prima cifra, N il numero di cifre di cui è composto.

Il numero si ottiene spostando la prima cifra C di X dopo l'ultima, dunque è dato dall'espressione:

(X-C 10N-1) 10 + C

infatti se X=210, allora C=2 e N=3, quindi (210-2*102)*10+2= 102 che è proprio la rotazione di 210.

L'espressione di sopra, semplificabile in

10 X-C (10N-1)

deve essere posta uguale ad X diviso 2, per la proprietà di cui deve godere tale numero:

X/2 = 10 X-C (10N-1)

da cui otteniamo:

X = 2/19 C (10N-1)

In questa formula, C ed N possono assumere solo un limitato numero di valori; C è una cifra da 1 a 9, N è un intero maggiore uguale a 2.

(si noti che il termine 10N-1 e un numero formato da N nove consecutivi, ndr)

X deve essere un intero per cui dovremo trovare il primo numero, formato da tutti "9", che è esattamente divisibile per 19. Siccome 999...9 e uguale a 111...1x9, il problema si riduce a trovare il primo numero formato da tutti "1" che sia divisibile per 19, moltiplicando poi in quoziente per 2x9=18.

Questo per C=1, ma la proprietà dovrebbe valere (vale, e come se vale!, ndr) anche per gli altri valori di C da 2 a 9...."

Il secondo bravo

Il secondo lettore che ha risolto il quesito, Andrea Sodomaco di Trieste, ci ha inviato una soluzione altrettando interessante, fornendoci anche un programmino atto alla ricerca di tali numeri. Il programma è scritto in AmigaBasic (perfettamente "girevole" anche sul Mac) e sono state effettuate un po' di modifiche per renderlo un tantino più leggibile ma soprattutto per estendere la soluzione anche a divisori diversi dal 2. Col programma modificato, infatti, è possibile chiedere anche "i numeri tali che, spostando la prima cifra dopo l'ultima otteniamo un numero esattamente 4, 13 o 60 volte più piccolo del primo".

Attenzione, il programma non cerca "stupidamente" la soluzione per tentativi, ma si basa su alcune interessanti considerazioni del lettore. Se ad esempio, il numero che stiamo cercando inizia per 4, la sua metà inizierà per 2. Ma essendo la sua metà pari al numero di partenza roteato di una cifra, la seconda cifra del numero cercato sarà parimenti un 2. Se la seconda cifra è un 2, la seconda cifra della sua metà è 1 che sarà, a sua volta, terza cifra del numero cercato. E così via, tenendo naturalmente conto anche dei riporti, fino a quando non concludiamo il ciclo, riottenendo il 4 di partenza, ovviamente con riporto nullo. Proviamo a fare un "giro". Troveremo il numero tale che bla.bla.bla otteniamo un numero che è un quinto del numero di partenza. Questo perché per il 5 esiste una soluzione molto piccola, appena sei cifre (trovata per caso dal programma modificato)

Iniziamo da 7, che diviso 5 fa 1 con riporto di 2. Annotiamo 7 come prima cifra del nostro numero, 1 come seconda cifra dato che è la prima cifra del numero roteato. Abbiamo ora 1 con riporto di 2, che fa 21. Diviso 5 fa 4 con riporto di 1. 4 sarà la terza cifra. Ora dobbiamo dividere 14 per 5, che fa 2 con riporto di 4, (annotiamo in 2), poi 42 che dà 8 con riporto di 2, 28 che ri restituisce un 5 con riporto di 3, infine 35 conclude il nostro ciclo dando 7 con riporto di 0 da cui eravamo partiti. Il numero cercato è:

714285

che diviso per 5 fa appunto:

142857

rotazione del primo.

Con lo stesso procedimento si ottengono le soluzioni del quesito da cui siamo partiti, dividendo ogni volta per 2.

Da notare che immediatamente troviamo altre infinite soluzioni del giochino: se noi concateniamo quante volte vogliamo un numero-soluzione, otterremo altre soluzioni. Ad esempio, essendo 714285 una soluzione lo sarà anche 714285714285 e così via. Amighi e Mac-chinisti, si potranno ora sbizzarrire a trovare tutte le soluzioni più interessanti. Gli altri, per esercizio, proveranno a tradurre il programmino da Basic strutturato al Basic della loro macchina. A tutti, comunque, buon divertimento.