Hyper-triangular numbers

Triangular number $T_n$ is defined as $T_n = 1 + 2 + \dots + n$.

Tetrahedral number $R_n$ is defined as $R_n = T_1 + T_2 + \dots + T_n$.

Let $T^k_n$ denote the $k$-th dimensional triangular numbers, with $T^1_n = 1+1+\dots+1 = n$, $T^2_n = T_n$, and $T^3_n = R_n$. Specifically, the higher dimensional triangular numbers are defined as: $$ T^{k+1}_n = T^k_1 + T^k_2 + \dots + T^k_n$$ Prove that: $$T^k_n.T^m_1 + T^k_{n-1}.T^m_2 + \dots + T^k_1.T^m_n = T^{k+m+1}_{n+1}$$

Triangular equations

A triangular series of equations is a system of $k$ equations where the $k$-th row consists of $k+1$ terms on the LHS and $k$ terms on the RHS. For example: $$a + b = c$$ $$d + e + f = g + h$$ $$i + j + k + l + m = n + o + p$$ $$...$$ Given the numbers $1, 2, \dots, n^2$ and one number with the same parity as $n$ is removed, prove that the rest of the numbers can be arranged into a triangular series of equations.

For example, out of $1,2,\dots,9$, 3 is removed, so the rest can be written as: $$ 1+4 = 5$$ $$2 + 6 + 8 = 7 + 9$$ Another example, out of $1,2,\dots, 16$, 10 is removed, so the rest can be written as: $$1+3 = 4$$ $$2 + 5 + 8 = 6 + 9$$ $$7 + 11 + 12 + 14 = 13 + 15 + 16 $$

Solution (In Progress)

Suppose we color all the numbers with the same parity as $n$ with red, and color all the numbers with the opposite parity with black. Also, call the number that was removed, the missing number, $x$. A number is called "good" if, when missing, the rest of the numbers can be written as triangular system.

Note the triangular system below: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$9+10+11+12 = 13+14+15$$ $$...$$ $$k^2 + \dots + (k^2+k) = (k^2+k+1) + \dots + (k^2+2k)$$ $$...$$ $$(n-1)^2 + \dots + ((n-1)^2+n-1) = ((n-1)^2+(n-1)+1) + \dots + (n^2-1)$$ We call this system A. This system is missing $n^2$, and the system is triangular and correct. (The correctness of said system can be verified by simple arithmetic series on the $k$-th row).

So we know that $n^2$ is good. Furthermore, note that each row has the same number of odd numbers (that is, $k$-th row has $k$ odd numbers if $k$ is odd and $k-1$ odd numbers if $k$ is even). So if we increase each odd number by two, we'll still get a correct triangular system: $$3+2 = 5$$ $$4+7+6 = 9+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ So if $n$ is odd, 1 is good. Call this system B.

Similarly, the $k$-th row has $k$ even numbers in the LHS and $k-1$ even numbers in the RHS. We can increase the even numbers by two, but then the equation will be incorrect. Call the "weight" of an equation to be its RHS - LHS. Obviously, an equation is correct only if it has weight zero. If we increase all the even numbers by two, then the weight of the new equation is -2, for example: $$6+5+8 > 7+10,w=-2$$ But note that now $(k^2+k+2)$ is in the LHS while $k^2+k+1$ is still in the RHS. In other words, the largest number in the LHS is exactly one more than the smallest number in the RHS, so if we switch those two, we restore the weight back to zero: $$6+5+7 = 8+10$$ So we can form a new system this way: $$1+3=4$$ $$6+5+7 = 8+10$$ $$9+12+11+13 = 14+16+15$$ $$...$$ Next, note that out of the $n$ rows in the equation, we can take the first $k$ rows from system A, and the $n-k$ last rows from system B or C. For example: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ Now we are ready to prove the main assertion by induction. We will show the base cases later. For now, suppose it holds for $n=2,3$. Then, if $x \leq (n-2)^2$, there is a way to arrange $\{1, 2, \dots, (n-2)^2\} \ \{x\}$ in triangular form by induction hypothesis, and the last two rows can be taken from the last two rows of system B (if $n$ is even) or system C (if $n$ is odd). So then we consider cases where the missing number is $x > (n-2)^2$. In system A above, it would be in the last two rows. We will divide into cases depending on the position of $x$ in system A. Note that the missing number is always red.

Suppose $x$ is red on the last row RHS (meaning the missing number is in the interval $x \ in [(n-1)^2+(n-1)+1, n^2-2]$). Take out that number and replace it with $n^2$. Then now the last row has weight a positive even number in the interval $[2, n-1]$. We can switch a number $k$ from LHS and $l$ from the RHS, and the weight would decrease by $2(l-k)$. But the difference of the numbers in RHS and LHS ranges from 1 to $2n-2 > n-2$, and each side has consecutive numbers. So we know there are numbers that we can pick to switch so that the weight is reduced back to zero.

Suppose the missing number is red on the last row LHS, meaning the missing number is in the interval $x \in [(n-1)^2+1, (n-1)^2+(n-1)]$. Take out that number and replace it with $n^2$. Then the last row has weight a negative even number in the interval $[-2n+2, -n]$. Now, there exists a number in RHS $y$ such that $y-n^2$ is exactly half the weight of the last row, because the numbers in RHS is in the range $[(n-1)^2+(n-1)+1,n^2-1]$ so those numbers subtracted by $n^2$ is in the range $[-n+1, -1]$ which encompasses $\frac{1}{2} [-2n+2, -n]$. If we switch this number $y$ and $n^2$, the weight of the last row is restored.

