Permutations of first 10 natural numbers such that all the prefix sums are distinct

Question

I posted this question on Math SE as well. Did not receive any help. This is a question that I was asked in a Quant Interview. I would like you all to have a crack at this. I could not find a problem similar in any way to this on the internet.

Given the first 10 natural numbers: $1, 2, \ldots 10 $. Find $6$ permutations of these numbers:

$$a_{1,1}, \; a_{1,2}, \ldots a_{1, 10}$$ $$a_{2, 1},\; a_{2,2}, \ldots a_{2, 10}$$ $$a_{3, 1},\; a_{3,2}, \ldots a_{3, 10}$$ $$a_{4, 1},\; a_{4,2}, \ldots a_{4, 10}$$ $$a_{5, 1},\; a_{5,2}, \ldots a_{5, 10}$$ $$a_{6, 1},\; a_{6,2}, \ldots a_{6, 10}$$ such that the sums of the prefixes of lengths $1, 2, \ldots 9$ of the $6$ permutations are distinct.

What I could notice in the problem was that the number of sums that we are supposed to make distinct is $9 \times 6 = 54$ and the last sum i.e. the sum of all the numbers will be the same for every permutation i.e. equal to $55$.

Hence, we can target every number from $1, 2, \ldots 54$ successively and try to create permutations in that manner. However, I am unable to prove/disprove whether this sort of construction will be possible for any 6 initial values (one for each permutation).

P.S. Lucky for me, $1, 2, 3, 4, 5, 6$ do make a valid set of the initial choices and I could construct the 6 permutations. However, the interviewer wasn't very impressed with the solution and asked me to think of a smarter way.

EDIT:

I made some kind of observation on the problem. Suppose we have a certain choice of numbers for the $j^{th}$ column of the permutations i.e. the set ${a_{1, j}, \ldots a_{6, j}}$, we can arrange the same values in the reverse order in the column $10-j+1$.

This would ensure that we have the same total sum left among the remaining numbers. I could not make any formal proof that this would work but I believe this could help.

Answer 1

This is a difficult puzzle, especially for an interview. It seems that there ought to be a clever solution, rather than a brute-force or trial and error kind of solution. Typically, I would expect something hinted at by @FlorianF where the puzzle is equivalent to something that has an obvious solution. Or that there would be some simple algorithm that yields a solution. I haven't found either one.

There are a couple of nice results that are almost helpful. For example, if you have a 1 at the beginning, you can move it to the end and have a second set that doesn't interfere with the first.

In terms of algorithms, the one I found most helpful (so far) was:

Build up the solution, hitting each sum in order (1 to 54), by adding the biggest legally available number to one of the 6 sequences.

For example:

- You first want a 1, so set $a_{1,1}=1$.
- Next you're looking for a 2. So set $a_{2,1}=2$
- This actually replicates the OPs starting point of $a_{i,1}=i$ for $i\in{1,\ldots,6}$.
- Next, you set $a_{i,2}=6$ for $i\in{1,\ldots,5}$
- Now $a_{6,2}$ cannot be 6, so you set $a_{1,3}=5$.
And so on. It's easy, and promising, but it ultimately gets stuck at some point.

Like this:

Failed attempt:
\begin{matrix}1&2&3&4&5&6\\6&6&6&6&6&7\\5&7&5&7&7&8\\4&4&8&3&8&9\\7&5&7&5&2&4\\8&3&9&8&4&2\\9&8&1&9&9&1\\?&9&4&?&?&?\\?&?&2&?&?&?\\?&?&?&?&?&?\end{matrix}

Or to put it visually:

So ultimately no cigar.

I then thought that there's some symmetry to the situation. For example, we need exactly one of the sequences to start with a 1, to start with a 2, to end with a 1, and to end with a 2.

So what if we:

Start with the first three columns, jumping to the 3 right columns only when we have to (for 8,9,10).
This seems to take us a little further, but still not quite getting there.
\begin{matrix}1&2&4&8&9&10\\2&3&3&6&6&6\\3&6&6&5&7&5\\6&7&7&7&5&7\\5&5&5&3&3&8\\7&8&8&9&4&1\\8&4&9&2&10&2\\9&10&?&?&?&4\\?&?&?&?&?&3\\?&?&?&?&?&?\end{matrix}

Or in the visual version:

This one is closer, and with a small tweak or two can be made to work:

If you break the algorithm slightly, shading smaller possibilities to the three left columns, and delaying allocations to the three right columns, you can easily find a solution (I don't think they're fundamentally hard to find, actually. It's just finding it in a "clever" way is tricky!)

Solution:

Solution (1 of many I suppose):
\begin{matrix}1&2&4&8&9&10\\2&3&3&9&7&8\\3&7&7&6&8&7\\5&1&6&3&5&6\\4&6&2&7&6&3\\6&8&8&4&10&4\\7&5&9&5&2&2\\8&9&5&1&1&9\\10&10&10&10&4&1\\9&4&1&2&3&5\end{matrix}

Or visually:

So this solves the problem, but doesn't really solve the problem of the "clever" way the interviewer was looking for. Maybe there's a better algorithm.

Incidentally, the simple algorithm seems to work for some smaller cases (such as the wooden puzzle @JaapScherphuis alluded to):

(6,4) case:

(4,3) case:

But it doesn't work for the (8,4) case, at least not out the box.

Answer 2

I'm not really sure I understand the question, especially the meaning of "such that the sums of the prefixes of lengths 1,2,… of the 6 permutations are distinct" - as it is ambiguous as to whether or not 'distinct' carries across all sums of all prefixes of all permutations, or just the sums of the prefixes of each permutation.

An additional clue to the question is given by

The count of combinations and the prefixes required: the shape.

It reminds me of

The eight queens puzzle

The immediate thought, which provides an answer was

To merely shift each number once per combination.

Giving us..

 1   2   3   4   5   6   7   8   9   10
 10  1   2   3   4   5   6   7   8   9
 9   10  1   2   3   4   5   6   7   8
 8   9   10  1   2   3   4   5   6   7
 7   8   9   10  1   2   3   4   5   6
 6   7   8   9   10  1   2   3   4   5

 and the sums of each prefix being

 1    3   6   10  15  21  28  36  45  55
 10   11  13  16  20  25  31  38  46  55
 9    19  20  22  25  29  34  40  47  55
 8    17  27  28  30  33  37  42  48  55
 7    15  24  34  35  37  40  44  49  55
 6    13  21  30  40  41  43  46  50  55
 

This only answers the second interpretation (the sums of the prefixes of each permutation), but it is intuitively available.