Coins in a circle

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Coins in a circle

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Pan-American Girls’ Mathematical Olympiad 2021, P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

122 posts

#1 h Oct 6, 2021, 10:16 PM • 2 Y

Y by FaThEr-SqUiRrEl, LawofCosine

There are $n \geq 2$ coins numbered from $1$ to $n$ . These coins are placed around a circle, not necesarily in order.

In each turn, if we are on the coin numbered $i$ , we will jump to the one $i$ places from it, always in a clockwise order, beginning with coin number 1. For an example, see the figure below.

Find all values of $n$ for which there exists an arrangement of the coins in which every coin will be visited.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

49 posts

jampm

#2 h Oct 6, 2021, 11:32 PM • 2 Y

Y by JuanDelPan, FaThEr-SqUiRrEl

This problem is basically equivalent to this other two...
Canada 2013/2 (just add an $a_0 = 1$ and shift everything) and Russia 1995 .
Anyways haha, here's a (very lazy) sketch of my solution:
solution sketch

This post has been edited 1 time. Last edited by jampm, Oct 7, 2021, 1:04 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11136 posts

#3 h Oct 7, 2021, 12:17 AM • 2 Y

Y by FaThEr-SqUiRrEl, megarnie

There are $n \geq 2$ coins numbered from $1$ to $n$ . These coins are placed around a circle, not necessarily in order.

In each turn, if we are on the coin numbered $i$ , we will jump to the one $i$ places from it, always in a clockwise order, beginning with coin number 1. For an example, see the figure below.

Find all values of $n$ for which there exists an arrangement of the coins in which every coin will be visited.

https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvOC9jL2E0ZDRhNDVhNDY2MDdjOTVhYTMyYzk3YzFkZjhiOWVhYTYwZDdhLnBuZw==&rn=U2NyZWVuIFNob3QgMjAyMS0xMC0wNiBhdCAxNy4xMy4xNS5wbmc=

This post has been edited 1 time. Last edited by jasperE3, Oct 7, 2021, 12:17 AM
Reason: posting for collection

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#4 h Oct 7, 2021, 10:23 AM

Y by

Clearly the last coin visited is numbered $n$ , after which the moves clearly consist on staying in place indefinitely. The sum of total moves (regardless of their order) until we reach the coin numbered $n$ is $1+2+\cdots+(n-1)=\frac{(n-1)n}{2}$ .

If $n$ is odd, this is a multiple of $n$ , ie we have made $\frac{n-1}{2}$ full turns to the arrangement. Or the starting coin is numbered both $n$ and $1$ , contradiction. Thus no such arrangement exists for odd $n$ .

If $n$ is even, we can place the coins such that we visit them in order $1,p-2,3,p-4,5,p-6,\dots$ . Using cyclic notation and assuming that coin numbered $1$ is located at position $0$ , this means that coin $n-2k$ is located at position $k$ for $k=1,2,\dots,\frac{n}{2}-1$ and coin $2k+1$ is located at position $-k$ for $k=0,1,\dots,\frac{n}{2}-1$ . Setting coin numbered $n$ in position $\frac{n}{2}$ , clearly all $n$ positions in the coin arrangement are assigned a coin with a distinct number, and hence all $n$ numbered coins are assigned to a different position. By trivial induction we can show that after $2k$ moves we are at position $-k$ on coin numbered $2k+1$ , and after $2k+1$ moves we are at position $k+1$ on coin numbered $n-2k-2$ , and we are done.

This post has been edited 1 time. Last edited by daniel73b, Oct 7, 2021, 10:24 AM
Reason: Clarity

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#6 h Oct 26, 2022, 3:23 AM • 2 Y

Y by HamstPan38825, NicoN9

Because the coin $n$ is a sink, a valid path must start at $1$ , visit every other coin in $\{2,\dots,n-1\}$ exactly once, and finally end at coin $n$ . The total distance traveled before reaching $n$ is $1+2+\dots+(n-1) = \frac{1}{2} n (n-1)$ . This means that

When $n$ is odd, the total distance is a multiple of $n$ , but that's impossible as $1$ and $n$ don't occupy the same place.
When $n$ is even, it hints that any valid construction must start with $1$ diametrically opposite $n$ and wind around exactly $\frac{1}{2} n$ times.

