Caligola è famoso per avere eletto senatore un cavallo e per molte altre azioni non proprio edificanti. Permettetemi, allora di inserire una nefandezza di cui pochissimi (o nessuno) è a conoscenza. Una nefandezza che ha però permesso a uno schiavo di essere reso libero e ricoperto di denaro.

Il gioco perverso di Caligola consisteva nel far mettere in cerchio un certo numero (sempre diverso) di schiavi muniti di una corta spada. A partire dalla posizione 1 e andando in verso orario ogni schiavo uccideva quello che gli era accanto. In breve, 1 uccideva 2, 3 uccideva 4, e via dicendo. Finito il primo giro si continuava in modo che ogni schiavo ancora vivo uccidesse il primo che trovava in vita, girando sempre nello stesso verso. Alla fine ne rimaneva uno solo che, comunque, avrebbe partecipato a un nuovo giro di giostra...

Tuttavia, per farsi vedere magnanimo, Caligola dava sempre la possibilità allo schiavo sopravvissuto di scegliersi il posto nel cerchio del giro successivo (con numero di schiavi diverso, però, come già detto). Faceva anche sempre la stessa promessa, con un diabolico sorriso sul volto: "Chi riuscirà a salvarsi per almeno cinque volte consecutive sarà reso libero e lo riempirò di denaro in modo da poter fare una vita al pari dei più ricchi aristocratici romani".

Un bel giorno, un certo schiavo dagli occhi svegli e dalla mente brillante, dopo essersi intrufolato in una ben definita posizione la prima volta, non solo rimase in vita, ma le sue quattro scelte successive lo videro sempre vincitore. Caligola era malvagio, ma non poteva mancare alla parola data e lo schiavo ottenne quanto gli era stato promesso. Anzi, Caligola lo volle senatore e gli venne conferito il titolo di grande matematico di corte. Molti si convinsero che lo schiavo fosse protetto dagli dei, forse da Giove stesso e nessuno osò mai mancargli di rispetto.

Ovviamente, Giove non c'entrava per niente, ma lo schiavo era riuscito a calcolare in modo generale la posizione che l'avrebbe salvato conoscendo solo il numero degli schiavi presenti nella giostra infame e chi sarebbe stato il primo a uccidere il compagno a fianco (il numero 1, insomma).

Non pretendiamo una dimostrazione precisa e dettagliata del perché e del percome, ma solo di stabilire, in qualche modo, anche empirico, la legge che bisogna seguire per uscire sicuramente incolumi. Ah... dimenticavo... lo schiavo si chiamava Astarium...

Come di consueto, ognuno può provare a dare la propria risposta nei commenti prima di continuare la lettura dell'articolo.

Forza, divertitevi e fermatevi al livello che volete!

 

***************************************************************************

 

Soluzione decimale e binaria

Esistono vari approcci al problema, alcuni molto complicati. Noi riportiamo il più semplice che può essere rappresentato in modo ancora più elegante attraverso i numeri binari.

Qualche considerazione preliminare

Si parte sempre dal numero 1

Qualsiasi sia il numero n degli schiavi i primi a essere uccisi sono quelli che occupano una posizione pari. Se, ad esempio, il numero totale è 33, saranno uccisi al primo giro tutti i pari da 2 a 32. Ne segue che già da subito possiamo dire che il sopravvissuto DEVE occupare una posizione dispari.

Possiamo però anche concludere subito che se n è dispari il numero 1 viene sicuramente ucciso al completamento del primo giro. Infatti, avendo eliminato tutti i pari, l’ultimo sopravissuto del primo giro deve essere dispari, ossia l’ultimo prima del numero 1. Ne segue che il primo ad essere ucciso al secondo giro è proprio il numero 1.

Se, invece, n è un numero pari, l’ultimo a essere ucciso al primo giro si trova  subito prima del numero 1, che quindi si salva e ricomincia a essere il primo ad uccidere. Se la stessa cosa capita al secondo, al terzo, al quarto giro, ecc., il numero 1 si salva sempre. Ne segue che l’unico modo affinché il sopravvissuto sia il numero 1 è che n sia una potenza di 2. Infatti, in tal caso, il dimezzamento degli schiavi porta sempre a un numero pari con la conseguente salvezza di 1.

In altre parole,

per n = 2⁰, 2¹, 2², 2³, 2⁴, … 2^m  lo schiavo che si salva è sempre il numero 1

Un po’ più complicato è il caso di n dispari o di n pari ma non è potenza di 2. In entrambi i casi, prima o poi, sicuramente il numero 1 viene ucciso. O, immediatamente al primo giro, per quanto detto all’inizio (se è un numero dispari) o dopo un certo numero di giri se n è pari ma non è potenza di 2:  la divisione per 2, infatti, dà, prima o poi, un numero dispari e si ricade nel caso precedente. E’ molto importante capire quando capita questa situazione e quanti giri possono ancora compiersi.

