11
$\begingroup$

I was looking at this short video, and it made me think of a puzzle.

Let's say you have this set of equations:

_ = N
_ + _ = N
_ + _ + _ = N
_ + _ + _ + _ = N
_ + _ + _ + _ + _ = N

If every blank has to be filled in with a different positive integer, what's the smallest possible value for N?

As a bonus -- which I don't personally know the answer to -- is there any (provable) straightforward formula that generalizes to any number of rows?

$\endgroup$
13
$\begingroup$

I'm not sure about the bonus but here's the best you can do for the main part

 27 = 27
 13 + 14 = 27
  8 +  9 + 10 = 27
  4 +  5 +  7 + 11 = 27
  1 +  2 +  3 +  6 + 15 = 27
 

Proof that this is the best

Ignore the first equation and consider the sum of both sides of the other four equations. This gives us that the sum of fourteen distinct positive integers is equal to $4N$. The sum of fourteen distinct positive integers is at least $105$ so we have $4N \geq 105$ or $N \geq 26.25$. Hence $N \geq 27$

Lower bound for the bonus

Let's say we use the same reasoning to try to obtain a lower bound and there are $n$ equations. Then ignoring the first equation we will have $\frac{n^2+n-2}{2}$ distinct positive integers on the left hand side which sum to $(n-1)N$. The smallest possible value of the sum of $\frac{n^2+n-2}{2}$ distinct positive integers is $\frac{(n^2+n-2)(n^2+n)}{8}$ so we have that $$ N \geq \frac{(n^2+n-2)(n^2+n)}{8(n-1)} = \frac{n(n+1)(n+2)}{8}$$ or, since we know it is an integer $$N \geq \left\lceil \frac{n(n+1)(n+2)}{8} \right\rceil$$

Improving this bound for larger $n$ (credit to Greg Martin in the comments for this idea)

If we ignore roughly the first $\frac{n}{3}$ equations and just consider the rest then we'll have roughly $\frac{4n^2 + 3n}{9}$ positive integers on the left hand side which sum to $\frac{2nN}{3}$ and since the sum of the first $\frac{4n^2 + 3n}{9}$ positive integers is $\frac{(4n^2 + 3n)(4n^2+3n+9)}{162}$ we obtain $$ \frac{2nN}{3} \geq \frac{(4n^2 + 3n)(4n^2+3n+9)}{162}$$ or $$ N \geq \frac{16n^3+24n^2+45n+27}{108} > \frac{4n^3}{27}$$ Greg Martin found the cutoff point $\frac{2n}{3}$ by optimization.
Already at $n=6$ we see this bound take over where the value of $\frac{16n^3+24n^2+45n+27}{108}$ is $42.75$ but for my original bound it's $42$.

$\endgroup$
9
  • 2
    $\begingroup$ The lower bound you give is $O(n^3)$ and is based on all terms being $O(n^2)$. This must at some point stop being achievable since all sums with fixed number of terms are also $O(n^2)$ and therefore cannot keep up with the bound. $\endgroup$ Jun 4 at 0:27
  • 1
    $\begingroup$ One can improve the lower bound by ignoring the first (roughly) $n/3$ equations and using the fact that the last $2n/3$ equations sum to $2nN/3$; the resulting lower bound is approximately $N \ge 4n^3/27$. (The cutoff $2n/3$ was found by considering the general cutoff $\ell$ and optimizing.) $\endgroup$ Jun 4 at 7:23
  • $\begingroup$ @GregMartin Thanks, I've added in a paragraph with your bound. $\endgroup$
    – hexomino
    Jun 4 at 10:45
  • $\begingroup$ @Albert.Lang you make a good point. How then should we expect $N$ to scale with $n$? $\endgroup$
    – hexomino
    Jun 4 at 10:48
  • $\begingroup$ My guess is we can maintain O(n^3). Naively, I would try to find the point at which $\sum_1^n i, \frac 1 2 \sum_1^{2n-1} i, \frac 1 3 \sum_1^{3n-3} i,...$ maxes out. From this point to the end we can try and use the smallest integers above that we need to use larger ones. $\endgroup$ Jun 4 at 13:36
4
$\begingroup$

The OIES entry for the sequence A047837 calls this "Honaker's triangle problem" and says that the optimal $N$ is conjectured to equal:

$$ a(n) = \max_{r=1\ldots n-1}\left\lceil\frac{T(T(n)-T(r-1))}{n-r+1}\right\rceil $$

(sequence A047873), where $T(n)=n(n+1)/2$, the $n$-th triangular number. The OIES entry refers to the book The Zen of Magic Squares, Circles and Stars by Clifford A. Pickover, who attributes the problem to math teacher and author G.L. Honaker, Jr. Pickover gives the same expression (in simplified form) as a lower bound on the sum $M$:

$$ M(n) = \left\lceil\frac{T(T(n)-T(\lfloor n/3\rfloor))}{n-\lfloor n/3\rfloor}\right\rceil $$

(This is equal to the above expression at the maximal value of $r=\lfloor n/3\rfloor+1$.) This bound is credited to Mike Keith and Judson McCraine, who conjecture this bound is exact and have verified it "for all $n$ up to several hundred" (the OEIS says $n<365$). Unfortuately the trail of references ends here, as Pickover cites personal communication with Keith.


Note that the bound can be derived using the method described by hexomino, as shown below.