For the construction, see the following example for $n=20$ which obviously generalizes to any even $n$ .
$[asy] size(7cm); defaultpen(fontsize(18pt)); draw(unitcircle); for (int i=1; i<=9; ++i) { dot("$"+(string)(2*i)+"$", dir(270+18*i), dir(270+18*i), blue); dot("$"+(string)(2*i+1)+"$", dir(90+18*i), dir(90+18*i), deepcyan); } dot("$1$", dir(90), dir(90), red); dot("$20$", dir(-90), dir(-90), red); [/asy]$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#7 h Nov 19, 2022, 10:54 PM • 2 Y

Y by centslordm, itslumi

We claim only even $n$ work. Notice we must visit $n$ last, and that we cannot visit a coin twice before repeating, so we must move $1+2+\dots+n-1=n(n-1)/2$ before getting to $n.$ If $n$ is odd, this implies that the first coin has value $n,$ which is absurd.

For $n=2k,$ the following construction works: $1,2k-2,2k-4,\dots,4,2,2k,2k-1,2k-3,\dots,5,3$ going clockwise. This works as we go $1\rightarrow 2k-2\rightarrow 3\rightarrow 2k-4\rightarrow 5\rightarrow\dots\rightarrow 2\rightarrow 2k-1\rightarrow 2k,$ reaching all the coins. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

#8 h Nov 27, 2022, 9:49 PM

Y by

Rigor:
We claim the answer is all even $n$ . Denote the $n$ coin positions around the circle as $0, 1, \dots, n - 1$ in clockwise order. Let $c_i$ denote the value of the coin in position $i$ , and $p_i$ denote our position after the $i$ -th move. WLOG $p_0 = 0$ and $c_0 = 1$ , and note on each turn if we are at position $p_i$ , we jump to position $p_{i + 1} = (p_i + c_{p_i} \mod n)$ . Hence note
$p_{i + 1} = \left (p_0 + \sum_{k = 0}^i c_{p_k} \mod n \right )$ Then we visit every coin if and only if $p_0, p_1, \dots, p_{n - 1}$ are distinct. The if direction is because we visit $n$ distinct positions, which must be the $n$ distinct coins. only if is because, if $p_a = p_b$ for some $n - 1 \geq a > b \geq 0$ , note we will repeatedly visit the sequence $(p_a, p_{a + 1}, \dots, p_{b - 1})$ , and never visit any new coins we have yet to visit. We prove that if $n$ is odd, we can never visit all the coins. Assume we can. Note if $c_{p_i} = n$ for some $i < n - 1$ , then $p_{i + 1} = (p_i + c_{p_i} \mod n) = p_i$ . However, there must be $i \in \{0, 1, \dots, n - 1\}$ such that $c_{p_i} = n$ , since we can visit the coin with value $n$ . Then $c_{p_{n - 1}} = n$ . Thus $\{c_{p_0}, c_{p_1}, \dots, c_{p_{n - 2}}\} = \{1, 2, \dots, n - 1\}$ . Hence
$p_{n - 1} = \left ( p_0 + \sum_{i = 0}^{n - 2} c_{p_{i}} \mod n \right )$ $p_{n - 1} = \left (\frac{(n - 1)n}{2} \mod n \right ) = 0$ Thus $p_{n - 1} = p_0$ , contradiction. Now we prove that we can visit all coins if $n$ is even. We set $c_{p_{n - 1}} = n$ and $(c_{p_0}, c_{p_1}, c_{p_2}, c_{p_3}, \dots c_{p_{n - 2}}) = (1, n - 2, 3, n - 4, \dots, n - 1)$ , where $c_{p_i} = 2i - 1$ and $c_{p_i} = n - i - 1$ when $i$ is even and odd respectively. Then we are done if $p_0, p_1, \dots, p_{n - 1}$ are distinct. If $p_a = p_b$ for $0 \leq a, b \leq n - 1$ ,
$p_a = \left ( p_0 + \sum_{i = 0}^{a - 1} c_{p_{i}} \mod n \right ) = p_b = \left ( p_0 + \sum_{i = 0}^{b - 1} c_{p_{i}} \mod n \right )$ $\iff f(a - 1) \equiv f(b - 1) \pmod{n}$ Where $f(x) = \sum_{i = 0}^x c_{p_{i}}$ evaluates to $n - \frac{x + 1}{2}$ when $x$ is odd and $\frac{x}{2} + 1$ when $x$ is even. If $a - 1$ and $b - 1$ are of the same parity, clearly $a - 1 \equiv b - 1 \pmod{n} \implies a = b$ . If WLOG $a$ is even and $b$ is odd,
$p_a = p_b \iff f(a - 1) \equiv f(b - 1) \iff \frac{a + b - 1}{2} + 1 \equiv 0 \pmod{n}$ $\iff a + b + 1 \equiv 0 \pmod{2n}$ However, $a + b + 1 \leq (n - 2) + (n - 1) + 1 < 2n$ . Thus $p_a = p_b \iff a = b$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#9 h Dec 18, 2022, 11:37 PM • 1 Y

