Combinatorics game

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

Combinatorics game

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: First JBMO TST of France 2020, Problem 1

The post below has been deleted. Click to close.

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

1388 posts

#1 h Mar 4, 2020, 6:52 PM • 3 Y

Y by MathsMadman, mathematicsy, cubres

Players A and B play a game. They are given a box with $n=>1$ candies. A starts first. On a move, if in the box there are $k$ candies, the player chooses positive integer $l$ so that $l<=k$ and $(l, k) =1$ , and eats $l$ candies from the box. The player who eats the last candy wins. Who has winning strategy, in terms of $n$ .

This post has been edited 2 times. Last edited by VicKmath7, Mar 11, 2020, 11:19 AM

Z K Y

The post below has been deleted. Click to close.

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

816 posts

#2 h Oct 23, 2020, 4:28 PM • 2 Y

Y by MathsMadman, cubres

For odd $n$ the first player chooses $n-2$ candies and eat them so he wins(except for $n=1$ where he obviously wins).for even $n$ first player should take odd number of candies so he will become second player and $n$ will be odd.So first player wins iff $n \equiv 1 \pmod 2$ .

Z K Y

The post below has been deleted. Click to close.

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

168 posts

#3 h Dec 17, 2024, 3:35 PM • 1 Y

Y by cubres

Easy:::
There are two cases:::
$\boxed{1}n$ is odd number.

LEMMA:For odd $n$ , $(n,n-2)=1$
Using that the first player eats $n-2$ candles there are $2$ candles remained.Second eats 1 and first eats the last one and wins.

$\boxed{2}n$ is even.
Notice First player should and will take an odd number of candles.Now second player continues to the game as first player and takes $n-k-2$ candles and wins...
So:::
$\mathcal{WINNER}=\begin{cases}First\to n=2k+1\\ Second\to n=2k\end{cases}$
$\boxed{\lambda}$

Z K Y

The post below has been deleted. Click to close.

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

25 posts

#4 h Apr 12, 2025, 6:56 PM • 1 Y

Y by cubres

We claim that the first player will win iff $n \equiv 1 \pmod 2$ , and the second player winning for even $n$ . The first player clearly wins for $n =1$ , and for odd $n\ge 1$ they simply take $n-2$ candies with there being $2$ left. The second player eats one and thus the first player wins.
For even $n$ the first player takes an odd number of candies due to the nature of the game. This results in the second player playing with the first instance of odd $n$ . This results in them winning.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a