Problem 1-7: Back-Engineering

Problem Posts

[Difficulty 2] [PDF]

QUESTION
(Adapted from UVA 10784) The number of diagonals of an $n$-gon is not less than $N$. Find a closed-form expression for the minimum possible value of $n$.

Laconic Solution Sketch
A polygon has an integral side number. Use bounds.




Discussion

Don't underestimate the power of making a ballpark estimate. We know that for some $n$, $N \le \frac{n \cdot\left(n-3\right)}{2}$. Since $n$ is minimum, $n-1$ won't cut it: $\frac{\left(n-1\right) \cdot\left(n-1-3\right)}{2} < N$. Now expand: $$n^2-5n+4<2N\le n^2-3n$$ Our instincts tell us to complete the square. Add $9/4$ to each element: $$\left(n-\frac{5}{2}\right)^2<2N+\frac{9}{4}\le \left(n-\frac{3}{2}\right)^2$$ It's noteworthy that adding the same constant completes the square for both sides. This is no accident, as the left hand side is just the right hand side under the substitution $n \rightarrow n-1$. We finish this one off: $$n-1<\sqrt{2N+\frac{9}{4}}+\frac{3}{2}\le n$$ and so $$n=\boxed{\left \lceil \sqrt{2N+\dfrac{9}{4}}+\dfrac{3}{2} \right \rceil}$$ .

Warning: Note how we're "forced" to use the least integer (ceiling) function instead of the greatest integer function, because the non-strict inequality lies between the second and third expressions. Of course, we could use the floor function, but it's cumbersome: $$n=\boxed{-\left \lfloor -\left( \sqrt{2N+\dfrac{9}{4}}+\dfrac{3}{2} \right) \right \rfloor}$$ Admittedly, both expressions are cumbersome. The question comes up:

BONUS QUESTION 1
If we had the added information that $N>0$ is indeed the number of diagonals of some polygon, could we make a simpler expression - simple enough to calculate mentally?

Yes. Since we know that $N=\frac{n \cdot\left(n-3\right)}{2}>0$, we can afford to be lax and choose bounds that we like (bounds that don't involve fractions). First, $N>0$ hence $n>3$. We bound $2N$ between two perfect squares: $$n^2-4n+4 \le n^3 - 3n < n^2-2n+1$$ (We can verify that $4-n\le 0 < n+1$, and we simply add $2N$ to each side). Then $$n=\boxed{\left\lfloor 2N \right \rfloor +2}$$ which is much nicer.

BONUS QUESTION 2
(Mr Jurgeen Vasquez, OEIS) Find a closed-form expression for the $n^\mathrm{th}$ term $a_n$ of the sequence $1,1,2,1,2,3,1,2,3,4\ldots$

The most sensible thing to do is arrange the sequence in tiers: $$\begin{array}{cccc} 1,\\ 1, & 2,\\ 1, & 2, & 3,\\ 1, & 2, & 3, & 4,\ldots \end{array}$$ Now we want a formula to know which tier$a_n$ term is in. Now, if $a_n$ is in the $N^\mathrm{th}$ tier, we have $\frac{N \cdot\left(n-1\right)}{2} < n\le\frac{N \cdot\left(N+1\right)}{2}$ Using exactly the same method as above we get $$N=\left\lceil \sqrt{2n+\frac{1}{4}}-\frac{1}{2} \right\rceil$$ We figure out that $a_n = n - \frac{N^2-N}{2}$.