in Just for Fun, Maths

Gabriele Lami
Co-founder @ Elif Lab : www.eliflab.com

La tendenza ad affidare l’intelligenza personale all’intelligenza artificiale sembra essere pervasiva (almeno a parole).
In alcuni casi, però, risulta più economico e illuminante usare un po’ il vecchio e appesantito cervello biologico.

Di seguito espongo un semplice gioco/rompicapo e una strategia per vincere, la cui validità può essere dimostrata con un minimo di algebra.

L’origine di questo post è tutta da attribuire al bell’articolo The “88 Hats” puzzle su Vector, un giornale della ‘British APL Association” che dimostra la strategia vincente utilizzando il linguaggio Dyalog APL.

Per chi ha qualche rudimento di APL consiglio vivamente di leggere l’articolo, per gli altri consiglio di imparare un po’ di APL e di accettare il consiglio precedente.

Tenterò nelle prossime righe di “tradurre” l’articolo (la prima parte) in formule matematiche e in Python.

Il gioco

88 persone si siedono in cerchio.

Ognuna indossa un cappello con un numero da 0 a 87 (i numeri possono essere ripetuti).

Tutti possono vedere il numero attribuito alle altre persone ma non il proprio.

A ogni persona viene richiesto di scrivere, contemporaneamente agli altri giocatori, un numero da 0 a 87 su un foglio.

Se almeno una persona scrive il numero che corrisponde al numero del suo cappello tutti vincono, in caso contrario tutti perdono.

I giocatori si possono accordare rispetto all’utilizzo di una strategia ma durante il gioco non possono comunicarsi informazioni.

Esistono strategie vincenti?

Una strategia vincente

La risposta è affermativa.

Di seguito una strategia vincente che funziona non solo nel caso originale di 88 partecipanti ma per ogni numero.

Strategia:

  • Prima di giocare, a ogni persona si attribuisce un numero univoco da 0 a 87 (un indice);
  • la persona con l’indice “i” scrive il numero

dove

è la somma dei numeri che la persona i vede sui cappelli delle altre 87 persone, modulo n

con

il numero che la persona i-esima ha sul suo cappello.

Per esempio: se la persona 3 calcola che la somma dei cappelli degli altri giocatori è 95 scriverà (3 – 95) mod 88 = 84

Applicando questa strategia esiste almeno una persona t per cui

Questa strategia risulta sempre vincente.

Dimostrazione

Per la dimostrazione bisogna definire alcuni elementi:

numero del cappello i-esimo

numero scritto dall’ i-esima persona

= numero di persone (88 nel caso originale)

Dimostriamo che la persona con l’indice t

uguale alla somma di tutti i numeri sui cappelli modulo n, scriverà il numero che ha sul suo cappello.

t si può sommare e sottrarre la stessa quantità:

Usando la strategia indicata sopra possiamo scrivere:

Sapendo che

è la somma di tutti i numeri modulo n, tranne il numero sul cappello della persona t e che t è la somma totale, data l’ultima uguaglianza abbiamo inesorabilmente che

La persona t scrive quindi il numero che manca alla somma che vede per avere la somma di tutti i numeri sui cappelli. Scrive quindi il suo numero.

In Python

import random
n = 88
# lista di 88 numeri casuali
h = [random.randint(0, n) for i in range(n)]# associamo ad ogni persona un indice (tuple (i, h[i])):
id = list(enumerate(h))# vettore w che nel posto i-esimo contiene il numero scritto dalla persona i secondo la strategia
w = [ (i — sum([ v for j, v in id if j !=i ]))%n for i, _ in id]# la persona t
t = sum(h)%n# cappelli
print h
# numeri scelti
print w
# cappello e numero scritto dalla persona t
print t, h[t] , w[t], h[t] == w[t]