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.

1317 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 Bob has a winning strategy.

This post has been edited 1 time. Last edited by Assassino9931, Apr 23, 2025, 4:03 PM

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 • 3 Y

Y by GoodGuy2008, sami1618, dgrozev

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

The post below has been deleted. Click to close.

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

2463 posts

#3 h Apr 23, 2025, 2:52 PM • 1 Y

Y by ayeen_izady

@above: It's ok, but why do you need a BFS tree? The job can be done using any spanning tree! Btw, your set $S$ is usually called "leaves".

This post has been edited 2 times. Last edited by dgrozev, Apr 28, 2025, 11:17 AM

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#4 h Apr 28, 2025, 11:33 AM

Y by

(Ilya Bogdanov) The required maximum is
$\frac1{\bigl\lfloor\frac{n+1}2\bigr\rfloor\cdot\bigl\lceil\frac{n+1}2\bigr\rceil} = \begin{cases} \frac{4}{(n+1)^2} & \text{ if } n \text{ is odd,}\\ \frac{4}{n(n+2)} & \text{ if } n \text{ is even,} \end{cases}$ and is achieved by the tree described at the end of the solution.

Consider the number $r_i$ Alice assigns to vertex $X_i$ . If she replaces her graph by some of its spanning trees, that makes Bob's job just harder, so we assume she draws a tree.
Now, assume that she has drawn a graph and assigned some numbers $r_i$ to vertices. We show how to modify those numbers to make Bob's job not easier.
Consider every leaf $X_i$ with $i>0$ , and assign it the sum of the numbers on the (unique) path from $X_0$ to $X_i$ ; all other numbers are replaced by zeroes. Then Bob's sum on every path does not increase. On the other hand, every number at a vertex is accounted for at least one leaf, so the sum of the numbers does not decrease. Now Alice may decrease the numbers at the leaves so as to fulfil the condition on the sum.

The problem now reads: Consider a tree on $n$ vertices rooted at $X_0$ . Let $L_1,\dots,L_k$ be the leaves of this tree different from the root, and let $d_i$ be the number of vertices of the path from $X_0$ to $L_i$ . We are to choose non-negative numbers $s_1,\dots,s_k$ adding up to $1$ so as to minimize the quantity
$r=\max_{1\leq i\leq k} \frac{s_i}{d_i}.$ Let $d=\max_i d_i$ ; without loss of generality, let $d=d_1$ . Then the path from $X_0$ to $L_1$ has $d-1$ vertices distinct from the $L_i$ , so $k\leq n-(d-1)$ . Hence
$r\geq \frac1k \sum_{i=1}^k \frac{s_i}{d_i}\geq \frac 1{dk}\sum_{i=1}^k s_i=\frac1{dk}\geq \frac1{d(n-d+1)}\geq \frac1{\bigl\lfloor\frac{n+1}2\bigr\rfloor\cdot\bigl\lceil\frac{n+1}2\bigr\rceil}.$ Equality is achieved, if, say, $d=\left\lceil\frac{n+1}2\right\rceil$ , and the graph consists of a path of length $d-1$ , one of whose endpoints is $X_0$ , and to the other $n-d+1=\left\lfloor\frac{n+1}2\right\rfloor$ leaves are attached. Each of those leaves should be assigned the number $1/(n-d+1)$ , while all other vertices are assigned zeroes.

Remark. When I proposed this problem, I hadn't expected it would be selected as p6. One can see the originally proposed solution as well as some further comments in my blog.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a