E giochiamo...

Come promesso trenta giorni orsono, questo mese appunti di informatica ospiterà tra le sue pagine alcune lettere giunte in redazione dopo l'articolo di MC 61. In quella sede un lettore ci scriveva per contestare alcune affermazioni di un paio di numeri prima, concludendo la sua missiva proponendo un giochino a base di numeri. In tanti mesi di "Appunti" non s'era mai visto un solo lettore... Poi di botto... Ci hanno scritto in tanti, alcuni chiedendo ulteriori chiarimenti, altri chiedendo la soluzione del maledetto giochino, ma un sacco scrivendo la soluzione con tanto di dimostrazione di alcune "importanti proprietà".

Non siamo dunque nell'informatica pura, ma se i lettori di questa rubrica sono tanto numerofili occorre accontentarli. Pubblichiamo qui di seguito le lettere più interessanti (ahimè, alcune contenenti altri giochini...) aspettando di vedere come andrà a finire. Ragazzi, se volete una rubrica di giochini basta dirlo. Scriveteci.

Il disperato

Carissimo Andrea,

il motivo per cui ti scrivo ti farà forse sorridere, ma il fatto è che ti ho inviato queste quattro righe per chiederti di inviarmi l'indirizzo o se vuoi di inviare ciò che scrivo di seguito ad Antonio Cunei di Monfalcone e la ragione di una simile "scandalosa" richiesta è presto detta.

Sul numero 61 di MC, che anch'io ho acquistato alla stazione , dato che stavo andando all'università, ho avuto la malaugurata idea di leggere la lettera del suddetto e devo dire che fino a che arrivassi alla fine ho molto apprezzato. Ma ecco che questo se ne esce con quella incredibile serie di numeri e fidandomi sul fatto che la soluzione era tremendamente semplice mi getto a capofitto alla ricerca della soluzione abbandonando momentaneamente il libro di Analisi I, quello di Geometria e qualche centinaio di foglietti svolazzanti con tremendi appunti ed esercizi sparsi in modo caotico sulla mia scrivania.

Dopo i primi tentativi andati a vuoto mi accorgo che quel "momentaneamente" è diventato tutta la serata e parte della giornata di ieri e ancora oggi non ho trovato la soluzione.

Ma ecco che mi viene un'idea meravigiosa: perché non vendicarmi a mia volta proponendo un giochino al tanto "caro" Antonio ? Tanto più che mi viene in mente un problemino proprio carino che apparve qualche anno fa su Genius, e che allora risolsi in un modo oscenamente semplice. Il problemino sarebbe dunque il seguente:

TROVARE UN NUMERO TALE CHE SPOSTANDO LA PRIMA CIFRA DOPO L'ULTIMA SI OTTIENE UN NUMERO CHE è ESATTAMENTE LA METà DEL PRIMO

Come vedi, Andrea, si tratta di un problemino niente affatto difficile che credo interesserà il nostro Antonio, anche perché ha una soluzione, almeno quella che io ho trovato, anch'essa tremendamente semplice.

Concludo augurando a te, ma soprattutto a MC una lunga, anzi lunghissima, ma che dico, lunghissima lunga vita, ad una rivista che riesce sempre a mandarmi in orbita.

Scarfato Francesco - Gragnano (NA)

Il Computer

Prima di proseguire con le lettere occorre avvertire i lettori di non impazzire più di tanto circa la soluzione del quesito. Secondo me occorre insistere sul quel "oscenamente semplice" che fa davvero tanto pensare...

Da bravo informatico la prima cosa che ho fatto è stata di scrivere un programmino basic che cerchi da solo il numero in questione. Sta ancora girando... siamo ormai a quota 41mila e non sputa fuori nulla. Secondo me c'è il trucco. Cattivo.

Il Professore

Caro De Prisco,

sono un lettore (da parecchi anni, ormai) della vostra interessante rivista, ho 35 anni, insegno Matematica e Fisica presso l'Istituto Magistrale di Fonni (NU).

