Soluzione all'enigma 38, proposto da Stefano P. l'11 aprile 2005

La cagnetta Twiggy ama le noci, ma non riesce a romperle, allora deve portarle al suo padrone affinché lui faccia questa operazione al suo posto. Tra il padrone e l'animale la regola del gioco è relativamente semplice.
Il padrone divide tutte le noci che Twiggy gli ha portato in due mucchietti uguali e ne mette da parte uno. Se così facendo resta una noce, questa è per Twiggy. Poi ripete l'operazione fino all'esaurimento delle noci. Per esempio, se Twiggy porta 1903 noci, i mucchietti successivi saranno di 951, 475, 237, 118, 59, 29, 14, 7, 3 e 1 noci e Twiggy avrà potuto mangiare 9 noci. Twiggy può portare al padrone al massimo 1998 noci e ne porta sempre almeno 1798. Quante noci deve portare al minimo Twiggy per poterne mangiare il più possibile?

Il numero ottimale di noci che la cagnetta deve portare è 1919, per un totale di 10 noci che si può mangiare lei. Come scoprirlo?

Beh... permettetemi prima una breve digressione su come si calcola la scrittura binaria di un numero in base 10 (uno dei modi per farlo...). Per esempio, vogliamo scrivere in base 2 il numero 123. Per farlo dividiamo 123 per 2, annotandoci il resto della divisione, poi dividiamo il quoziente ottenuto per 2, annotando nuovamente il resto e così via fino ad ottenere 0 come quoziente. I resti annotati, letti dall'ultimo al primo, rappresentano il numero in base 2. Quindi:

123  |  1
 61  |  1
 30  |  0
 15  |  1
  7  |  1
  3  |  1
  1  |  1
  0  |

(123)_10 = (1111011)_2

Come notate, il procedimento è esattamente quello che esegue il padrone di Twiggy per decidere quante noci assegnare all'animale, quindi il problema delle noci, tenuto conto che

(1998)_10 = (11111001110)_2
(1798)_10 = (11100000110)_2

può essere riscritto in questo modo: qual è il numero binario più piccolo compreso nell'intervallo qui sopra che massimizzi il numero di uni utilizzati nella sua scrittura? Beh... si vede subito che Twiggy non può mangiare 11 noci, perché il numero composto da 11 uni sarebbe troppo grande (maggiore di 1998), quindi deve esserci almeno uno zero (e di conseguenza 10 uni). Il problema, allora è scoprire dove mettere lo zero per ottenere un numero con 10 uni nella scrittura binaria e che sia il
più piccolo compreso nell'intervallo sopra. Con un po' di prove uno scopre che tale numero è:

(11101111111)_2 = (1919)_10