Robot tries to get to (0,0) or (1,0)

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

Robot tries to get to (0,0) or (1,0)

G H J

Reveal topic tags

Combinatorial games

L

G H BBookmark kLocked kLocked NReply

Source: SMO Open 2019 Q3

The post below has been deleted. Click to close.

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

10 posts

prtQ

#1 h Jul 6, 2019, 7:21 AM • 1 Y

Y by Adventure10

A robot is placed at point $P$ on the $x$ -axis but different from $(0,0)$ and $(1,0)$ and can only move along the axis either to the left or to the right. Two players play the following game. Player $A$ gives a distance and $B$ gives a direction and the robot will move the indicated distance along the indicated direction. Player $A$ aims to move the robot to either $(0,0)$ or $(1,0)$ . Player $B$ 's aim is to stop $A$ from achieving his aim. For which $P$ can $A$ win?

Z K Y

The post below has been deleted. Click to close.

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

9657 posts

#2 h Jul 6, 2019, 8:05 AM • 2 Y

Y by Adventure10, Upwgs_2008

Solution

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#3 h Jul 6, 2019, 2:56 PM • 2 Y

Y by Adventure10, Mango247

Another possible solution goes by setting $S_n$ to be the set of points that are winnable in at most $n$ moves, and noting that $S_n$ consists of the midpoints of $S_0,\ldots, S_{n-1}$ , it is clear that $\cup_{n=0}^{\infty} S_n$ is exactly the solution set described above.

However, one cannot conclude that this is every possible $P$ since it is not true in general that if $A$ can win from $P$ in finitely many turns, then there is an $n$ such that $A$ will definitely win in $n$ moves. To illustrate, consider a game where $B$ chooses a positive integer $n$ , does nothing afterwards, and every turn $A$ gets to subtract $1$ off it and wins when the number is $0$ . Then although $A$ is guaranteed to win from the starting position in finitely many turns, no upper bound for the number of turns exists.

To fix this, consider a binary tree where the vertices are the current point the game is at, and the two descendants are the two possibilities given by the two possible directions $B$ can choose. Assuming $A$ is able to win from $P$ and plays optimally, every path then has finite depth. If there is no upper bound, then there are arbitrary large paths exists and so the graph is infinite. But by Kőnig's lemma there must exist an infinite path --- a contradiction. Hence every point $P$ will exists in $S_n$ for some $n$ 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.

341 posts

#4 h Jul 26, 2019, 9:38 AM • 2 Y

Y by Adventure10, Mango247

The following is essentially the above post restated, but it cleared up some confusion for me on why $\cup_{n=0}^{\infty} S_n$ isn't necessarily the set of winnable positions.

Suppose now there's a slightly different game:

modified game wrote:

A robot is placed at point $P$ on [...]. Two players play the following game. Before the game starts, player $B$ gives a positive integer $N$ . Player $A$ gives a distance and $B$ gives a direction and the robot will move the indicated distance along the indicated direction. Player $A$ aims to move the robot to either $(0,0)$ or $(1,0)$ . Player $B$ 's aim is to stop $A$ from achieving his aim, however, after $N$ turns player $B$ runs out of patience and forfeits the game. [...]

It turns out each $S_i$ in the modified game is the same as in the original game. However, all positions are now winnable, so the winnable set is not $\cup_{n=0}^{\infty} S_n$ .

Essentially, what must be shown is that in the original game, none of $B$ 's decisions (left/right) really have the "same impact" as picking $N$ in the modified game.

This post has been edited 1 time. Last edited by DVDthe1st, Jul 26, 2019, 9:40 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a