Lámání čokolády
Úloha číslo: 3303
Mějme tabulku čokolády o \(m\times n\) dílcích. Určete, kolikrát budete muset nějakou část čokolády rozlomit na dvě menší části než dostanete \(mn\) jednotlivých dílků.
Najděte postup, jak tabulku rozlámat s co nejmenším počtem lámání.
Řešení
Označme \(f(m,n)\) počet lámání tabulky o rozměrech \(m\times n\). Ze zadání plynou následující identity:
\(f(m,1)=m-1\)
\(f(1,n)=n-1\)
\(f(m+m’,n)=1+f(m,n)+f(m’,n)\)
\(f(m,n+n’)=1+f(m,n)+f(m,n’)\)Tyto mají řešení \(f(m,n)=mn-1\).
Odpověď
Na postupu lámání nezáleží, vždy bude třeba dílky rozlomit \((mn-1)\)-krát.