Newsgroup: it.hobby.enigmi
Titolo: [MAT] La tavoletta di cioccolata

Abbiamo una classica tavoletta di cioccolato di, diciamo, N "righe" e M "colonne" per un totale di NxM scacchi di cioccolato.
 
Vogliamo separare tra loro tutti gli NxM scacchi procedendo con l'usuale metodo che prevede di dividere una tavoletta di cioccolato axb in due parti lungo una riga o una colonna qualsiasi (quindi con tagli lineari "da una parte all'altra") e procedendo poi con le tavolette così ottenute in maniera ricorsiva fino a quando non ho tutti scacchi singoli (o, se preferite, tavolette 1x1...).
 
Di quanto passaggi ho bisogno, al minimo, per separare tutti gli scacchi?
 
Ciao
 
GaS


Immagino sia sottinteso che posso sovrapporre 2 o più pezzi e
'tagliarli' tutti insieme con un'unica mossa...
 
Bye by SixaM 8-]

On 13/07/2017 09:32, GaS wrote:

Ci provo:
Se non posso sovrapporre o comunque fare tagli che prendono più 
tavolette, direi nm-1: ogni taglio mi crea una nuova tavoletta, e alla 
fine ne devo avere nm.
Se posso sovrapporre, log2(nm) approssimato per eccesso: ogni taglio mi 
raddoppia le tavolette.
 
bye
-- 
Paolo Lucchesi - p...@NOSPAMpaololucchesi.it

 fine ne devo avere nm.
 
Sicuro che non sia (n-1)(m-1)? In tavoletta di n righe, le separo con
(n-1) tagli, idem x le colonne...
 
Bye by SixaM 8-]


Se con ogni taglio posso prendere una sola "sottotavoletta" (niente 
sovrapposizioni, niente tagli di tavolette accostate), con i primi (n-1) 
tagli ottengo n tavolette m x 1, e ognuna di esse ha bisogno di (m-1) 
tagli per ottenere gli scacchi separati.
Quindi (n-1) + n*(m-1) = nm - 1.
 
Se posso tagliare tavolette accostate ma non sovrapporre, la miglior 
riposta che trovo è un banale n+m-2.


 Quindi (n-1) + n*(m-1) = nm - 1.
 
Giusto, pensavo alle linee di taglio totali della tavoletta intera
quando ho fatto il calcolo, non rapportate ai singoli pezzi tagliati
 
By eby SixaM 8-]

 raddoppia le tavolette.
 
 
mmmmm, non lo vedo ma ci devo pensare meglio. Grazie dell'idea :-)
 
Ciao
GaS

 all'evidenza...
 
In effetti è curioso che il numero dei tagli prescinda dai lati della 
tavoletta e dal modo di effettuarli, ma che dipenda solo dall'area. Per 
induzione si dimostra che la formula è giusta, ma non so se sia la 
dimostrazione "semplice a capirsi" che intende Gabriele.
 
Innanzitutto la formula dipende esclusivamente dall'area, quindi diciamo che 
afferma che una tavoletta rettangolare di area A necessita di A - 1 tagli 
per essere ridotta a singoli scacchi.
 
Questo è vero per una tavoletta di area 1 (1 singolo scacco). Infatti i 
tagli sono A - 1 = 1 - 1 = 0.
 
Se faccio un taglio qualsiasi ad una tavoletta di area A > 1, ottengo due 
tavolette rettangolari rispettivamente di area B e C, entrambe non nulle, 
per cui B + C = A. Il numero totale di tagli per ridurre entrambe le 
tavolette a singoli scacchi sarà B - 1 + C - 1, che sommati al taglio appena 
effettuato rendono vera l'uguaglianza B - 1 + C - 1 + 1 = A - 1, che diventa 
B + C - 1 = A - 1, cioè B + C = A.
 
Ciao.
 
Giorgio
 

 dimostrazione "semplice a capirsi" che intende Gabriele.
[cut]
 
Più facile Giorgio, tanto facile che Paolo Lucchesi se la è cavata con 14 parole in tutto :-)
 
Ciao grande
GaS

"GaS"  ha scritto nel messaggio 
news:d5aba485-56c3-4c8e...@googlegroups.com...

Accidenti! Ho dovuto ricercarla tra i post di Paolo perché mi era proprio 
sfuggita. Veramente bella, nella sua "semplicità"!
 
Ciao
 
Giorgio