Problema dei laghi di ghiaccio

[marcob90]

Ciao! Mi sono imbattuto nel seguente enigma matematico durante un test.

Ci sono 2 laghi ghiacciati di forma quadrata esattamente identici.
Si vuole conoscere con esattezza quanti kilogrammi sono necessari per rompere le lastre di ghiaccio.
A questo scopo, si hanno a disposizione blocchi da 1 kg ciascuno che si possono porre al centro dei 2 laghi.
Si sa in partenza che la massa minima che provochera' la rottura delle lastre di ghiaccio e' compresa tra 1kg e 144kg estremi compresi ed e' un numero intero.

Per risolvere il problema, si puo' pensare di aggiungere un blocco da 1 kg alla volta su uno dei due laghi fino alla rottura dello stesso. A questo punto si sa con certezza che la massa cercata e' quella posta fino al punto di rottura. Se pero' la massa cercata fosse effettivamente 144, nel caso peggiore dovremmo effettuare 144 passi per trovare il risultato.
Come possiamo ottimizzare l'operazione? Cambiando il numero di blocchi posizionati per passo e sfruttando il secondo lago.

Ad esempio, decido di porre 4 blocchi alla volta ad ogni passo sul lago 1. A un certo punto il lago si rompera', diciamo dopo aver posto 64 kg. Per trovare l'esatta massa di rottura, basta porre 60kg sul lago 2 (cioe' la massa posta sul lago 1 al passo precedente la rottura) e successivamente un blocco alla volta fino alla rottura del lago 2 (cioe' 61, 62 o 63 kg).
Nel caso peggiore in cui la massa e' pari a 144kg, il numero di passi necessari per conoscere la risposta e' $ 144/4 + 3 = 39$.

Ci si puo' chiedere quindi quale sia il numero di blocchi ottimo per passo, affinche' il numero di passi necessari per conoscere la risposta sia minimo. Detto s il numero di blocchi per passo e $\omega$ il numero di passi totali, il caso peggiore corrisponde a:

$ 144/s + s -1 = \omega $

Derivando per s e ponendo uguale a zero, si ottiene:

$ (d\omega)/(ds) = -144/s^2 + 1 = 0 $

Da cui si trova facilmente che s = 12. Questo e' l'ottimo, per cui $\omega = 23.$

A questo punto ci si domanda ancora: e' possibile effettuare un'ulteriore ottimizzazione dicendo che il numero di blocchi posti sul lago 1 per passo s non e' un numero costante? Cioe' per esempio al passo 1 si pongono 2kg, al passo 2 4kg eccetera..

Come trovare la soluzione ottima?

[Vincent46]

Testo nascosto, fai click qui per vederlo

Si potrebbe cominciare ponendo 17 kili, poi 16, eccetera. Così al 13° passo si saranno posti 143 kg, e al 14° si saranno posti tutti i 144 kg. Alla peggio ci servono 17 tentativi.

Per fare meglio di così bisognerebbe porre, alla prima posa, al più 16 kili (se ne metto di più, nel caso peggiore mi serviranno comunque almeno 17 tentativi). Ad ogni posa successiva bisognerebbe scendere di almeno un kilo, per lo stesso motivo: al passo successivo dovrei metterne al più 15, poi al più 14, eccetera.
D'altronde questo procedimento non va bene perché 16+15+...+2+1=136, quindi non copro tutti i 144 kili.

edit: messo in spoiler

[axpgn]

@Vincent46

Testo nascosto, fai click qui per vederlo

Bella soluzione, molto furba.
Pensavo fosse impossibile perché ragionavo "in avanti" ma così facendo "esplodevano" i passaggi mentre andando "all'indietro" rimangono costanti.