Welcome to NRICH.

 
Finite sequences
By Charlie Gilderdale on Monday, June 10, 2002 - 01:22 pm:

I have been asked to find all possible finite sequences {n0, n1, ..., nk} of integers such that,

for each i = 0, 1, ..., k

i appears in the sequence ni times.

I've had a go at the problem and found these solutions:

1,2,1,0
2,0,2,0
2,1,2,0,0

and an infinite set of solutions starting with

3,2,1,1,0,0,0
4,2,1,0,1,0,0,0
5,2,1,0,0,1,0,0,0
6,2,1,0,0,0,1,0,0,0
7,2,1,0,0,0,0,1,0,0,0
etc, etc
24,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0
etc, etc

Unfortunately, I have no way of proving that I have found all the possible solutions.
Can anyone help?
Many thanks
Charlie

By Graeme Mcrae on Monday, June 10, 2002 - 05:40 pm:

An interesting property of any solution to this question is this:

n0+n1+n2+...+nk = 0n0+1n1+2n2+...+knk

This fact might help you prove that you've found all possible solutions.

By Charlie Gilderdale on Tuesday, June 11, 2002 - 04:24 pm:

I can see that this must be true, but can't see how it helps me to prove that I have all the possible solutions.

By Graeme Mcrae on Tuesday, June 11, 2002 - 05:28 pm:

I'm not exactly sure how it helps, either, but I was thinking along these lines:

Suppose n1 > 2, and
n0+n1+n2+...+nk = 0n0+1n1+2n2+...+knk

Then n0 = n2+2n3+...+(k-1)nk

Maybe you can reach a contradiction this way.

On thinking it over, there's another way that looks more fruitful:

The number of elements of the sequence is equal to the sum of the elements.

So the number of non-zero elements among n1, n2, ... must be one less than the sum of n1+n2+...+nk, which means that at most one of them is "2", and all the rest of the non-zero elements are "1". The only way to achieve that, within the rules of this game is using the sequences you've described.

By Charlie Gilderdale on Wednesday, June 12, 2002 - 03:31 pm:

Many thanks Graeme for all your help. I had to work hard to understand what you meant in the last paragraph, but I got there in the end.
All the best.

By Charlie Gilderdale on Thursday, June 13, 2002 - 12:43 pm:

I've had a go at explaining the solution to the problem to somebody else, so I thought I'd post my working here for anybody who might be interested:

n0 + n1 + n2 + n3 + ........ nk = k + 1

So
n1 + n2 + n3 + ........ nk = (k + 1) - n0

In
n1, n2, n3, ....... nk there are k elements;

we know that n0 of them are zeroes (note that n0 cannot be zero),
so there are (k - n0) elements that are not zero;

if each of these elements were 1, they would add up to k - n0,
but we know that they need to add up to (k + 1) - n0 (see above).

Therefore, if these (k - n0) non-zero elements are to add up to (k + 1) - n0,
one of the 1's needs to be turned into a 2

(note that we cannot have a number greater than 2 since that would then
require at least one zero amongst the non-zero elements).

This means that n0 can take any value greater than 0,
and all subsequent values must be a combination of 0's, 1's and a 2.

The only sequences that fit these conditions are:

1,2,1,0
2,0,2,0
2,1,2,0,0

and an infinite set of solutions starting with

3,2,1,1,0,0,0
4,2,1,0,1,0,0,0
5,2,1,0,0,1,0,0,0
6,2,1,0,0,0,1,0,0,0
7,2,1,0,0,0,0,1,0,0,0
etc, etc

I hope this is helpful.

By Graeme Mcrae on Friday, June 14, 2002 - 05:56 am:

Charlie, you're welcome! I like the way you restated and elaborated on my explanation. After you described the solution, it seemed quite obvious, which, of course, it isn't when one first sees this question. That makes this question fun.