Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $N$ children sitting along a circle, numbered $1,2,\dots,n$ clockwise. The ith child has a piece of paper with number $a_i$ written on it. They play the following game:

In the first round, the child numbered $x$ adds to his number the sum of the numbers of his neighbors. In the second round, the child next in clockwise order adds to his number the sum of the numbers of his neighbors, and so on. The game ends after M rounds have been played.

any idea about how to get the value of $j$-th element when the game is started at the $i$-th position after $M$ rounds.

is there any closed form equation???

share|improve this question

1 Answer 1

In principle there is, but in practice I doubt that there’s anything very useful.

It really suffices to solve the problem when $i=1$, since for any other value of $i$ we can simply relabel the children. If we start at position $1$, we can define $a_{kn+i}$ to child $i$’s number after $k$ rounds have been played. Then the rules ensure that $$a_{kn+i}=a_{(k-1)n+i}+a_{(k-1)n+i+1}+a_{kn+i-1}\;.\tag{1}$$ That is, child $i$’s number after $k$ rounds is his number after $k-1$ rounds plus child $(i+1)$’s number after $k-1$ rounds + child $(i-1)$’s number after $k$ rounds. (You can check that this works even when $i$ is $1$ or $n$.)

We can simplify $(1)$ to the homogeneous $n$-th order linear recurrence

$$a_m=a_{m-1}+a_{m-n+1}+a_{m-n}\;,\tag{2}$$

where the terms on the righthand side are in the opposite order from those in $(1)$. The general solution to this recurrence involves powers of the solutions of the auxiliary equation $$x^n-x^{n-1}-x-1=0\;,$$ and those solutions aren’t going to be at all nice.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.