European Mathematical Cup 2016 senior division problem 2

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

European Mathematical Cup 2016 senior division problem 2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

351 posts

#1 h Dec 31, 2016, 2:30 PM • 1 Y

Y by Adventure10

For two positive integers $a$ and $b$ , Ivica and Marica play the following game: Given two piles of $a$
and $b$ cookies, on each turn a player takes $2n$ cookies from one of the piles, of which he eats $n$ and puts $n$ of
them on the other pile. Number $n$ is arbitrary in every move. Players take turns alternatively, with Ivica going
first. The player who cannot make a move, loses. Assuming both players play perfectly, determine all pairs of
numbers $(a, b)$ for which Marica has a winning strategy.

Proposed by Petar Orlić

This post has been edited 2 times. Last edited by steppewolf, Jan 1, 2017, 1:17 PM

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#3 h Dec 31, 2016, 6:44 PM • 2 Y

Y by Adventure10, Mango247

We will show that Marica has winning strategy iff $|a-b|\leqslant 1$ by induction on $a+b$
In other words, $|a-b|\leqslant 1$ is losing position; the player who receive it has no wining strategy.
The base case is obvious.
For induction step, suppose the statement is true for $a+b\leqslant t$ .
Consider when Ivica start with two piles of $a$ and $b$ that $|a-b|\leqslant 1$ and $a+b=t+1$
We have two cases:

$t+1$ is even. We get that $a=b=(t+1)/2$ .
Then Ivica will take $2n$ cookies and the numbers of cookies in two piles become $a'=(t+1)/2+n$ and $b'=(t+1)/2-2n$ .
is odd. WLOG that $a=(t+2)/2,b=t/2$ . We have two sub-cases
- Ivica take $2n$ cookies from the $a$ -cookie pile.
  The number of cookies become $a'=(t+2-4n)/2$ and $b'=(t+2n)/2$ .
- Ivica take $2n$ cookies from the $b$ -cookie pile.
  The number of cookies become $a'=(t+2+2n)/2$ and $b'=(t-4n)/2$ .

In both cases, we have $|a'-b'|> 1$ and $a'+b'\leqslant t$ .
By induction hypothesis, this situation is a winning position, so Marica has the winning strategy.

We also have to show that when $|a-b|>1$ and $a+b=t+1$ , Ivica have winning strategy.
WLOG $a>b$ . Let $a=b+k$ , then take $2m=2\lfloor (k+1)/3 \rfloor$ cookies from $a$ -cookie pile.
This yields $|a'-b'|=|(b+k-2m)-(b+m)|=|k-3m|\in \{ -1,0,1\}$ and $a'+b'=t+1-m\leq t$ .
Again, by induction hypothesis, this situation is a losing position, so Ivica has the winning strategy.

This post has been edited 3 times. Last edited by ThE-dArK-lOrD, Jan 17, 2019, 2:44 PM

Z K Y

The post below has been deleted. Click to close.

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

477 posts

#4 h Jan 1, 2017, 1:02 PM • 2 Y

Y by Adventure10, Mango247

Happy 2017!

Basically its all about guessing the correct answer. To do so I basically bashed all such pairs with $max(a,b)\le 6$ , failed a few conjectures with counterexamples, and arrive at the final answer. Once you guessed it correctly its quite trivial.

The answer is all $|a-b|\le 1$ . It is clear that $(1,0), (1,1)$ are both good. Now the winning strategy given any pair $(a,b)$ with $|a-b|\ge 2$ is to choose some $n\ge 1$ s.t $|(a-2n)-(b+n)|=|a-b-3n|\le 1$ or $|(a+n)-(b-2n)|=|a-b+3n|\le 1$ . You can choose to make a move at $a$ or $b$ , so we just assume that $n$ is any non-zero integer (then we make a move at $a$ or $b$ according to the sign of $n$ ). Such integer $n\neq 0$ is possible to choose since when you run the numbers $a-b+3n$ along the integers $n$ , exactly one such $n$ will have $a-b+3n$ falls either $-1, 0, 1$ .

