Vecchie bilance
Vecchie bilance
Avendo a disposizione una bilancia a due piatti, qual e' il minor numero di pesetti necessario per poter pesare tutti gli oggetti di 1, 2, 3, ... 40 grammi?
La generalizzazione è facile...
Dato un numero $ $n $ qual'è il minor numero di naturali con cui posso scrivere tutti i numeri da $ $1 $ a $ $n $ come somma di questi?
Il numero minimo è il più piccolo naturale $ $m $ tale che $ $2^m-1\geq n $
(Questa soluzione presuppone che i nostri pesetti si possano mettere solo su un piatto della bilancia)
Dato un numero $ $n $ qual'è il minor numero di naturali con cui posso scrivere tutti i numeri da $ $1 $ a $ $n $ come somma di questi?
Il numero minimo è il più piccolo naturale $ $m $ tale che $ $2^m-1\geq n $
(Questa soluzione presuppone che i nostri pesetti si possano mettere solo su un piatto della bilancia)
Ultima modifica di Zok il 25 apr 2007, 09:54, modificato 1 volta in totale.
a me vengo 4 pesi per misurare da 1 a 40: 1,3,9,27
ogni nuovo peso deve essere pari al doppio della somma dei precedenti piu' 1:
coi primi n pesetti riesci a pesare da 1 a $ ~T=\sum p_i $. Ergo mettendo sull'altro piatto un peso da $ ~2T+1 $ puoi pesare pesi da $ ~T+1 $ a $ ~2T $; $ ~2T+1 $ ce l'hai, e poi spostando di nuovo il peso piu' grosso misuri da $ ~2T+2 $ a $ ~3T+1 $.
in pratica l'n-esimo peso e' pari a $ ~3^{n-1} $
ogni nuovo peso deve essere pari al doppio della somma dei precedenti piu' 1:
coi primi n pesetti riesci a pesare da 1 a $ ~T=\sum p_i $. Ergo mettendo sull'altro piatto un peso da $ ~2T+1 $ puoi pesare pesi da $ ~T+1 $ a $ ~2T $; $ ~2T+1 $ ce l'hai, e poi spostando di nuovo il peso piu' grosso misuri da $ ~2T+2 $ a $ ~3T+1 $.
in pratica l'n-esimo peso e' pari a $ ~3^{n-1} $
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
-
- Messaggi: 145
- Iscritto il: 21 mag 2006, 00:18
- Contatta:
Partiamo dal fatto che ogni numero $ ~n $ si può rappresentare in un solo modo in base tre come:
$ \displaystyle n = c_s 3^s + c_{s-1} 3^{s-1} + \ldots + c_0 = \sum\limits_{j=0}^s c_j 3^j $ dove i $ c_j $ sono 0, 1 o 2.
Ora, supponiamo che per un certo $ ~j=k $ sia $ c_k = 2 $. Allora si ha $ c_k3^k = 2 \cdot 3^k = (3-1)3^k = 3 \cdot 3^k - 1 \cdot 3^k = 1 \cdot 3^{k+1} -1 \cdot 3^k $. Da cui possiamo concludere che ogni numero ha un'unica rappresentazione come:
$ n = \sum\limits_{j=0}^s c_j 3^j $ dove i $ c_j $ sono -1, 0 o 1. Questo risultato, applicato al nostro caso, indica che, se possiamo mettere i pesi su entrambi i piatti della bilancia, basta un solo peso per ogni potenza di tre che compare nella rappresentazione in "base tre modificata".
Nello specifico, $ ~40 = 1 + 3 + 9 + 27 = 1111_3 $, quindi bastano quattro pesi.
$ \displaystyle n = c_s 3^s + c_{s-1} 3^{s-1} + \ldots + c_0 = \sum\limits_{j=0}^s c_j 3^j $ dove i $ c_j $ sono 0, 1 o 2.
Ora, supponiamo che per un certo $ ~j=k $ sia $ c_k = 2 $. Allora si ha $ c_k3^k = 2 \cdot 3^k = (3-1)3^k = 3 \cdot 3^k - 1 \cdot 3^k = 1 \cdot 3^{k+1} -1 \cdot 3^k $. Da cui possiamo concludere che ogni numero ha un'unica rappresentazione come:
$ n = \sum\limits_{j=0}^s c_j 3^j $ dove i $ c_j $ sono -1, 0 o 1. Questo risultato, applicato al nostro caso, indica che, se possiamo mettere i pesi su entrambi i piatti della bilancia, basta un solo peso per ogni potenza di tre che compare nella rappresentazione in "base tre modificata".
Nello specifico, $ ~40 = 1 + 3 + 9 + 27 = 1111_3 $, quindi bastano quattro pesi.