0
$\begingroup$

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???

1 Answers 1

2

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.