Suppose the missing number is red on the second-to-last (STL) row LHS, meaning the missing number is in the interval $x \in [(n-2)^2, (n-2)^2+(n-2)]$. Take out that number and replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where $(n-1)^2+1$ used to be. The STL row now has weight negative even number in the interval $[-2n+2,-n]$, whereas last row has some other even number weight. The last row could be fixed with the procedure described above (as if $(n-1)^2+1$ was the missing number). However the STL row can be fixed by switching $(n-1)^2+1$ with an appropriate number in the STL RHS, because the numbers in STL RHS ranges from $[n^2-3n+3,n^2-2n]$ so the difference ranges from $[-n+1, -2]$ which encompasses $\frac{1}{2}[-2n+2,-n]$

Suppose the missing number is red on the STL row RHS. Same as before, take out that number, replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where it used to be. Same as above, the last row can be fixed using the previous strategy, whereas the STL row can be fixed by switching two numbers in the STL (similar to if the missing number is from RHS last row).

Now all that remains is to prove the base cases. For $n=2$, we have either $1+3=4$ or $1+2=3$. For $n=3$, the missing numbers could be $x=1,3,5,7,9$, but $x=9$ is already covered by system A above, $x=1$ covered by system B, and $x=3$ is shown in the example. For $x=5$: $$1+2=3$$ $$4+7+6 = 9+8$$ For $x=7$: $$1+3=4$$ $$2+5+8 = 6+9$$ (Really we're just applying the algorithm described above but we're including here for the sake of proof completeness).

Integer solutions

Let $f(t) = t(t-1)$. Find all positive integers $x,y$ such that $$f(x) + f(y) = f(x+y) / 2$$ First Solution Expanding and canceling, we have: $$x^2+y^2-2xy = x+y$$ It's easy to see that there's no solution for $x=y$. The above equation is now equivalent to: $$16x^2+16y^2+1-8x-8y+32xy = 64xy+8x+8y+1$$ $$(4x+4y-1)^2 = (8x+1)(8y+1)$$ Because both quantities are positive, we have: $$4x+4y-1 = \sqrt{8x+1} \sqrt{8y+1}$$ Once again rearranging, $$(8x+1) - 2\sqrt{8x+1} \sqrt{8y+1} + (8y+1) = 4$$ $$(\sqrt{8x+1} - \sqrt{8y+1})^2 = 4$$ If $x=y$, then there is no solution WLOG, we may assume that $x > y$, so that $$\frac{\sqrt{8x+1}}{2} - \frac{\sqrt{8y+1}}{2} = 1$$ Note that $g(t) = \frac{1+\sqrt{8t+1}}{2}$ is the reverse triangular number function. Thus, any two consecutive triangular numbers (for example 3 and 6, 6 and 10, and so on) are a solution.

Now we show that there's no other solution. The equation is equivalent to $g(x) - g(y) = 1$. In order for $g(x)$, to be an integer, we must have $8x + 1 = k^2$ for some $k$. But $k$ is odd, so $8x+1 = 4m^2 + 4m + 1$ which means $x = m(m+1)/2$ is a triangular number

Now suppose $g(x)$ is not an integer, then it will be irrational, and so will $g(y)$. They both have form of $a+\sqrt{b}$ with $a,b$ rational, but with different $b$s, because $x \neq y$. The difference can't be rational, a contradiction.

Thus, the only solutions are two consecutive triangular numbers. Second Solution Let $d = \gcd(x,y)$, and $x = dm, y = dn$ with $m,n$ coprime. Upon substitution and rearranging, we have: $$d(m-n)^2 = m+n$$ Clearly $m=n$ is not a solution. Now wlog let $m < n$ and $n = m + k$ $$dk^2 = 2m+k$$ Because $k$ divides $dk^2$ and $2m$ then $k$ divides $2m$. Because $m$ and $n$ are coprime, then $k$ and $m$ are coprime. Thus we have $k=1$ or $k=2$.

For $k=1$, $d = 2m+1, n=m+1$, so $x = (2m+1)m,y=(2m+1)(m+1)$.

For $k=2$, $d = (m+1)/2, n=m+2$, and obviously we can only use odd values of $m$. Suppose $m = 2l+1$, then $d = l+1, n=2l+3$, so $x=(l+1)(2l+1), y =(l+1)(2l+3)$. Interestingly, this form is the same as the case for $k=1$, except we substitute $m = l + 1/2$

Combining the two cases, we can conclude that the solution must have form of $m(2m+1),(m+1)(2m+1)$ for $m$ multiples of 1/2, or equivalently, $k(k+1)/2, (k+1)(k+2)/2$ for $k$ any integers. In other words, they must be two consecutive triangular numbers.

Solution 1: Critical Height

Original problem: http://dharmath.blogspot.com/2010/04/critical-height.html

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1

First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.

Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.

From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.

Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
So:
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$

For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.

Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$

Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
...
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.

We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.

Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.

We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.

$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$

So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.

This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.

For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
...
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.

For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$