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.

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze