Leggenda di Nassir
Ciao a tutti, volevo chiarimenti sulla storiella di Nassir.
«Il re della Persia, il più potente mago del suo tempo, chiamò un famoso mago, Sissa Nassir, e gli disse: - Inventa per me un gioco bellissimo, che io lo possa giocare in ogni momento, e che sia imperituro. – Sissa inventò gli scacchi e li donò al re che tanto fu contento che gli disse: - Hai superato te stesso; chiedimi ordunque come ricompensa quel che vuoi e sarai accontentato. – E Sissa chiese, semplicemente, un po’ di riso. – Come un po’ di riso, - ribatté il re incredulo e divertito. – Chiedi di più, quel che vuoi. – Ma Sissa insisté, finché il re disse: - E sia, tutto il riso che vuoi ti sarà dato. – E chiamò il gra ciambellano, che era anche l’abacista di corte. Sissa chiese un granello di riso per la prima casella, due per la seconda, quattro per la terza, e così via sempre al raddoppio, fino a completare le caselle della scacchiera che lui stesso aveva inventato. Il re rise a crepapelle, pensando: Che idiota, poteva avere metà del mio regno! Ma il gran ciambellano sbiancò in volto. Si rivolse al re e disse: - Maestà, temo che non potremo accontentare Sissa Nassir. – Oh, e perché? – chiese il re allibito. E il ciambellano fece presente al re che anche raccogliendo tutto il riso di Persia e di Cina e di India e di ogni terra emersa, non solo il riso del raccolto attuale, ma, ma il passato e il futuro nei tempi dei tempi, mai e poi mai si sarebbe ottenuto tanto riso, il cui valore superava di miliardi di volte quello del reame stesso. E così finì che Sissa Nassir fu decapitato per alto tradimento reale e il ciambellano fu condannato a fare i conti di quanto riso era quello richiesto…»
Il mio prof ha detto che Sissa quindi richiede $2^64 - 1$ chicchi. Non ho capito perchè ne chiede $2^64 - 1$. E' una cosa banalissima ma mi manda in confusione. Non ne chiede semplicemente $2^64$ chicchi? Perchè quel $-1$?
Grazie in anticipo
«Il re della Persia, il più potente mago del suo tempo, chiamò un famoso mago, Sissa Nassir, e gli disse: - Inventa per me un gioco bellissimo, che io lo possa giocare in ogni momento, e che sia imperituro. – Sissa inventò gli scacchi e li donò al re che tanto fu contento che gli disse: - Hai superato te stesso; chiedimi ordunque come ricompensa quel che vuoi e sarai accontentato. – E Sissa chiese, semplicemente, un po’ di riso. – Come un po’ di riso, - ribatté il re incredulo e divertito. – Chiedi di più, quel che vuoi. – Ma Sissa insisté, finché il re disse: - E sia, tutto il riso che vuoi ti sarà dato. – E chiamò il gra ciambellano, che era anche l’abacista di corte. Sissa chiese un granello di riso per la prima casella, due per la seconda, quattro per la terza, e così via sempre al raddoppio, fino a completare le caselle della scacchiera che lui stesso aveva inventato. Il re rise a crepapelle, pensando: Che idiota, poteva avere metà del mio regno! Ma il gran ciambellano sbiancò in volto. Si rivolse al re e disse: - Maestà, temo che non potremo accontentare Sissa Nassir. – Oh, e perché? – chiese il re allibito. E il ciambellano fece presente al re che anche raccogliendo tutto il riso di Persia e di Cina e di India e di ogni terra emersa, non solo il riso del raccolto attuale, ma, ma il passato e il futuro nei tempi dei tempi, mai e poi mai si sarebbe ottenuto tanto riso, il cui valore superava di miliardi di volte quello del reame stesso. E così finì che Sissa Nassir fu decapitato per alto tradimento reale e il ciambellano fu condannato a fare i conti di quanto riso era quello richiesto…»
Il mio prof ha detto che Sissa quindi richiede $2^64 - 1$ chicchi. Non ho capito perchè ne chiede $2^64 - 1$. E' una cosa banalissima ma mi manda in confusione. Non ne chiede semplicemente $2^64$ chicchi? Perchè quel $-1$?
Grazie in anticipo
Risposte
Ne chiede $2^0$ per la prima casella, $2^1$ per la seconda, ..., $2^63$ per l'ultima.
Quindi in totale ne ha chiesti $\sum_{k=0}^{63}\ 2^k=2^{64}-1$.
Quindi in totale ne ha chiesti $\sum_{k=0}^{63}\ 2^k=2^{64}-1$.
Ok a logica ci sono, ma ci sono dei passaggi matematici per dimostrarlo?
Si tratta di una progressione geometrica di ragione $2$. Si può dimostrare anche così:
$S_n=1+q+q^2+...+q^(n-1)$ (la ragione è q)
$S_n*q=q+q^2+q^3+...+q^n$
Adesso sottrai membro a membro $S_n*q-S_n=q^n-1$, quindi $S_n(q-1)=q^n-1$, alla fine arrivi a $S_n=(q^n-1)/(q-1)$.
Nel tuo caso $q=2$, quindi $S_64=(2^64-1)/(2-1)=2^64-1$.
$S_n=1+q+q^2+...+q^(n-1)$ (la ragione è q)
$S_n*q=q+q^2+q^3+...+q^n$
Adesso sottrai membro a membro $S_n*q-S_n=q^n-1$, quindi $S_n(q-1)=q^n-1$, alla fine arrivi a $S_n=(q^n-1)/(q-1)$.
Nel tuo caso $q=2$, quindi $S_64=(2^64-1)/(2-1)=2^64-1$.
Come dice @anonymous_c5d2a1 
Altrimenti puoi fare un'osservazione intuitiva carina.
Il numero $\sum_{k=0}^n 2^k$, se scritto in rappresentazione binaria, è ovviamente il numero \(\underbrace{111...1}_{n+1\ volte}\), cioè \(1\underbrace{000...0}_{n+1\ volte}-1\). Scrivendolo in rappresentazione decimale diventa $2^{n+1}-1$.
Nel tuo caso $n=63$ quindi $\sum_{k=0}^{63} 2^k=2^{64}-1$
Altrimenti puoi fare un'osservazione intuitiva carina.
Il numero $\sum_{k=0}^n 2^k$, se scritto in rappresentazione binaria, è ovviamente il numero \(\underbrace{111...1}_{n+1\ volte}\), cioè \(1\underbrace{000...0}_{n+1\ volte}-1\). Scrivendolo in rappresentazione decimale diventa $2^{n+1}-1$.
Nel tuo caso $n=63$ quindi $\sum_{k=0}^{63} 2^k=2^{64}-1$
Grazie mille ad entrambi 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo