Vecchie bilance

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Vecchie bilance

Messaggio da Hammond »

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?
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

6? cmq..provate a generalizzare per 1 a n..
Zok
Messaggi: 140
Iscritto il: 01 gen 1970, 01:00
Località: Cambridge - Verona

Messaggio da Zok »

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)
Ultima modifica di Zok il 25 apr 2007, 09:54, modificato 1 volta in totale.
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

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} $
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
TADW_Elessar
Messaggi: 145
Iscritto il: 21 mag 2006, 00:18
Contatta:

Messaggio da TADW_Elessar »

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.
Rispondi