gabyteodor

(m-1)*(n-1)

wmutex

Daca notam cu X(m, n) numarul de "rupturi" ale ciocolatei mxn pentru a ajunge la patratele 1x1, atunci:

X(m, n) = 1 + min{ p = 1..m-1 | X(m-p, n) + X(p,n)}  pentru m>1

X(m, n) = X(n, m)

Prima formula spune ca numarul minim de "rupturi" ale ciocolatei este 1 (ruperea ciocolatei mxn in 2 bucati de lungimi p si m-p si latime n) plus nr optim de ruperi ale celor doua bucati rezultate.

A doua formula spune ca pozitia ciocolatei (orizontala sau verticala) nu conteaza cand contorizam ruperile.

Cateva calcule preliminare:

X(1,1) = 0
X(2,1) = 1; X(1,2) = 1
X(3,1) = 2; X(1,3) = 2
X(4,1) = 3; X(2,2) = 3; X(1,4)=3
X(5,1) = 4; X(1,5) = 4
X(6,1) = 5; X(3,2) = 5; X(2,3) = 5; X(1,6) = 5

Asta sugereaza ca:

X(m,n) = mn-1


Demonstratie prin inductie completa:

Presupunem ca, pentru a≤m, b≤n, ab<mn este intodeauna valabil ca:

X(a,b) = ab-1

Demonstram ca:

X(m,n) = mn-1

Avem:

X(m, n) = 1 + min{ p = 1..m-1 | X(m-p, n) + X(p,n)} =
    = 1 + min{ p = 1..m-1 | (m-p)n - 1 + pn - 1} =
    = 1 + min{ p = 1..m-1 | mn - 2} =
    = 1 + mn - 2
    = mn - 1 (q.e.d.)