11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by unique minimum and unique maximum? $\endgroup$ – Beastly Gerbil Sep 30 '16 at 16:05
  • 2
    $\begingroup$ @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. $\endgroup$ – user27395 Sep 30 '16 at 16:06
  • 2
    $\begingroup$ "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? $\endgroup$ – Rand al'Thor Sep 30 '16 at 17:40
  • $\begingroup$ @randal'thor they just can be included. $\endgroup$ – Ankoganit Oct 1 '16 at 3:05
11
$\begingroup$

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$.

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

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.