[MAT] La tavoletta di cioccolata

[GaS]

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

[SixaM]

Post by GaS
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-]

[Paolo Lucchesi]

Post by GaS
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?

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

[SixaM]

Post by Paolo Lucchesi
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.

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-]

[Paolo Lucchesi]

Post by SixaM

Post by Paolo Lucchesi
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.

Sicuro che non sia (n-1)(m-1)? In tavoletta di n righe, le separo con
(n-1) tagli, idem x le colonne...

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.

bye

[SixaM]

Post by Paolo Lucchesi
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.

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-]

[GaS]

Post by Paolo Lucchesi

Post by GaS
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?

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.

Avevo pensato a questa ipotesi in effetti, senza sovrapporre le "sottotavolette": mi sembra incredibile che a prescindere dall'ordine dei tagli il numero sia sempre fisso, ma la dimostrazione è così "semplice" (almeno a capirsi, non tanto a trovarsi) che non si può non cedere all'evidenza...

Post by Paolo Lucchesi
Se posso sovrapporre, log2(nm) approssimato per eccesso: ogni taglio mi
raddoppia le tavolette.

mmmmm, non lo vedo ma ci devo pensare meglio. Grazie dell'idea :-)

Ciao
GaS

[Giorgio Vecchi]

Post by GaS
Avevo pensato a questa ipotesi in effetti, senza sovrapporre le
"sottotavolette": mi sembra incredibile che a prescindere dall'ordine dei
tagli il numero sia sempre fisso, > ma la dimostrazione è così "semplice"
(almeno a capirsi, non tanto a trovarsi) che non si può non cedere
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

[GaS]

Il giorno venerdì 14 luglio 2017 12:44:44 UTC+2, Giorgio Vecchi ha scritto:
[cut]

Post by Giorgio Vecchi
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.

[cut]

Più facile Giorgio, tanto facile che Paolo Lucchesi se la è cavata con 14 parole in tutto :-)

Ciao grande
GaS

[Giorgio Vecchi]

"GaS" ha scritto nel messaggio news:d5aba485-56c3-4c8e-ace9-***@googlegroups.com...

Il giorno venerdì 14 luglio 2017 12:44:44 UTC+2, Giorgio Vecchi ha scritto:
[cut]

Post by Giorgio Vecchi
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.

[cut]

Post by Giorgio Vecchi
Più facile Giorgio, tanto facile che Paolo Lucchesi se la è cavata con 14
parole in tutto :-)

Accidenti! Ho dovuto ricercarla tra i post di Paolo perché mi era proprio
sfuggita. Veramente bella, nella sua "semplicità"!

Ciao

Giorgio