Sintetizzando... il sopravvissuto è sicuramente un numero dispari e per due n consecutivi (non potenze di due) esso deve passare da un numero dispari a quello successivo (ricordiamo infatti che il sopravvissuto NON può mai occupare una posizione pari).

Proviamo a pensare a due numeri entrambi potenze di 2, ad esempio 8 (2³) e 16 (2⁴) e vediamo cosa succede per i numeri intermedi.

Per 8 il sopravvissuto è sicuramente 1. Per 9 sarà il numero dispari successivo, ossia 3, per 10 sarà il 5, e così via…. fino a 15 a cui corrisponderà proprio il 15. La faccenda è intuitiva dato che il numero dopo è 16 e deve avere soluzione uguale a 1. In parole molto semplici cosa succede? Per n potenza di 2 abbiamo come sopravvissuto il numero 1 e poi segue la lista di tutti i dispari successivi fino a che il numero n coincide con il sopravvissuto. Sicuramente, subito dopo siamo obbligati a trovare come n una nuova potenza di 2 e la sequenza dei sopravvissuti riparte da 1 fino al valore dispari precedente la nuova potenza di 2.

Concludendo

Il tutto si riassume con una semplice formula ricorrente:

se n = 2^m + k

(Questa relazione ci dice che k non è altro che la differenza tra l'ultima potenza di due e il numero di schiavi)

e se 0 ≤ k < 2^m

(Ovviamente k può anche essere zero (n = 2^m, sopravvissuto il numero 1), ma non uguale a una potenza di due, se no si ricade nel caso di una potenza di 2 (2^m + 2^m = 2 · 2^m = 2^m+1))

allora il sopravvissuto sop(n) è dato da

sop(n) = 2k + 1               ....(1)

Si può anche dimostrare per induzione, ma basta provarne la validità per 8 (2³), per 9, per 10, 11 e 12,  ecc.

sop(8) = 2·0 + 1 = 1

sop(9) = 2·1 + 1 = 3

sop(10) = 2·2 + 1 = 5

sop(11) = 2·3 + 1 = 7

sop(12) = 2·4 + 1 = 9

……

Scriviamo i sopravvissuti per i primi 16 numeri, ma è banale andare avanti finché si vuole..

n = 1  2  3  4  5  6  7  8  9  10  11 12  13  14  15  16 …

sop(n) = 1  1  3  1  3  5  7  1  3    5    7   9  11  13  15    1 …

 

Astarium = Binario

Il metodo sicuramente più elegante è però, come già detto, quello che fa uso dei numeri binari. In fondo, siamo parlando di potenze di 2, proprio quelle che permettono di scrivere un qualsiasi numero a base 10 (decimale) in base 2 (binario)

Per far ciò richiamiamo la rappresentazione binaria dei numeri, proprio quella che usa un qualsiasi computer. In pratica, invece di usare come base il numero dieci e scrivere un numero sommando le unità (10⁰), le decine (10¹), le centinaia (10²), le migliaia (10³), ecc., prendiamo come base il numero 2 e sommiamo i vari multipli di 2, ossia 2⁰, 2¹, 2², 2³, ecc.

Prendiamo ad esempio il numero 142 (scritto in decimali). Esso è la somma di 2 unità più 4 decine e 1 centinaia, ossia:

142 = 2 + 40 + 100 = 2·10⁰ + 4·10¹ + 1·10²

Scriviamolo, adesso, cercando di sommare i multipli di 2...

142 = 128 + 8 + 4 + 2 = 1 ·2⁷ + 1· 2³ + 1· 2² + 1· 2¹  

Dobbiamo però tenere conto dei termini mancanti, ossia delle potenze di 2 che non sono presenti e che si considerano  moltiplicate per 0.

142 = 128 + 8 + 4 + 2 = 1· 2⁷ + 0 ·2⁶ + 0· 2⁵ + 0· 2⁴ + 1· 2³ + 1· 2² + 1· 2¹ + 0· 2⁰

Il che vuole anche dire scrivere: 10001110

che non è altro che 142 scritto in binario.

Infatti quella serie di 0 e di 1 ci dice che vi è 1 potenza settima di 2, 0 potenze seste, quinte e quarte, 1 potenza terza, 1 potenza seconda, 1 potenza "prima" e 0 potenze "zero". Si potrebbe anche scrivere

 

Consideriamo adesso il numero n degli schiavi secondo la relazione ricavata precedentemente:

n = 2^m + k

il "resto" k può sempre essere scritto come una somma di potenze di 2, ricordando che 2⁰ = 1

Vediamolo direttamente utilizzando il numero 41 (con k = 9)

41 = 32 + 8 + 1 = 1 · 2⁵ + 0· 2⁴ + 1· 2³ + 0· 2² + 0·2¹ + 1· 2⁰

scritto in binario diventa:

n =41 = 101001            .... (2)

Qual è la soluzione che possiamo ricavare dalla (1)?

sop(41) = 2k + 1 = 2· 9 + 1 = 19

Prendiamo, adesso, la scrittura in binario di k = 9

9 = 1· 2³ + 0· 2² + 0· 2¹ + 1 · 2⁰

1001

sommiamolo a se stesso (moltiplichiamolo per 2)

1001  +

1001

-------

10010   (ricordando che 1 + 1 = 0 con il riporto di 1, dato che siamo in base binaria: 1  = 2⁰, 1 + 1 = 2⁰ + 2⁰ = 2¹)

2k in binario vale, quindi:

10010

aggiungiamo 1 = 2⁰

e otteniamo

sop(41) = 10011                .... (3)

 

che sarebbe il numero del sopravvissuto, ossia

sop(41) = 1·2⁴ + 0·2³ + 0·2² + 1·2¹ + 1·2⁰

sop(41) = 16  + 0  + 0 + 2 + 1 = 19

Come dovevamo aspettarci. Sia utilizzando i decimali che i binari il risultato deve essere lo stesso!

I primi saranno gli ultimi...

Tuttavia, possiamo notare un fatto estremamente interessante... Guardiamo nuovamente la forma binaria di n = 41

41 = 101001

e quella del  numero del sopravvissuto (19)

19 = 10011

Come una specie di magia, basta prendere il primo 1 di 41 in binario e portarlo alla fine e si ottiene proprio il numero del sopravvissuto.

Meraviglia delle meraviglie! In realtà, non poteva che essere così ragionando sul fatto che il numero totale ha una potenza di 2 che viene scartata nel calcolo del sopravvissuto, a cui invece viene aggiunta una unità...

Volessimo calcolare il sopravvissuto di 142?

142 = 10001110

sop(142) = 11101

16 + 8 + 4 + 0 + 1 = 29

Controlliamo se è giusto?

142 = 128 + 14

sop(142) = 2· 14 + 1 = 29

Come volevasi dimostrare...

Non sappiamo se al tempo di Caligola lo schiavo-matematico Astarium usasse già i numeri binari o si limitasse a quelli decimali. La cosa migliore è andare a leggere cosa racconta a riguardo il grande storico Caius Mauritius Phantasius...

 

Le pietre sono pensieri

(di Murizio Barnardi)

Erano giorni di grande caldo, una delle estati più calde degli ultimi venti anni, quella del 39.

Ma Astarium non sentiva quasi il calore dei raggi infuocati che piovevano nella grande arena, sulla folla di spettatori, che vociavano e incitavano i combattenti.

I Giochi di Caligola erano in pieno svolgimento e quella giornata di sole sarebbe probabilmente stata l'ultima della vita di Astarium, se non avesse trovato qualche via di uscita da quella situazione incresciosa.

Il gioco del Cerchio infame!

Un gruppo di schiavi costretti a disporsi in cerchio. Il primo deve uccidere il suo vicino, il terzo deve uccidere il quarto e così via , nel senso in cui gira il Sole. Poi ricomincia il giro finché solo uno resta vivo. Già, solo uno resta vivo, ma chi? Dipende dal numero di persone che formano il circolo, pensò Astarium. E dove si trovava quel fortunato nella disposizione iniziale, che posto occupava? Perché, era certo, che se fosse stato in un posto diverso sarebbe morto.

Si frugò in tasca per cercare il suo amuleto: lo zampino di coniglio che gli aveva regalato la zia Woller, e che gli aveva sempre portato fortuna.

Ma si ritrovò tra le dita gli astragali di Flaminia, la sua fidanzata. Cinque sassi bianchi tondeggianti che la ragazza portava sempre con sé per giocare con le amiche lanciandoli e afferrandoli al volo.

Chissà quando glieli aveva infilati in tasca, forse nel momento in cui si erano lasciati, quando i pretoriani erano venuti a prenderlo per portarlo all'arena con gli altri schiavi.

Astarium depose in terra i cinque sassolino in cerchio.

Se , invece di cinque, fossero solo quattro... Pensò: il primo uccide il secondo, il terzo uccide il quarto, Poi tocca ancora al primo che uccide il terzo. Resta vivo il primo. Due giri, ad ogni ciclo si dimezza il numero ma il primo resta il primo. Anche se fossero otto, dopo il primo giro diventerebbero quattro e sappiamo che, in quattro, il primo si salva.

E' chiaro che tutti quelli in posizione pari, il secondo , il quarto eccetera vengono uccisi subito al primo giro, Assolutamente da evitare. Ma anche i dispari prima o poi vengono uccisi, Solo il primo si salva. Quindi se il cerchio è composto da 2 , 4 , 8, insomma un numero che è sempre il doppio del doppio del doppio, eccetera si salva il primo. Devo assolutamente essere al primo posto.

Ma se invece ci sono più sassi di 2 o di 4 o di 8 eccetera? Per esempio, uno in più, come questi cinque astragali di Flaminia?

Dunque... il primo posto non va più bene, perché viene fatto fuori subito, alla fine del primo giro, dal numero 5.

Allora, forse , meglio il secondo posto... Ma no! Per Giove! Cosa dico? Il secondo posto non va per niente bene: è un posto pari, addirittura il primo posto pari, la prima vittima sicura. Allora meglio spostarsi ancora di un posto: vado al numero 3. Sì, il posto tre è un dispari ed è il primo dispari dopo il numero uno, che è diventato pericoloso. In pratica il posto tre ha ereditato^* le prerogative che aveva prima il numero uno, perché dopo che il 5 ha eliminato il numero 1, il nuovo cerchio è composto da un numero di individui che è un numero raddoppiante (sono rimasti in 2) e in questo cerchio il primo posto è occupato dal numero 3. Si salverà, sono sicuro che si salverà.

Astarium lanciò uno sguardo ai sassi e mentalmente fece uccidere il sasso 2 dal sasso 1, il sasso 4 dal sasso 3 il sasso 1 dal sasso 5. Proseguì con il secondo giro, toccava al sasso 3 che, senza fare complimenti, uccise sasso 5. Ecco, era rimasto solo il sasso 3! Proprio come aveva immaginato.

Quindi la regola era semplice: se nel gruppo c'era uno in più, in aggiunta a uno di quei numeri “raddoppianti”: 2, 4, 8, 16 eccetera, bastava spostarsi di due posti , evitando in questo modo la posizione pari, ed eri salvo!

Astarium quasi non ci credeva. Volle riprovare a fare il ragionamento. Se nel gruppo fossero stati in 6... come dire 2 in più di 4 (che era il numero raddoppiante di riferimento), doveva spostarsi nel senso di circolazione di due posti per 2 volte, andando ad occupare quindi il posto numero 5.

Provò lo schema e constatò che il 5 era davvero il posto giusto.

Al centro della arena il “gioco” stava iniziando con il primo gruppo di schiavi. Li contò: 17.

Diciassette è come dire un numero raddoppiante, che è 16, più 1. Quindi si salverà quello che ora si trova nella posizione 3. Se fossi lì in mezzo dovrei mettermi al posto numero 3. Per Giove! Non è difficile.

Quando lo spinsero nel nuovo gruppo, in mezzo agli altri, ebbe appena il tempo di fare i conti.

I suoi sventurati compagni erano 40, lui era il quarantunesimo.

Strofinò le dita sui cinque sassolini che aveva rimesso in tasca mentre contava... 41 supera il numero raddoppiante 32 di 9 unità, basta che mi metta diciotto posti dopo il primo, cioè nella posizione 19.

E così fece.

* Nota

In un gruppo di tipo 2ⁿ + 1 , alla fine del primo giro, viene eliminato il posto 1. Restano a questo punto esattamente 2ⁿ + 1 - ( 2^n-1 + 1) = 2^n-1 giocatori nel cerchio, per cui si ricade nel caso studiato per primo: un gruppo di giocatori il cui numero è una potenza del 2.

Nell'esempio del gruppo di 5 giocatori, dopo il primo ciclo, il numero 3 va ad occupare il primo posto nel nuovo cerchio, in uno schema che lo vede destinato a sopravvivere. In questo senso il numero 3 “eredita” il privilegio della prima posizione.

 

Ecco una sintesi del ragionamento dello schiavo Astarium (per gli amici... Binario)

Prima osservazione:   sopravvive sempre colui che, dopo di sé, vede  (2ⁿ -1 )  rivali, in altre parole è il primo di un cerchio composto da   2ⁿ  giocatori, compreso lui.

Seconda osservazione:  se i giocatori sono in numero N, superiore a  2ⁿ  ma inferiore a  2ⁿ⁺¹    , allora, eliminando i primi  N  - 2ⁿ  ,   si ridurrà il loro numero  a 2ⁿ  e  si arriverà ad individuare la posizione di salvezza.

Terza osservazione:  per eliminare le prime  N  - 2ⁿ    vittime  occorre che ciascuna di esse sia preceduta dal suo "esecutore". Conseguentemente la posizione sicura (quella in cui sistemarsi inizialmente) si sposterà in avanti, dalla numero 1, di  2(N  - 2ⁿ) posti.

Conclusione

Dato il numero N di partecipanti, si sottrae ad esso il valore  2ⁿ   che lo precede , si raddoppia il risultato e si somma 1 per avere la posizione di salvezza.

 

Se vi è piaciuto questo NON-QUIZ, ne trovate altri QUI