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$
4
  • 1
    $\begingroup$ What do you mean by unique minimum and unique maximum? $\endgroup$ Sep 30, 2016 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, 2016 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$ Sep 30, 2016 at 17:40
  • $\begingroup$ @randal'thor they just can be included. $\endgroup$
    – Ankoganit
    Oct 1, 2016 at 3:05

1 Answer 1

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$
1
  • 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, 2016 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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