Блог пользователя jhknmj

A supercalifragilisticexpialidocious problem
Автор jhknmj, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
← 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}

→ Ответить
»
3 года назад, # |
← 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.

→ Ответить