Tante volte mi sono ripromesso di inviare un qualche contributo ma, sia per pigrizia, sia per il tempo suddiviso fra diversi campi di interesse, questa è la prima volta (ma non l'ultima, lo prometto) che vi scrivo.

L'occasione è molto banale: il quesito posto da un giovane e spiritoso lettore (A. Cunei di Monfalcone) che chiede di scoprire la regola di costruzione della stringa numerica A$(J+1) a partire da una stringa A$(J) (J=1,2,3...). Ebbene: se la j-ma stringa è del tipo

cioè è costituita da un numero k1 di cifre uguali a k2, da k3 cifre uguali a k4 ecc., a partire da sinistra allora la (J+1)-ma stringa sarà

k1k2k3k4...k2n-1 k2n

ed è dunque immediato, per il criterio di formazione, che qualunque sia il numero di caratteri della j-ma stringa A$(J+l) conterrà un numero pari di cifre. Inoltre, essendo in A$(J) k2i<>k2i+2 per qualunque i>Q si ha anche che la massima cifra che potrà comparire in A$(J+l) è 3. Infatti in ogni sottostringa di A$(J) del tipo

k2i-1 k2i k2i+l k2i+2

saranno uguali, al massimo, i caratteri numerici

k2i-1 k2i k2i+1

(In realtà una cifra> 3 potrà comparire nel caso che la stringa iniziale A$(l) contenga quella cifra oppure se è costituita da un numero di cifre uguali consecutive maggiore di 3).

Sebastiano Serra - Tresnuraghes (OR)

Il giorno dopo...

E' passata una intera notte, ma il 128 non ha trovato nulla (l'ultimo numero testato è: quattromilioniottocento-novantunomilacinquecentodiciotto). Mi rifiuto di proseguire oltre fino a nuova idea. Andrebbe comunque chiarito cosa si intende per prima cifra, per ultima e per "spostare". Io l'ho inteso in questo senso: prendiamo un numero, ad esempio 1234, spostando la prima cifra (l'uno) dopo l'ultima (quattro) otteniamo 2341. Ma per prima ed ultima cifra si potrebbe intendere il contrario quindi da 1234 passiamo a 4123. Proviamo dunque a modificare il programma.

Il Vichingo

Caro Andrea,

anche se ti conosco da molti anni attraverso le pagine di MC (precisamente dai vecchi tempi in cui ero un VIC-hingo, seguiti poi da quelli di SESSANTAAQUATTRista fino ai momenti attuali di AMIGO), questa è la prima volta che ti scrivo cogliendo l'occasione del tuo invito sul numero di marzo 1987 nella rubrica «Appunti di Informatica».

Innanzitutto per rassicurarti che almeno un terzo accanito lettore della tua rubrica c'è, ed inoltre per incitarti a continuare su questa strada dell'Informatica «SERIA».

Veniamo adesso al quesito (abbastanza facile devo dire) della generazione dei «numeroni» proposto dal lettore Antonio Cunei sul numero di MC detto più sopra:

[1] I numeri sono generati in base ai numeri precedenti con il sistema di figura a.

[2] Non potremmo mai avere una cifra maggiore di 3 presente nelle sequenze numeriche, questo perché per produrre un 4 dovremmo avere, nelle sequenza precedente almeno una serie AAAA (con A uguale a 1,2 o 3), ma questo è impossibile perché:

AAAA sarebbe generabile solamente da AA che però genera 2A (regola [1]).

Mi spiego con un esempio pratico che spero sia più chiaro: dalla coppia 11 otterremmo la quadrupla 1111 solo tramite una produzione del tipo UNa cifra 1 ed UNa cifra 1 (corrispondente a 1111), ma come abbiamo visto la regola ci dice che 11 -> 21 (cioè DUE cifre 1).

[3] Questo motivo inoltre fa anche in modo che il numero delle cifre di ogni sequenza generata sia sempre pari, infatti abbiamo visto (2 1) che al massimo in una sequenza avremmo una tripla AAA, quindi una sequenza potrà essere formata da singoli elementi (del tipo A), da coppie (AB) oppure da triple (AAA).

Allora le possibili produzioni saranno solamente quelle di figura b.

A questo punto è facile vedere che tutte le possibili produzioni generano sequenze formate da coppie, quindi sequenze con un numero di cifre PARI.

Con questo ho concluso il mio piccolo contributo al mondo dell'Informatica (spero che sia tale, il contributo non l'Informatica) e ti saluto sperando di poterti "risentire" presto.

Giovanni Beani - Marina di Pietrasanta (LU)

Lampadina!

Mentre il computer testardamente continua a cercare "nell'altro senso" (siamo già a quota 130mila), forse ho scoperto il tranello... secondo me ha a che fare con "un altro tipo di arimetica". Ma non posso aggiungere nient'altro per non togliervi il gusto di cercare anche voi. Non sono proprio sicuro che va bene... ma potrebbe.

Lo studente

Caro Andrea,

mi chiamo Corrado, concludo tra un paio di mesi la carriera di teen-ager e frequento il secondo anno della facoltà di Ingegneria, con sede in Arcavacata (CS).

Anzitutto, i miei più vivi complimenti per la tua rubrica, sempre «ricca di spunti per discussioni demolitrici» (vedi lettore di Monfalcone). Visto che per il momento non sono animato da propositi demolitori, è il mio turno di proporre un certo numero di «divertenti» rompicapo:

1) Se la metà di 5 fosse 3, che cosa sarebbe un terzo di 10?

2) Perché un assegno datato 1 aprile non è valuta legale?

3) Consideriamo il seguente gioco: in una griglia 10 x l0 sistemare i numeri da 1 a 100 consecutivamente, osservando le seguenti regole: a partire da qualsiasi posizione si può effettuare uno:

