# Pheno Menon's number challenge

Today Professor Pheno Menon challenged me with a puzzle:

"I will give you a composite number $n$. You need to give me a list of $n$ integers, all between $1$ to $n$ (those two included), so that the sum of their cubes is equal to the square of their sum. Can you always do that?

I said "That's easy! I can just give the numbers $1,2,\cdots,n$."

He replied, "Not so fast, my friend! There are some more conditions: the list must have a unique minimum and a unique maximum, and it mustn't be exactly the same as $1,2,\cdots ,n$ (up to permutation, of course). Now tell me, is it always possible?"

I tried for some time, but couldn't quite get to any conclusion. Maybe you can help?

I'd prefer a solution with completely elementary maths, not higher than high school mathematics.

• What do you mean by unique minimum and unique maximum? – Beastly Gerbil Sep 30 '16 at 16:05
• @BeastlyGerbil: There should be only one minimum number and only one maximum number, i.e [1,2,2,2,n] is allowed, but [1,1,2,3,n,n] is not. – user27395 Sep 30 '16 at 16:06
• "all between $1$ to $n$ (those two included)" - does that mean $1$ and $n$ MUST be included in the list (and therefore they are the unique minimum and maximum) or just that they CAN be? – Rand al'Thor Sep 30 '16 at 17:40
• @randal'thor they just can be included. – Ankoganit Oct 1 '16 at 3:05

Is it always possible?

Yes, it is always possible.

Proof:

Suppose $n=pq$ is a non-trivial factorization of $n$, and you have two lists $a_1, a_2, ..., a_p$ and $b_1, b_2, ..., b_q$ for which the sum of cubes is equal to the square of the sum, and each has a unique maximum and a unique minimum. That is, we have $(\sum a)^2 = \sum a^3 = A$ and $(\sum b)^2 = \sum b^3 = B$.

Now let's consider the list of pairwise products $c = (a_ib_j)$ (for every i,j). Clearly, $c$ has $n$ elements. Now let's compute $(\sum c)^2$ and $\sum c^3$:

$\sum c^3 = \sum a_i^3b_j^3 = (\sum a_i^3)(\sum b_j^3) = AB$
$(\sum c)^2 = (\sum a_ib_j)^2 = [(\sum a_i)(\sum b_j)]^2 = (\sum a_i)^2(\sum b_j)^2 = AB$

So $c$ also satisfies the property that the sum of the cubes is the square of the sum, and given that $a$ and $b$ had unique maxima and minima, $c$ has a unique maximum and a unique minimum as well.

It remains to show that suitable lists $a$ and $b$ exist. But this is obvious, because as said in the question we can take $a = 1, 2, ..., p$ and $b = 1, 2, ..., q$, and the final list $c$ cannot be equal to $1,2,...,n$ because it has at least two equal numbers $a_1b_2 = a_2b_1 = 2$.

• You also need to establish that the list you constructed isn't just 1,2,3,...,pq. (This is not terribly difficult.) – Gareth McCaughan Oct 1 '16 at 0:06