A game optimization on a graph

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

A game optimization on a graph

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Bulgaria National Olympiad 2025, Day 2, Problem 6

The post below has been deleted. Click to close.

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

1247 posts

#1 h Apr 8, 2025, 1:59 PM • 1 Y

Y by cubres

Let $X_0, X_1, \dots, X_{n-1}$ be $n \geq 2$ given points in the plane, and let $r > 0$ be a real number. Alice and Bob play the following game. Firstly, Alice constructs a connected graph with vertices at the points $X_0, X_1, \dots, X_{n-1}$ , i.e., she connects some of the points with edges so that from any point you can reach any other point by moving along the edges.Then, Alice assigns to each vertex $X_i$ a non-negative real number $r_i$ , for $i = 0, 1, \dots, n-1$ , such that $\sum_{i=0}^{n-1} r_i = 1$ . Bob then selects a sequence of distinct vertices $X_{i_0} = X_0, X_{i_1}, \dots, X_{i_k}$ such that $X_{i_j}$ and $X_{i_{j+1}}$ are connected by an edge for every $j = 0, 1, \dots, k-1$ . (Note that the length $k \geq 0$ is not fixed and the first selected vertex always has to be $X_0$ .) Bob wins if
$\frac{1}{k+1} \sum_{j=0}^{k} r_{i_j} \geq r;$ otherwise, Alice wins. Depending on $n$ , determine the largest possible value of $r$ for which Bobby has a winning strategy.

Z K Y

The post below has been deleted. Click to close.

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

32 posts

#2 h Apr 15, 2025, 6:30 AM • 2 Y

Y by GoodGuy2008, sami1618

Hopefully this is correct! I claim that the answer is: $\begin{cases}n=2k\implies r= \frac{1}{k(k+1)}\\n=2k+1\implies r=\frac{1}{(k+1)^2}\end{cases}$
WLOG assume that Alice makes a tree $T$ (a connected graph without cycles). Now use BFS starting from $X_0$ . Let $S$ be the set of vertices of $T$ that are not connected to any vertex below them. I claim that in the best strategy for Alice(worst case scenario for Bob) any vertex $X_i\not\in S$ should be labeled with $r_i=0$ . The proof of this claim is quite easy since when we have a vertex $X_i\not\in S$ such that $r_i=c>0$ we can turn $r_i$ into $0$ and add $c$ to vertices below $X_i$ (maybe more than one layer) that are in $S$ . Note that by doing this algorithm largest possible value for $r$ will be decreasing(not necessarily strictly decreasing). Hence we may assume that in the best strategy for Alice, our claim holds. Now I claim that the distance between any vertex in $S$ and $X_0$ should be a constant(every two vertices in $S$ should have equal distance to $X_0$ ). In order to prove this, assume that we have vertices $X_i,X_j\in S$ such that $d(X_i,X_0)>d(X_j,X_0)$ . in this case by deleting $X_i$ and putting it between $X_0$ and the second layer of our BFS Tree we will decrease $r$ . Thus by doing this process again and again we may assume that in the worst case scenario for Bob, all vertices in $S$ have equal distance to $X_0$ . Here is an example for this process:
$[asy] unitsize(2cm); pair A,B,C,D,E,F,G; A=(0,0); B=(0.5,-1); C=(-0.5,-1); D=(-1,-2); E=(0,-2); F=(1,-2); G=(1,-3); dot(A); label("$X_0$",A,dir(100)); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); draw(G--F--B--A);draw(A--C--D); draw(A--C--E); label("$X_i$",G,dir(270)); [/asy]$
The above tree turns into:
$[asy] unitsize(2cm); pair A,B,C,D,E,F,G; A=(0,0); B=(0.5,-1); C=(-0.5,-1); D=(-1,-2); E=(0,-2); F=(1,-2); G=(0,1); dot(A); label("$X_0$",G,dir(100)); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); draw(F--B--A--G);draw(A--C--D); draw(A--C--E); label("$X_i$",A,dir(180)); [/asy]$
So we finally have that the distance between any two vertices of $S$ and $X_0$ is equal. Since they are equidistant we may assume that their labeling numbers are equal. Thus $r_{i_1}=r_{i_2}=\ldots r_{i_{|S|}}=\frac{1}{|S|}$ . So the least value that Alice can bound is: $\frac{1}{|S|}\times\frac{1}{d}\ge\frac{1}{|S|}\times\frac{1}{n+1-|S|}\ge\begin{cases}n=2k\implies r\ge \frac{1}{k(k+1)}\\n=2k+1\implies r\ge\frac{1}{(k+1)^2}\end{cases}$ Which we used AM-GM for the last equality. And the structure is that the graph will be a path of length $\lfloor\frac{n}{2}\rfloor-1$ which the last vertex is connected to $\lceil\frac{n}{2}\rceil$ other vertices. Here is an example for $n=8$ :
$[asy] unitsize(1.5cm); pair A,B,C,D,E,F,G,H; pair A=(0,0);B=(0,-1);C=(0,-2);D=(0,-3);E=(1.5,-4);F=(0.5,-4);G=(-0.5,-4);H=(-1.5,-4); dot(A);dot(B);dot(C);dot(D);dot(E);dot(F);dot(G);dot(H); draw(A--B--C--D--F); draw(D--G); draw(D--H);draw(D--E);label("$r_1=0$",B,dir(180));label("$r_2=0$",C,dir(180));label("$r_3=0$",D,dir(180));label("$r_0=0$",A,dir(90));label("$r_4=\frac{1}{4}$",E,dir(270)); label("$r_5=\frac{1}{4}$",F,dir(270));label("$r_6=\frac{1}{4}$",G,dir(270));label("$r_7=\frac{1}{4}$",H,dir(270)); [/asy]$
Which gives $r=\frac{1}{20}$ for $n=8$ . Q.E.D $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a