20. Lotti scaduti

[Toadino2]

In un grande magazzino, un cliente ha segnalato un prodotto in cattive condizioni. Dunque il personale si muove per ritirare dagli scaffali l'intero lotto di prodotti; tuttavia non è stato segnalato il numero esatto del lotto, ma il personale è comunque riuscito a trovare venti lotti che dovrebbero racchiudere quello scadente.
Presupponendo che il lotto scadente sia uno solo, che si abbia a disposizione una bilancia ad un piatto, e sapendo che ogni lotto è racchiuso in un'unica scatola contenente cento prodotti, ognuno pesante 100g, mentre quelli scadenti pesano 15 grammi di meno, come si può ritrovare il lotto incriminato?

Nota: questo quesito non è tratto dalle Olimpiadi, ma da un libro. Spero vada bene comunque

[cip999]

Intendi il numero minimo di pesate necessarie? E si possono pesare solo le scatole con i lotti o anche i singoli prodotti?

[Federico II]

Se è come ho capito io, cioè che si pesano i lotti interi e che va trovato il minimo numero di pesate necessarie per trovare il lotto contenente il prodotto scaduto, la soluzione è:

Testo nascosto:

$5$

Testo nascosto:

Si pesano all'inizio $10$ lotti. Se il peso è $100\ kg$, il lotto cattivo sta tra gli altri, altrimenti sta tra quelli pesati. Si scartano a questo punto i lotti ormai noti come buoni e si ripete il procedimento con $5$ lotti sulla bilancia vedendo se il peso è $50\ kg$. Resteranno dopo due pesate $5$ lotti, ripetendo il procedimento con $3$ ne restano $2$ o $3$ (nel caso peggiore $3$), poi lo si fa con $2$ e nel caso peggiore ne restano $2$, e con la quinta pesata è facile determinare quale dei due è incriminato (deve pesare meno di $10\ kg$). Non è possibile fare di meglio perché ogni pesata dà un'informazione del tipo "il lotto cattivo è tra quelli sulla bilancia" o "il lotto cattivo non è tra quelli sulla bilancia", e in totale con $4$ pesate abbiamo $2^4=16$ combinazioni possibili di informazioni, e dal momento che $16<20$ e non è possibile che ogni combinazione porti al più ad una scelta per il lotto incriminato (si può usare pigeonhole considerando come gabbie le combianzioni e come piccioni i lotti), che non può quindi essere sempre determinato univocamente. Pertanto $5$ pesate sono necessarie e sufficienti. In generale con $n$ lotti il minimo numero di pesate è $\log_2 n$, arrotondando il valore per eccesso quando non è un intero.

[Toadino2]

No, scusa hai una sola pesata...
Ma puoi estrarre i prodotti dalle scatole...

Mi sono espresso male io...

[Federico II]

Ancora non capisco... con una pesata puoi ottenere due diverse informazioni: "il prodotto scaduto è tra questi" oppure "il prodotto scaduto non è tra questi". Anche se puoi tirare fuori i prodotti se c'è un solo prodotto scaduto non puoi trovare il lotto a cui appartiene con una sola pesata. Se invece tutti i prodotti di un lotto (e solo quelli) sono scaduti, allora la soluzione è la seguente:

Testo nascosto:

Dopo aver numerato ogni lotto con un intero positivo da $1$ a $20$, poniamo sulla bilancia dei prodotti in modo che, per ogni $k\in\mathbb{N}$ tale che $1\leq k\leq20$, si pongano sulla bilancia esattamente $k$ prodotti, tutti del lotto $k$ (possiamo farlo perché $20<100$). In questo modo avremo un prodotto del lotto $1$, due del lotto $2$ e così via, fino a venti prodotti del lotto $20$. A questo punto osserviamo il peso totale. In totale abbiamo pesato $\sum_{i=1}^{20}{i}=\frac{20\cdot21}{2}=210$ prodotti, quindi se fossero tutti buoni peserebbero $210\cdot100\ g=21000\ g$. Ogni prodotto scaduto abbassa però il peso di $15\ g$, quindi il peso totale (in grammi) sarà della forma $21000-15n$, con $n\in\mathbb{N}$ tale che $1\leq n\leq20$, perché per ipotesi il lotto scaduto è uno e uno solo. Detto $P$ il peso in grammi fornito dalla bilancia, basta risolvere nell'incognita $n$ l'equazione $21000-15n=P$ per trovare il numero di prodotti scaduti pesati (per quanto detto prima il risultato dell'equazione sarà sempre un numero naturale compreso tra $1$ e $20$). Detto $x$ il risultato trovato, avremo che il lotto $x$ è quello scaduto, perché come detto all'inizio per ogni $1\leq k\leq20$ il lotto $k$ ha esattamente $k$ prodotti posti sulla bilancia.

[Toadino2]

È giusta puoi andare!