Conversely, if $|a-b|\le 1$ , then no other integers $n\neq 0$ can give $a-b+3n$ equal to $-1, 0, 1$ , thus it falls off to bad numbers. So with this strategy, any player holding a good pair can give his enemy a bad number, and the enemy cannot retain a new bad pair for the player, so the player wins.

This post has been edited 1 time. Last edited by navi_09220114, Jan 1, 2017, 1:04 PM

Z K Y

The post below has been deleted. Click to close.

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

187 posts

#5 h Jan 16, 2019, 5:06 PM • 3 Y

Y by Aryan-23, Adventure10, Mango247

steppewolf wrote:

For two positive integers $a$ and $b$ , Ivica and Marica play the following game: Given two piles of $a$
and $b$ cookies, on each turn a player takes $2n$ cookies from one of the piles, of which he eats $n$ and puts $n$ of
them on the other pile. Number $n$ is arbitrary in every move. Players take turns alternatively, with Ivica going
first. The player who cannot make a move, loses. Assuming both players play perfectly, determine all pairs of
numbers $(a, b)$ for which Marica has a winning strategy.

Proposed by Petar Orlić

Here’s my solution.

We claim that Marica can win iff $|a-b| \leq 1$ .

Call a position good if $|a-b| \leq 1$ at that instant. Else call it bad.

CLAIM 1: A person in a bad position must always leave behind a good position to the opponent.

PROOF: Suppose there are $(a,b)$ cookies obeying $|a-b| \leq 1$ in piles $A,B$ respectively. Suppose the person removes $2k$ cookies from one pile and stacks $k$ in another. WLOG, let the unlucky pile ( the one from which cookies are removed ) be $A$ . So $(a,b) \rightarrow (a-2k,b+k)$ . Thus $|a-2k-b+k| > 1$ .

CLAIM 2: A person in a good position can leave behind a bad position for the opponent.

PROOF: Suppose there are $(a,b)$ cookies obeying $|a-b| \leq 1$ in piles $A,B$ respectively. The person can then choose some $n\ge 1$ s.t $|(a-2n)-(b+n)|=|a-b-3n|\le 1$ or $|(a+n)-(b-2n)|=|a-b+3n|\le 1$ . This is possible since $|a-b| \geq 2$ .

CLAIM 3: A person in a good position can never lose.

PROOF: Note that a person in a good position can ever have $|a-b| \leq 1$ by definition. So, that person. Note that a person loses iff $|a-b| \leq 1$ in his turn at some point of time ( more strongly iff $(a,b) = (1,0),(1,1),(0,0),(0,1)$ at some point of time ). By Claim $1$ and Claim $2$ , we can easily see that Claim $3$ follows.

Thus, our desired conclusion follows from these $3$ claims.

This post has been edited 2 times. Last edited by MathInfinite, Feb 13, 2019, 10:14 AM

Z K Y

The post below has been deleted. Click to close.

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

1184 posts

L567

#6 h Apr 26, 2021, 10:04 AM • 3 Y

Y by Mango247, Mango247, Mango247

Nice problem. In my opinion, the only difficulty of the problem is guessing when Marica can win, which can only be done by bashing out the first few cases, then you realise that only when the number of cookies in both piles is almost same, only them Marica wins. Once you figure out the answer, proving it works is pretty easy.

Call the piles of cookies $\emph{nice}$ if the number of cookies differ by at most $1$ and $\emph{horrible}$ otherwise

The answer is that Marica can win if and only if the piles are nice.

Suppose the piles have $a,b$ cookies respectively and $|a-b| \le 1$ . Then, Ivica can change it from $(a,b) \rightarrow (a-2n, b+n)$ . Then, Marica removes $2n$ cookies from the second pile to change it $(a-2n, b+n) \rightarrow (a-n, b-n)$ , which is also nice. So, Marica can always ensure that the piles after her turn are nice i.e. she only plays when the piles are horrible. But if the piles are horrible, then some pile has to have at least $2$ cookies more than the other one and so Marica can always play. So, Marica cannot lose and since the number of cookies strictly decreases every move, Marica must eventually win.

Now, suppose the piles of cookies are horrible. I will show that Ivica can convert this piles into nice ones, in which case the roles of Marica and Ivica will be swapped, and so Ivica will win by using the strategy shown above.

Suppose the number of cookies in the piles are $(a+n,a)$ with $n \ge 2$ . If $n = 3k$ , then remove $2k$ from $a+n$ to convert $(a+n, a) = (a+3k,a) \rightarrow (a+k, a+k)$ , which is indeed a nice pair of piles.

If $n = 3k+1$ , then Ivica does $(a+3k+1, a) \rightarrow (a+k+1, a+k)$ by removing $2k$ cookies from the first pile.

If $n = 3k+2$ , then Ivica does $(a+3k+2, a) \rightarrow (a+k, a+k+1)$ by removing $2k+2$ cookies from the first pile. Therefore, Ivica can always convert horrible piles into nice ones and win.

So, Marica wins if and only if the piles are $\emph{nice}$ i.e. the number of cookies in the piles differ by at most $1$

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

389 posts

alexanderhamilton124

#7 h Sep 20, 2024, 10:51 AM • 1 Y

Y by L13832

Claim 1: If $a = b$ , then Marica wins.
Note that Marica wins for the case $\{1, 1\}$ , as well as for the case $\{2, 2\}$ , so say she wins for $\{1, 1\}, \dots, \{k - 1, k - 1\}$ , where $k \geq 3$ . We now prove Marica wins for $k$ as well. Say Ivan performs a move, making the cookies in each pile to $\{k - 2x, k + x\}$ . Now, Marica simply turns this set to $\{k - x, k - x\}$ , and since $k - x \leq k - 1$ , we are done by our inductive hypothesis (along with the fact that it is Ivan's move again).

Claim 2: If $a, b$ are consecutive, then Marica wins as well.
Note that Marica wins for $\{1, 2\}$ , as well as $\{2, 3\}$ . Say Marica wins for $\{1, 2\}, \dots, \{k - 1, k\}$ , where $k \geq 3$ . We now prove Marica wins for $\{k, k + 1\}$ as well. Say Ivan performs a move, making the cookies in each pile to $\{k - 2x, k + 1 + x\}$ . Now, Marica just reduces it to $\{k - x, k + 1 - x\}$ , and since it's a smaller set of consecutive numbers we are done by our inductive hypothesis (if Ivan performs $k + x, k + 1 - x$ , just replicate our method).

Claim 3: If none of these are true, then Ivan wins. (WLOG $a > b$ here)
If $3\mid a - b$ , take $x = \frac{a - b}{3}$ , and Ivan just performs the move $a - 2x, b + x$ , reducing it to $\{\frac{a + 2b}{3}, \frac{a + 2b}{3}\}$ , which are equal, so Ivan can just play as Marica here and win the game.

If $a - b \equiv 1\mod{3}$ , take $x = \frac{a - b - 1}{3}$ , yielding $\{\frac{a + 2b + 2}{3}, \frac{a + 2b - 1}{3}\}$ , which are consecutive so Ivan just plays as Marica again, winning him the game.

If $a - b \equiv 2\mod{3}$ , take $x = \frac{a - b + 1}{3}$ , giving $\{\frac{2a + b - 1}{3}, \frac{2a + b + 2}{3}\}$ , which are consecutive so Ivan wins again.

Therefore, our answer is when $a = b$ , or when $a, b$ are consecutive.

Z K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

99 posts

SimplisticFormulas

#8 h Apr 2, 2025, 8:58 AM

Y by

yay here from rushils book

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a