Recurrence with Minimum

Question

I need to solve the following recurrece:

$T(n,m)=\begin{cases} 1, & m\leq 2(n-1)!\\ \min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else} \end{cases}$

Note: in the first line beneath the $\min$ we have $a,b$ and in the next line it's $a\cdot b$.

I find it difficult to solve this recurrence as it contains $\min$, so I tried to calculate the minimum, but I didn't know how to prove it (I believe that the minimum occurs at $a=b=\sqrt{(n-1)!}$, but I don't know how to prove it...). So I am stuck with this.

Any help would be highly appreciated!

Edit:

Experiments show that

$T(n,m)=\begin{cases}1 & f(n,m)\leq 0\\ 3+2\Big\lfloor\frac {f(n,m)-1}{(n-1)!}\Big\rfloor & \text{else}\end{cases}$

for $f(n,m)=m-2(n-1)!$, and considering the $\min$ of an empty set to be infinity.

• 喜欢算法和数学: Is $T(n,m)$ defined on $\Bbb Z\times\Bbb Z$ or $\Bbb Z_{\ge0}\times\Bbb Z_{\ge0}$ or $\Bbb Z_{\ge1}\times\Bbb Z_{\ge1}$? If $(n,m)=(2,1)$ or $(n,m)=(2,2),ドル then $f(n,m)\le0$ and $n\le2$. According to your experiments, should $T(n,m)$ be 1 or $\infty$?
• Dudi Frid: @Apass.Jack It is defined on $\mathbb Z_{\geq 1}\times \mathbb Z_{\geq 1}$. In addition, I should have written "else if" in the second case; I edited my question respectively. Finally, are my experiments correct? How to prove it?

Answer 1

Let us prove that for $m \geq 1$, $$ T(n,m) = \max(1, 2\lfloor \tfrac{m-1}{(n-1)!} \rfloor - 1). $$ (This is the same as your formula.)

If $m \leq 2(n-1)!$ then by definition $T(n,m) = 1$, and indeed $\lfloor \tfrac{m-1}{(n-1)!} \rfloor \leq 1$, showing that our formula also gives the value 1ドル$. If $m > 2(n-1)!$, then $$ T(n,m) = \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n-1,a) + T(n-1,b) + T(n-ab). $$ Since $ab \leq (n-1)!$ also $a,b \leq (n-1)!$, and so $T(n-1,a) = T(n-1,b) = 1$. Therefore $$ T(n,m) = 2 + \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n,m-ab) = 2 + \min_{1 \leq c \leq (n-1)!} T(n,m-c). $$ We can prove inductively that $T(n,m)$ is monotone nondecreasing, and so $$ T(n,m) = 2 + T(n,m-(n-1)!). $$ From here it's not too hard to prove the formula by induction.