# recurrence relation with min-max

While solving a puzzle I got stuck with this recurrence

\begin{align*} &A(n) = \min_x \left \{ \max \left [ x, 1+A(n-x) \right ] \right \} \\ &\text{where }A(1) = 1,A(0) = 0 \text{ and } 1 \leq x \leq n , \text{ x is natural }\\ \end{align*}

Please give some idea how to proceed ? Thanks !

• Whats is the nature of $x$ ? Is it real ? – Khosrotash Aug 13 '17 at 7:34
• No x is natural number – Debashish Aug 13 '17 at 7:35
• $A(2)=\min \{ \max\{1, 2\},\max\{2,1+A(0)\} \}$.... so need to know what is $A(0)$ – MAN-MADE Aug 13 '17 at 7:40
• This would give $A(k) = n$ when $2k \in (n(n-1), n(n+1)]$. (when $n \neq 0$) – Gribouillis Aug 13 '17 at 7:58
• @Gribouillis Got the same outcome with javascript code: var a = [1]; for (let i=0; i<100; i++) {var minVal = Infinity; for (let j=0; j<a.length; j++) {minVal = Math.min(minVal, Math.max(j+1, 1+a[a.length-1-j]));} a.push(minVal); a.push(minVal); } – ploosu2 Aug 13 '17 at 8:20

• Show by induction that $A(n) \le n$
• Show that when $n>1$, $\displaystyle\min_{1\le x\le n} = \min_{1\le x < n}$
• Use this to prove by induction that $A(n)\le A(n+1)$
• Prove that $A(n)\le A(n+1)\le 1 + A(n)$, so that $A(n+1) = A(n) \text{ or } 1+A(n)$