1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – John L.
    Jun 8, 2019 at 13:49
  • $\begingroup$ @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? $\endgroup$
    – Dudi Frid
    Jun 8, 2019 at 15:54

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.