### jhknmj's blog

By jhknmj, history, 6 months ago,

Find the number of such sequence A[0...n-1] that satisfies A[i] equals the number of i in A[0...n-1].

For example , if n = 9, there is only one solution [5, 2, 1, 0, 0, 1, 0, 0, 0]. (We use bruteforce to prove it)

We guess that if n > 6, there is only one solution and it takes the form of [n-4, 2, 1, 0, 0, ..., 1, ...,0, 0].

We want to know whether it is right.

• +38

 » 6 months ago, # | ← Rev. 2 →   +29 We find that if n=4,there exists two solutions: {1,2,1,0} {2,0,2,0} And if n=5,there exists one solution: {2,1,2,0,0}
 » 6 weeks ago, # | ← Rev. 3 →   0 A friend of mine -> ast123 have solved this problem.First, A[0] mustn't be 0.You can find that A[1] + A[2] + A[3]... + A[n-1] = (the number of i which doesn't equal 0 in A[1...n-1]) + 1.And A[1] + A[2] + A[3]... + A[n-1] means the sum of i which doesn't equal 0 in A[1...n-1].So there must be one 2 and some(may be zero) 1 in A[1...n-1].Second, Because there is no number which is bigger than 2 in A[1...n-1], so the number of 1 in A[1...n-1] is <= 2.At last,if there is no 1, the [2,0,2,0] is the only solution.if there is one 1, the [1,2,1,0] and [2,1,2,0,0] is the only two solution.if there is two 1, the solution takes the form of [n-4, 2, 1, 0, 0, ..., 1, ...,0, 0] when n > 6.It's easy to prove that there's no other situation.