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

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.

• Did you have a computer in the interview? Or was this a pen & paper exercise? If the latter, I would suggest you add a no-computers tag Jan 15 at 0:59
• I've seen a smaller version of this puzzle in a nice wooden form. It had 24 pieces in four types of wood. In each wood type there was a set of 6 pieces of different lengths from 1 to 6. These had to be placed in 4 rows in a tray, one wood type in each row, a bit like layers of brickwork. The rule was that the seams between the bricks should never line up. Jan 15 at 20:00
• @FirstNameLastName The $3$ rows of $4$ numbers case has $4$ distinct solutions if you disregard the row permutations and the left-right mirror images. Jan 17 at 6:33
• @FirstNameLastName and anybody else curious for a reasonably fast computer solution: Here is one. Note that this doesn’t print the last number of each permutation. Jan 18 at 7:11
• @bigbang, it would be a better question if you provided a concrete example, even if it fails - especially the meaning of 'prefix' in this case. Does this just mean "the first k numbers of each permutation where k is 1,2,3..9"? Jan 18 at 9:32

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.

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.

• I think the point is that all the sums should be distinct (every value between 1 and 54 appears once).
– fljx
Jan 18 at 11:28
• I believe this is not the intended answer. The sums (apart from the last column where the values are all 55) should be distinct. Since there are $9\times6=54$ sums, every number should be represented exactly once. Jan 18 at 20:51
• @DrXorile, you may have a point - but this doesn’t necessitate that the numbers will be 1…54, just that they will all be different. My guess is such an answer has something to do with primes. Jan 18 at 23:33
• Um... if you have 54 distinct whole numbers that are $\geq1$ and $<55$... Jan 18 at 23:50
• prefix sums must all be different and having 10 even, so it happens (not incidentally) to be, all 55-1=54 need to hit target Jan 19 at 4:36