Bariz - Problem

Source: 2017 Peru Ibero TST P3

Tags: combinatorics

hectorleo123

22.08.2023 04:37

We have a table in the form of a regular polygon with $1000$ sides, where each side has length $1$. At one of the vertices is a beetle (consider this vertex to be fixed). The $1000$ vertices must be numbered, in some order, using the numbers $1, 2,\ldots ,1000$ such that the beetle is at vertex $1$. The beetle can only move along the edge of the table and always moves clockwise. The beetle moves from vertex $1$ to vertex $2$ and stops there. then it moves from vertex $2$ to vertex $3$, and stops there. So on, until the beetle ends its journey at vertex $1000$. Find the number of ways the numbers can be assigned to the vertices so that the total length of the beetle's journey is $2017$.

Let $v_i$ denote the $i$-th vertex counted clockwise from $1$. The beetle will travel around the polygon for $2$ times and then stop at $v_{17}$ since the total length of its journey is $2017$. Therefore, $v_1, v_2, \dots, v_{16}$ will be passed through for $3$ times, and the beetle can choose to stop at each vertex in the first, second, or third time. $v_{18}, v_{19}, \dots, v_{99}$ will be passed through for $2$ times, and the beetle can choose to stop at each in the first or second time. $\therefore$ there are $3^{16}\times2^{82}$ ways to choose the stopping time of all vertices. Since each choice of the stopping time of all vertices uniquely determined the stopping orders of the vertices (which are the numbers on the vertices), the number of ways the numbers can be assigned to the vertices is also $3^{16}\times2^{82}$.