On the Domino Ring

Consider $N$ vertices labelled $1, 2, 3, \ldots N$ . Let the edge joining two vertices, say $a$ and $b$ represent the domino $[a | b]$ . Once we draw all the edges, we will obtain a complete graph along with a loop on each vertex.

In the problem, a ring is defined as either a single domino, which is a single edge on our graph, or it is defined as a closed loop, which is a Eulerian cycle on our graph. To use minimum number as rings, there should be more Eulerian cycles and of bigger size.

---

When $N = 1$ , the graph obtained is a single loop. It corresponds to a single domino $[1|1]$ . Therefore $F(1) = 1$ .

For all odd integers $N$ , each vertex will be of even degree, and the graph is connected, so the entire graph is one Eulerian cycle; i.e. we can always find a path that starts and ends at the same vertex and uses each edge exactly once. Hence it is possible to use just one ring.

So, for all odd integers $N$ , $F(N) = 1$ .

---

When $N=2$ , the following graph is obtained.

There is no Eulerian cycle possible in this case, so we have to split it into three edges, so $F(2) = 3$ .

---

A connected graph is Eulerian iff each vertex has an even degree. If $N$ is even, then each vertex has an odd degree. By separating out alternate edges on the perimeter of the polygon , we are left with a Eulerian graph.

For example $N = 4$ . We remove the alternate red edges of the square, and now each vertex has an even degree. It is now a Eulerian graph.

For even integers $N \geq 4$ , $F(N) = 1 + \frac{N}{2}$ .

---

Therefore

$\begin{aligned} \displaystyle \sum _{n = 1} ^{2016} F(n) & = (F(1) + F(3) + F(5)+ \ldots + F(2015)) + F(2) + (F(4) + F(6) + \ldots + F(2016)\\ & = (1008 \times 1) + 3 + (1007 \times 1 + \frac{4}{2} + \frac{6}{2} + \ldots + \frac{2016}{2}) \\ & = 1008 +3 + (1007 + (2 + 3 + 4 + 5 +\ldots + 1008))\\ & = 1011 + 1007 + \frac{1008 \times 1009}{2} - 1\\ & = 2018 + 504 \times 1009 -1 \\ & \equiv 18 + 504 \times 9 - 1 \pmod{1000}\\ & \equiv 18 + 4536 - 1 \pmod{1000} \\ & \equiv \boxed{553} \pmod{1000} ~~~ _{\square} \\ \end{aligned}$

---

Please comment below if any step is not clear and I will explain it in detail.