Y by bjump

The answer is even $n$ only. The problem is equivalent to there existing a sequence of jumps that visits every coin without visiting any coin twice.

Necessarity: Notice that we cannot jump to a coin numbered $n$ until the very last move using our reformulation: therefore, the total distance jumped between the first move and last is $\frac{n(n-1)}2$ . When $n$ is odd, this is divisible by $n$ , which means we always land on $1$ on our final move. But this implies that there must exist a coin that we have never visited at this point.

Sufficiency: On move $i$ , let the coin we visit be numbered $i$ if $i$ is odd, and $n-i$ if $i$ is even. Then the indices of the coins we land on (labeling the first index $1$ ) are $1, 2, 0, 3, n-1, 4, n-2, \cdots$ . After $n-1$ jumps, this visits all coins, as needed.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

315 posts

#10 h Jun 11, 2024, 1:45 AM

Y by

We claim the answer is all even $n \ge 2$ . As a construction, the cycle in order $1, 3, 5, \dots, n - 1, 2, 4, \dots, n$
works. To show odd $n$ do not work, note that we must visit the coin labelled $n$ last as otherwise we are caught in a cycle. But $n \mid 1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$ , so the coin labelled $n$ coincides with $1$ in the circle, which is invalid. We are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

559 posts

cursed_tangent1434

#11 h Jun 11, 2024, 5:32 AM

Y by

Solved with a small hint. The answer is all even $n$ .

We first see why all odds do not work. Let a cycle be a sequence of moves where we start from coin $1$ and reach coin $n$ for the first time. Then, in a cycle, no coin can be visited twice, since if some coin were visited twice, the sequence of moves would loop from then on. Further, all the coins must be visited exactly once in a cycle, since once we land on coin $n$ , we keep looping in the same place without visiting any other coins. Thus, the coins visited (in some order) before visiting $n$ for the first time are $1$ , $2$ , $\dots (n-1)$ . Further, the magnitude of the 'jumps' done before visiting $n$ for the first time must also be $1,2,\dots , (n-1)$ in some order. But then, we would have a total displacement of
$1+2+\dots +n =\frac{(n-1)n}{2}$ which is clearly divisible by $n$ for odd $n$ . But then, before we reach $n$ we would have loop backed to our starting position (coin 1) which is a clear contradiction to the fact that in a cycle, no coin is visited twice.

To see why all evens work, simply consider the following placement of coins (going clockwise).
$(1,2n-2,2n-4,\dots , 2 , 2n , 2n-1, 2n-3, \dots , 3)$ Here, we will quite clearly move in the following order $1\rightarrow 2n-2 \rightarrow 3 \rightarrow 2n-4 \rightarrow \dots \rightarrow 2 \rightarrow 2n-1 \rightarrow 2n$ visiting every coin in the process.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1318 posts

#12 h Jul 19, 2024, 4:46 AM

Y by

Only all even $n$ work. Our construction for even $n$ is(in clockwise order) $(1, n-2, n-4, \dots, 2, n, n-1, n-3, \dots, 3)$ which clearly works since $n-2$ will go to $3$ , $3$ will go to $n-4$ and so on until we get to the middle( $n$ ).
Clearly we cannot land on coin $n$ before another coin, since we will be stuck on $n$ and we will not be able to move.
So we must go through coins $1$ , $2$ , $\dots$ , $n-1$ before $n$ , so we move a distance of $\frac{n-1(n)}{2}$ which is divisible by $n$ . So then after going through all of $1$ , $2$ , $\dots$ , $n-1$ we will land on $1$ again so we get stuck in a loop without $n$ , impossible.