The triangle with $n$ rows has $T(n)$ entries, and similarly the portion of the triangle above row $r$ (i.e. up to row $r-1$) has $T(r-1)$ entries. Therefore the trapezoid from rows $r$ to $n$ has $k=T(n)-T(r-1)$ entries. The sum of the entries is equal to the row sum $N$ times the number of rows, $n-(r-1)=n-r+1$. Since these entries must be distinct, their sum must be no less than the sum of the first $k$ integers, which is $T(k)=T(T(n)-T(r-1))$. Putting these together yields:

$$ \begin{align} N &\ge \frac{T(T(n)-T(r-1))}{n-r+1} \\ &= \frac{\left(\frac{n(n+1)}{2} - \frac{(r-1)r}{2}\right)\left(\frac{n(n+1)}{2} - \frac{(r-1)r}{2}+1\right)}{2(n-r+1)} \\ &= \frac{\left(n^2-r^2+n+r\right)\left(n^2-r^2+n+r+2\right)}{8(n-r+1)} \\ &= \frac{\left((n+r)(n-r)+(n+r)\right)\left(n^2-r^2+n+r+2\right)}{8(n-r+1)} \\ &= \frac{\left(n+r\right)\left(n-r+1\right)\left(n^2-r^2+n+r+2\right)}{8(n-r+1)} \\ &= \frac{1}{8}\left(n+r\right)\left(n^2-r^2+n+r+2\right) \\ &= \frac{1}{8}\left(-r^3-(n-1)r^2+(n^2+2n+2)r+(n^3+n^2+2n)\right) \end{align} $$

Since this is true for any $r\in[1,n]$, we can take the maximum over all $r$ as the lower bound for $n$ (and since $N$ is an integer we can take the ceiling as well). The expression is cubic in $r$, with a derivative of:

$$ \frac{1}{8}\left(-3r^2-2(n-1)r+(n^2+2n+2)\right) $$

The derivative has roots at:

$$ \begin{align} r^* &=\frac{2(n-1)\pm\sqrt{4(n-1)^2-4(-3)(n^2+2n+2)}}{2(-3)} \\ &= \frac{1}{3}\left(1-n\pm\sqrt{n^2-2n+1+3n^2+6n+6}\right) \\ &= \frac{1}{3}\left(1-n\pm\sqrt{4n^2+4n+7}\right) \\ &= \frac{1}{3}\left(1-n\pm\sqrt{(2n+1)^2+6}\right) \end{align} $$

The derivative is a downward-facing parabola, so the expression is decreasing before the first root, increasing between the two roots, and decreasing after the second root. However, the first root occurs when $r<0$ so for the range we are interested in the expression is increasing before the positive root and decreasing after. This means that the maximum for $r\in\mathbb{R}$ occurs at the positive value of $r^*$, and the maximum for $r\in\mathbb{Z}$ will occur at the floor or ceiling of $r^*$.

Note that, for $a,b\gt 0$:

$$ \begin{align} \left(a+\frac{b}{2a}\right)^2 &= a^2+b+\left(\frac{b}{2a}\right)^2 \\ \left(a+\frac{b}{2a}\right)^2 &> a^2+b \\ a+\frac{b}{2a} &> \sqrt{a^2+b} \\ \end{align} $$

We can use this, as well as $a<\sqrt{a^2+b}$, to bound the square root term in the expression for the optimum $r$:

$$ \frac{1-n+(2n+1)}{3} < \frac{1-n+\sqrt{(2n+1)^2+6}}{3} < \frac{1-n+(2n+1)+\frac{6}{2(2n+1)}}{3} \\ \frac{n+2}{3} < r^* < \frac{n+2}{3}+\frac{1}{2n+1} $$

Finally, if we take $n\ge 1$, then $\frac{1}{2n+1}\le \frac{1}{3}$, so we can bound:

$$ \frac{n+2}{3} < r^* \le \frac{n}{3}+1 $$

From this we can determine that the optimum value for $r\in\mathbb{Z}$ is one of $\lfloor (n+2)/3\rfloor=\lceil n/3\rceil$ or $\lceil n/3\rceil+1$. To determine which, we need to consider three cases:

$$ \begin{align} n&=3k & \lceil n/3\rceil &= k \\ n&=3k+1 & \lceil n/3\rceil &= k + 1 \\ n&=3k+2 & \lceil n/3\rceil &= k + 1 \\ \end{align} $$

For each of these cases, the two bounds for $n$ are:

$$ \begin{array}{|c|c|c|} \hline n & N(r=\lceil n/3\rceil) & N(r=\lceil n/3\rceil+1) \\ \hline 3k & 4k^3+2k^2+k & 4k^3+2k^2+\frac{5}{4}k+\frac{1}{4} \\ \hline 3k+1 & 4k^3+6k^2+4k+1 & 4k^3+6k^2+\frac{13}{4}k+\frac{3}{4} \\ \hline 3k+2 & 4k^3+10k^2+\frac{37}{4}k+3 & 4k^3+10k^2+9k+3 \\ \hline \end{array} $$

For the $n=3k$ case, the right-hand column ($r=\lceil n/3\rceil+1$) is larger, while for the other two the left-hand column is larger ($r=\lceil n/3\rceil$). However, note that $\lceil n/3\rceil=\lfloor n/3\rfloor$ when $n$ is divisible by 3, and $\lceil n/3\rceil=\lfloor n/3\rfloor+1$ when $n$ is not divisible by 3, so both cases can be simplified to just:

$$ r=\lfloor n/3\rfloor +1 \tag*{$\blacksquare$} $$

$\endgroup$
1
  • $\begingroup$ This is brilliant work - give this person a bonus! Great connection to the Honaker problem that will save me a great deal of computation. $\endgroup$ Jun 11 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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