I) spostamento laterale (alto, basso, destra, sinistra), lasciando due caselle tra un cifra e l'altra

II) spostamento obliquo, lasciando una casella tra una cifra e l'altra

I contorni della griglia sono fittizi, nel senso che è possibile considerare i vari lati collegati fra di loro. Quante soluzioni si può stimare che esistano? (Cioè, non bisogna trovare tutte le soluzioni, ma, in base a certe supposizioni, stimare il numero di soluzioni).

In conclusione, (sperando che tu sia arrivato fin qui), oltre agli auguri di Buona Pasqua, un caloroso incoraggiamento a continuare questa rubrica, visto che almeno tre lettori ci sono.

Corrado Pecora - Vibo Valentia (CZ)

L'Informatico

Evviva! un altro lettore, e con questo fanno tre. Beh, andiamo con ordine. Intanto tanti saluti e una valanga di complimenti a tutta la redazione di MC, in particolare al destinatario della lettera e cioè Andrea (permetti che ti dia del tu?) ottimo curatore di "Appunti di Informatica" che è una tra le migliori cose che mi è capitato di leggere in questi ultimi tempi su certa stampa specializzata. Ma è ora di iniziare con gli argomenti che ho da sottoporti: sia nel numero 58 che nel numero 60 utilizzi la tecnica "diagonale" per dimostrare rispettivamente che la cardinalità dell'insieme dei sottoinsiemi di N è maggiore di quella di N e che l'insieme delle funzioni calcolate dal formalismo S non comprende tutte le funzioni da N in N.

La tecnica che usi non fa nessuna grinza nel primo caso mentre mi lascia un po' perplesso nel secondo. Infatti prendere gli elementi delle caselle della matrice secondo la diagonale di un quadrato vuol dire considerare come ipotesi iniziale che la matrice formata dai numeri naturali e dalle funzioni generate da S sia quadrata seppure infinita. Ma se si parte da questa considerazione e cioè cha la cardinalità di N e dell'insieme della funzioni generate da S è uguale, o meglio, equipotente, ls dimostrazione mi pare superflua, sapendo già che l'ordine di infinito dei sottoinsiemi di N e delle funzioni da N in N è maggiore dell'ordine di N.

Altra considerazione: data per vera l'ipotesi che funzioni generate da S non siano tutte le funzioni da N in N non potrebbe essere sufficiente comporre tutte le funzioni generate da S, in tutti i modi possibili ?

Otterremmo così ancora funzioni da N in N in un numero superiore allo stesso numero di tutte le funzioni da N in N, essendoci tra esse una valanga di doppioni, questo però non mi garantisce di ottenere tutte le possibili funzioni da N in N. Il mio cruccio è questo: come posso stabilire se il mio procedimento incrementa il numero delle funzioni generate da S fino ad ottenere tutte le funzioni da N in N ?

Mi sembra superfluo a questo punto chiederti di darmi una mano.

Enrico Giordani - Tricesimo (UD)

Fermi tutti!!!

Non facciamo confusione. Innanzitutto nel numero 60 io non ho dimostrato che l'insieme delle funzioni calcolate dal formalismo S non comprende tutte le funzioni da N in N (questo è stato dimostrato nel #58) ma "semplicemente" che se S s' un formalismo capace di calcolare solo funzioni totali certamente non sarà in grado di calcolarle tutte (le funzioni totali, attenzione). E la dimostrazione non fa un grinza. Il problema è proprio questo. Nella tua lettera parli di funzioni in generale, mentre occorre distinguere tra funzioni, funzioni calcolabili e funzioni calcolabili totali. Una funzione da N in N è un qualsiasi procedimento che preso un input restituisce un output (sempre nel campo dei naturali). Una funzione calcolabile in più può essere effettivamente calcolata ovvero esiste un formalismo effettivo in grado di valutarla per ogni input. Valutare non vuol dire pervenire ad un risultato in un tempo finito. Uno. Secondo, potrebbe anche essere che la funzione non sia definita affatto su alcuni valori di ingresso.

Infine le funzioni calcolabili totali si dicono tali in quanto valutandole, qualsiasi input gli passiamo ottenaimo un risultato in un tempo finito.

Per quanto riguarda l'operazione di composizione, essendo questa una operazione effettiva e calcolabile (prendo il risultato ottenuto valutando la prima funzione e lo "passo" alla seconda funzione) partendo da funzioni totali otterrò ancora funzioni totali (e quindi se il mio formalismo le calcolava tutte non ne aggiungo di nuove) se il formalismo calcola sia funzioni totali che parziali discorso analogo: il formalismo calcola tutte le funzioni calcolabili ? L'operazione di composizione è calcolabile ? risposta: non aggiungeremo una sola funzione non già contemplata. Tutto qui.