This post has been edited 1 time. Last edited by dolphinday, Jul 19, 2024, 4:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

22 posts

#13 h Jul 22, 2024, 1:29 PM

Y by

\begin{claim}
We claim only even n works.
\end{claim}
Define a cycle to start from $1$ and end at $n$ . In a cycle you can only visit a coin once as if it was otherwise, the sequence of moves would then loop.
All coins must be visited must be visited once as if $n$ is visited twice, the sequence would stagnate at $n$ .
This implies that the order of coin visitations must be $1$ , $2$ , $\cdots$ , $n$ . The total distance travelled when performing the moves is simply $1+2+$ , $\cdots$ , $n = \frac{n(n-1)}{2}$ . For odd $n$ (i.e ) $n\equiv 2m+1 \; \text{for arbitrary m} \in \mathbb Z^+$ the total distance is divisible by $n$ which is absurb as it would imply $1$ and $n$ would occupy the same spot in the circle.

We now prove that $n$ even works. The configuration that can be generalised is as: $1$ , $n-2$ , $n-4$ , $\cdots$ , $2$ , $n$ , $n-1$ , $n-3$ , $\cdots$ , $3$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#14 h Aug 1, 2024, 6:56 PM

Y by

The answer is all even $n.$ For the construction, if $n = 2k,$ label the numbers on the circle in clockwise order as $2k-2, 2k-4, \dots, 4, 2, 2k, 2k-1, 2k-3, \dots, 5, 3, 1.$ Our process then looks like $1 \to 2k-2 \to 3 \to 2k-4 \to 5 \to 2k-6 \to \dots \to 4 \to 2k-3 \to 2 \to 2k - 1 \to 2k.$
To prove that all odd $n$ don't work, write $n = 2k + 1.$ Note that if we visit the same coin twice before reaching every coin, then we get stuck in an infinite loop, causing failure. Thus we visit every coin exactly once. Then we travel a total of $1 + 2 + \dots + 2k+1 = (k+1)(2k+1)$ spots clockwise in total, and this brings us back to $1.$ However, once we visit coin $2k + 1,$ we get stuck there forever, so the only possibility is for coin $1$ to overlap with count $2k + 1,$ which is a contradiction.

Therefore, the only $n$ that work are even integers, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

D4N13LCarpenter

13 posts

D4N13LCarpenter

#15 h Jan 10, 2025, 7:23 PM • 1 Y

Y by Vahe_Arsenyan

Note that since landing on $n$ causes an infinite loop, the coin number $n$ must be the last to be visited. But then, the total distance jumped before visiting $n$ is $1+2+\dots+n=\frac{n(n-1)}{2}.$ If $n$ is odd, then we have $n\mid \frac{n(n-1)}{2}$ , which is a contradiction since this would imply that the coin number $1$ and the coin number $n$ are at the same position.
If $n$ is even, I claim that there is a valid construction. To do this, place the odds increasingly in one half, place the coin number $n$ and then the even coins increasingly on the other. Notice that this works because after every two jumps, we have moved one unit clockwise. Refer to the diagram below for more clarity.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

27 posts

#16 h Jan 30, 2025, 12:02 PM • 1 Y

Y by Kaus_sgr

storage

This post has been edited 3 times. Last edited by cosdealfa, Jan 31, 2025, 7:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

329 posts

#17 h Mar 26, 2025, 10:45 PM

Y by

The answer is all even $n.$

We first show all odd values don’t work.
First, note that if it reaches $n$ before all of the other ones, $1, 2, \dots, n - 1,$ then it becomes stuck at $n.$ Hence, it has to first go through $1, 2, \dots, n - 1.$ This implies it goes $\frac{1 + \dots + n - 1}{2} = \frac {n - 1}2n$ steps. However, $n\mid \frac{n-1}2n,$ so it loops back to 1. Contradiction.

To do the construction, simply take $1 \to 2k - 2 \to 3 \to 2k - 4 \to \dots \to 2\to2k-1\to2k$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a