Alice in Wonderland

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

Alice in Wonderland

G H J

Reveal topic tags

IMO Shortlist

IMO Shortlist 2019

combinatorics

G H BBookmark kLocked kLocked NReply

Source: ISL 2019 C8

The post below has been deleted. Click to close.

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

ilovemath04

70 posts

ilovemath04

#1 h Sep 22, 2020, 11:32 PM • 9 Y

Y by magicarrow, SnowPanda, fidgetboss_4000, Adventure10, centslordm, megarnie, Inconsistent, mathleticguyyy, AMR12

Alice has a map of Wonderland, a country consisting of $n \geq 2$ towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be “one way” only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns.

Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most $4n$ questions.

This post has been edited 2 times. Last edited by ilovemath04, Sep 22, 2020, 11:35 PM

Z K Y

The post below has been deleted. Click to close.

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

pinetree1

1207 posts

pinetree1

#2 h Sep 22, 2020, 11:32 PM • 7 Y

Y by tree_3, magicarrow, Adventure10, HamstPan38825, megarnie, centslordm, sabkx

Take the obvious graph interpretation. Alice starts with the empty graph, and as she asks questions, she adds directed edges.

At each point in time, keep track of three sets: $A$ , the set of vertices with out-degree $0$ ; $B$ , the set of vertices with out-degree $1$ ; and $C$ , the set of vertices with out-degree at least $2$ . Initially all vertices belong to $A$ . We outline a four-step procedure for Alice.

Step 1: Build a tree. Using the first $n-1$ questions, Alice builds a directed tree by repeating the following procedure:

Take $u, v\in A$ . Since $\operatorname{outdeg} u = \operatorname{outdeg} v = 0$ , Alice could not have asked the question $uv$ before.
Ask the question $uv$ ; WLOG the response is $u\to v$ .
Move $u$ from $A$ to $B$ , and keep $v$ in $A$ .

Every iteration, $|A|$ decreases by $1$ and $|B|$ increases by $1$ , so after $n-1$ questions, we have $|A| = 1$ and $|B| = n-1$ .

Claim: After Step 1, the graph has no cycles.

Proof. After we draw edge $u\to v$ , we never query $u$ again; hence no cycles can form. $\blacksquare$

Step 2: Kill $x$ . Let $x$ be the vertex that was still in $A$ after Step 1. We will now kill $x$ . While $x$ has out-degree $0$ or $1$ , repeat:

Take $v\in B$ such that $xv$ has not already been queried. If no such $v$ exists, stop.
Ask the question $xv$ .
- If the answer is $v\to x$ , then $v$ moves from $B$ to $C$ .
- Otherwise, $\operatorname{outdeg} x$ increases by $1$ and $v$ stays in $B$ .

If, after this process, $x$ still has out-degree $0$ or $1$ , then $x$ is Alice's desired vertex. Furthermore, at most $n-2$ questions have been asked in this step, so in total Alice has asked at most $(n-1)+(n-2) < 4n$ questions.

Otherwise, after $k$ questions, $x$ has moved to $C$ ; out of these, $k-2$ of the answers must have been $v\to x$ , so $k-2$ other vertices have been moved to $C$ . Thus, at this point, we have $|C| = k-1$ and $|B| = n-k+1$ , and $n+k-1$ questions have been asked.

Step 3: Clear the deck. Now we try to move the rest of the vertices from $B$ to $C$ . Just like in Step 1, repeat:

Take $u, v\in B$ where $uv$ has not been queried, and ask the question $uv$ .
WLOG the answer is $u\to v$ . Then $u$ is moved to $C$ , and $v$ stays in $B$ .

And now here's the key observation:

Claim: When this process terminates, we have $|B|\le 2$ .

Proof. If there are no unqueried edge $uv$ with $u, v\in B$ , either $|B| = 1$ or there is an edge between every two vertices in $B$ . So if $|B| = \ell \ge 3$ , then there must be $\tbinom{\ell}{2}$ edges between the vertices of $B$ ; but each vertex has out-degree $1$ , which forces $\ell \le 3$ .

Now assume $|B| = 3$ ; then the end state must be a $3$ -cycle $uvw$ . If any of these edges was added in Step 3 (say $u\to v$ ), then $u$ should be in $C$ , contradiction. Thus all $3$ edges must have been added in Step 1. But this is also impossible, since the graph after Step 1 was acyclic! $\blacksquare$

Each question in Step 3 moves $1$ vertex from $B$ to $C$ , so the number of questions asked in Step 3 is either $n-k$ or $n-k-1$ . Therefore, either $2n-1$ or $2n-2$ total questions have been asked after Step 3.

Step 4: Finish. Let $B = \{u, v\}$ (where $u = v$ if $|B| = 1$ ); now we just use at most $2n$ questions to query all edges involving $u$ and $v$ .

If either $u$ or $v$ remains in $B$ after these questions, Alice has shown that some vertex has out-degree at most $1$ .
Otherwise every vertex has moved to $C$ , meaning that every vertex has out-degree at least $2$ .

Thus Alice has completed her task in at most $(2n-1)+2n < 4n$ questions, and the proof is complete.

Remark: [Motivation] A natural idea is to combine Steps 1 and 3 --- just query two vertices $u$ and $v$ that both have out-degree at most $1$ . Unfortunately you can end up with $|B| = 3$ in a triangle, and this is fatal since you need to query all the edges with the triangle, which requires a total of $2n+3n+O(1)$ moves. Thus the main difficulty of the problem is dealing with such ``death triangles."

Another natural idea is to move vertices from $A$ to $B$ first as in Step 1, singling out a specific vertex $x$ left in $A$ . The key observation is that now every death triangle must contain $x$ . This allows for the main innovation in Step 2: we can gain information about $x$ (and thus about death triangles) and simultaneously kill other vertices, which allows for the $5n\to 4n$ optimization.

This post has been edited 1 time. Last edited by pinetree1, Sep 22, 2020, 11:33 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6874 posts

v_Enhance

#3 h Sep 22, 2020, 11:37 PM • 10 Y

Y by Mathematicsislovely, ProblemSolver2048, Math_olympics, v4913, Adventure10, HamstPan38825, megarnie, sabkx, Chiaquinha, mathfun07

The following solution was found with the Taiwanese observer Zhao Ting-Wei.
In what follows, we consider an initially empty graph $G$ on the set of $n$ vertices. During the game Alice will pick two vertices not connected by an edge, and the King will add a directed edge between them in one of the two directions. We say that a vertex is

dead if it has outdegree at least $2$ ;
almost dead if it has outdegree exactly $1$ ;
alive if it has outdegree exactly $0$ or $1$ ;
healthy if it has outdegree exactly $0$ .

Alice's goal is to achieve a graph in which either all vertices are dead, or some vertex is alive and has an edge joining in to all other vertices.
The strategy takes four steps.

Step 1: Repeatedly pick two healthy vertices and query them. This generates a directed tree $T$ , with $n-1$ almost dead vertices and a sink/root $v$ (the unique healthy vertex left).

Step 2: We then query the healthy vertex $v$ with every other vertex not already joined to it, until $v$ dies. In each move every vertex queried either dies, or has an edge pointing away from $v$ .
After Step 2, if $v$ is still alive, then it is the vertex Alice seeks. So we may assume $v$ died, and every other vertex is now almost dead or dead.

Step 3: We now repeatedly query pairs of almost dead vertices, until we can do this no more --- which means we have a set $S$ of living vertices with all edges within $S$ present.
Claim: [No triangle lemma] We have $|S| \le 2$ .
Proof. It's obvious $|S| < 4$ . We claim $S$ cannot be a triangle either. Indeed, if there was, some edge of the triangle would not be in our tree $T$ (since trees are acyclic!) and so one of the vertices in $S$ should have died. $\blacksquare$

Step 4: Up until Step 3, we never queried a vertex after it died, so we certainly have at most $2n$ questions asked (each outdegree is at most $2$ ). Now we query every vertex in $S$ with any vertices not already joined; this adds at most $2n$ questions as needed. If any vertex in $S$ is still alive they are the vertices Alice seeks; if not, all vertices are deceased, as needed.

Remark: The key difficulty of the problem is the possibility that $|S| = 3$ . Here is the motivation.
Consider what happens with a simple greedy algorithm: one replaces Step 1 and Step 2 with random queries between living vertices. It takes at most $2n$ questions to reach our set $S$ . However, it is possible that $|S| = 3$ , so we only get a bound of $2n + 3n = 5n$ .
Thus, what we need is some way to prevent the triangle from forming. The trick to doing so is Step 1, in which we essentially postpone any deaths until most vertices are almost dead (i.e.\ until Step 2). This counter-intuitive move is the biggest surprise of the problem, since in some sense Alice's goal is to kill vertices. But once it is done, Step 1 gives us the tree $T$ and already one cannot get a triangle of living vertices not using $v$ .
It's clear that at least $3n-9$ questions are necessary, for if Alice somehow started with a triangle and all other vertices are already dead, it would still take at least $3(n-3)$ queries to determine the answer. Since it is impossible to kill vertices without at least $2$ queries to them, we find that a valid solution must either avoid the triangle altogether, or perhaps guarantee that if a triangle is formed some of its vertices are already queried with the dead.

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#4 h Sep 22, 2020, 11:39 PM • 1 Y

Y by Adventure10

Call a vertex good if it has outdegree at most $1$ .

Initially label every vertex $0$ . Whenever we ask an edge, we increase the label on the tail by $1$ . In this way, the labels represent the outdegrees of the vertices in our asked subgraph.

Claim: We can ask $n-1$ questions to form a tree $T$ such that every vertex except one is labeled with $1$ , and the remaining vertex is labeled $0$ .

Proof: We induct on $n$ with the base cases of $n=1,2$ trivial. Indeed, if $n$ is even, select an arbitrary perfect matching and ask those edges. Apply the inductive hypothesis on the $n/2$ vertices that are labeled $0$ now to finish. If $n$ is odd, select an arbitrary matching with $(n-1)/2$ edges, and again apply the inductive hypothesis on the $(n+1)/2$ vertices labeled $0$ . This completes the proof. $\blacksquare$

Call the tree we obtain $T$ , and the distinguished vertex still labeled $0$ as $v$ . We have the following key observation (this is the main idea).

Lemma: There are at most $3$ good vertices, and if there are exactly $3$ , then they form a directed $3$ -cycle where one of the vertices is $v$ .

Proof: Note that any directed graph on four vertices has the property that at least one of its vertices has outdegree at least $2$ , so there are at most $3$ good vertices. Furthermore, if there are exactly $3$ , then they must form a directed $3$ -cycle.

Suppose none of them were $v$ . Then since $T$ is acyclic, one of the edges of the $3$ -cycle, say $a\to b$ would be outside $T$ . But $a$ already has an edge pointing out through $T$ , so $a$ has outdegree at least $2$ , so it can't be good. Thus, if we have three good vertices, at least one of them must be $v$ . $\blacksquare$

Let the vertices adjacent to $v$ in $T$ be in the set $D$ . Now test edges $vx$ where $x$ is outside of $D$ , and keep doing so until either $v$ is proven to have outdegree at most $1$ , or we test $k$ edges and prove that $x$ has outdegree at least $2$ .

Case 1: Suppose that $v$ is proved to have outdegree at most $1$ . Then, at most one vertex $y$ outside $D$ has an edge pointing from $v$ to $y$ , and all the other vertices out of $D$ are labeled at least $2$ . This took $n-1-|D|$ steps. Run the tree from the first claim on $D$ (there are no internal edges here yet), which takes $|D|-1$ steps and labels everything in $D$ $2$ except one vertex $z$ still labeled $1$ . Thus, we have narrowed down the good vertices to $\{v,y,z\}$ . We see that $v$ has already been proven to be good, so we just execute at most $2(n-1)$ more steps to prove $y$ and $z$ are good (or disprove), at which point we've found all the good vertices. This takes at most $(n-1)+(n-1-|D|-1)+(|D|-1)+2(n-1) = 4n-6$ steps, as desired.

Case 2: Suppose that $v$ is proved to have outdegree at least $2$ after $k$ steps. Thus, $k-2$ vertices are now labeled $2$ (besides $v$ ), and the remaining $n-k+1$ vertices are still labeled $1$ (this includes $D$ ). Since $v$ is not good, we see that there are at most $2$ good vertices.

Now consider just the subgraph with $n-k+1$ vertices. It already may have some leftover edges from $T$ . Note that every vertex has already been labeled as $1$ by $T$ . Now we'll show that we can narrow down the good vertices down to $3$ possibilities in $n-k-2$ steps. If there is any unasked edge between two vertices labeled $1$ , then ask it. Once we get down to the case where all the vertices labeled $1$ have all edges between them asked, then there at most $3$ such vertices, so we're done. Each step changed a label from $1$ to $2$ , and we stop with $3$ labels equal to $1$ , so the process took $n-k-2$ steps, as desired.

Consider the three vertices we get, $a$ , $b$ , $c$ . One of the edges $ab,ac,bc$ is outside of $T$ , so by previous logic, we can prove that one of the vertices is bad without asking any more edges. Now, we've narrowed down the good vertices to $2$ possibilities, and we may ask at most $2(n-1)$ questions to finish. This takes at most $(n-1)+k+(n-k-2)+2(n-1) = 4n-5$ steps, as desired. This completes the solution.

Remark: There is a really easy strategy to solve in $5n$ steps. Indeed, start with all labels as $0$ , and ask random edges between two vertices with label at most $1$ until we've narrowed down to $3$ possibilities (this takes at most about $2n$ steps). Now we can verify those $3$ remaining in at most $3n$ steps, so we're done.

The hard part is that checking the final $3$ takes at least $3n$ steps, so it seems that we have to narrow down to those $3$ in at most $n$ steps, which is basically impossible. But there is in fact another way, which is to do checking and finding simultaneously. The key insight is that $v$ is basically always good (if it's not, we have at most $2$ good and this case is just easy), so we can narrow down the others at the same time as checking $v$ , and this allows us to solve the problem.

Z K Y

The post below has been deleted. Click to close.

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

SnowPanda

186 posts

SnowPanda

#5 h Sep 23, 2020, 12:28 AM • 3 Y

Y by Adventure10, nixon0630, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

MarkBcc168

1595 posts

MarkBcc168

#6 h Sep 24, 2020, 1:58 PM • 4 Y

Y by magicarrow, Adventure10, tymo, jrsbr

In fact, the number $4$ cannot be replaced with any smaller constant, i.e. for any constant $c<4$ , Alice cannot accomplish his goal for all sufficiently large $n$ . In my opinon, this is much more interesting than the actual problem. Here is a proof found with YRNG-BCC168.

We claim that Alice cannot answer within $4n-O(\log n)$ moves. First, we state two easy graph theoretic facts.

Lemma: Let $G$ be a graph with $n$ vertices and $n-k$ edges. Then, $G$ contains at least $k$ connected components which is a tree.

Proof. Let $G_1,G_2,\hdots,G_{\ell}$ be all connected components of $G$ . Clearly $|V(G_i)|-|E(G_i)|\leq 1$ for each $i$ . But
$\sum_{i=1}^{\ell}|V(G_i)|-|E(G_i)| = n-(n-k)=k$ thus it's $1$ for at least $k$ indices of $i$ , i.e. $G_i$ is a tree for at least $k$ indices of $i$ . $\blacksquare$

Lemma: A directed tree $G$ must contains a vertex with outdegree $0$ .

Proof. Let $G$ have $n$ vertices and $n-1$ edges. Then, since the sum of outdegree is $n-1$ , at least one of the $n$ outdegrees must be zero, done. $\blacksquare$

Now we are ready to tackle the lower bound. Let the King of Heart's name be Bob. We will give a strategy for Bob to answer Alice's query so that she cannot achieve her goal.

First, Bob will answer first queries subject to the following condition.
- If Alice asks an edge joining two vertices in the same component, then Bob answers arbitrarily.
- Otherwise, if Alice asks an edge joining two components, then Bob answers the direction pointing to the smaller components. Ties are broken arbitraily.
One can check by induction that each vertex of the tree of size has indegree at most as follows: if Bob's moves joining component of size to size where $a\geq b$ , then the each vertex in the new tree has indegree at most
At this point, the graph has at least three components which is a tree. Thus by Lemma 2, we can pick a vertex from each component which have outdegree $0$ . Picking vertices from three such components gives $x_1,x_2,x_3$ , each with outdegree zero and indegree $O(\log n)$ . Label the other $n-3$ vertices $y_1,y_2,\hdots,y_{n-3}$ .
Next, Bob will answer the remaining queries by the following scheme.
- Answer directed edges $x_1\to x_2$ , $x_2\to x_3$ and $x_3\to x_1$ .
- Answer directed edges in form $y_j\to x_i$ where $i=1,2,3$ and $j=1,2\hdots,n-3$ . Call this type of edges yangie.
- Answer directed edges in form $y_i\to y_j$ arbitrarily.
Observe that at the end of the first stage, at most yangie edges has been queried.
Now we claim that Alice is required to check all yangie edges. Assume not, WLOG has not been checked. Then consider the graph defined by
- A directed cycle $x_1\to x_2\to x_3$ ,
- all yangie edges $y_j\to x_i$ except $x_1y_1$ , and
- edges in form $y_i\to y_j$ are directed according Bob's answers.
This graph is consistent with Bob's answer. However, flipping the directions of could change the answer from yes to no, which is a contradiction.

Hence for the second stage, Alice requires questions. In total, she requires questions.

This post has been edited 2 times. Last edited by MarkBcc168, Sep 24, 2020, 2:02 PM

Z K Y

The post below has been deleted. Click to close.

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

inge

8 posts

inge

#7 h Sep 25, 2020, 3:23 AM • 2 Y

Y by Adventure10, sabkx

Nice solution MarkBcc168
In the shortlist package, it was proved that the number of questions needed is at least $4n-3\log_2(n)-15$ and at most $4n-2\log_2(n)+1$ for $n\geq8$

Z K Y

The post below has been deleted. Click to close.

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

harrisp

6 posts

harrisp

#12 h Sep 25, 2020, 10:15 PM • 3 Y

Y by Hamel, Serpadinas, Adventure10

The following proof can be improved in many points but I have tried to keep it as simple as possible.
Let's call $f$ the Step 1 in #2. We can apply $f$ in an unconnected set of vertices and pinetree1 of the set by 1 except of one vertex (the winner).

Step 1: We apply $f$ one time ( $n-1$ questions).

Step 2: We connect the winner with other edges until it is dead (see @v_Enhance post) ( $k$ questions and as a result $k-2$ vertices dead beacuse every vertex except of the 2 that killed the winner have already one outgoing road), otherwise we found the vertex we wanted.

Step 3: Then, because the graph with the vertices that remain has no cycles we can divide it in 2 unconnected set of vertices (bipartite graph) and apply $f$ in each set (less than $n-1-(k-2)$ questions) and we are left with 2 vertices (all the other vertices increased their outgoing by 1 so they are dead), the two last winners with one outgoing vertex each.

Step 4: We just connect each of them with every other vertex they are not connected to find the answer (less than $2n$ questions).

In total: $n-1+k+n-1-(k-2)+2n=4n$ questions.

The solution with some adjustments can achieve at most $4n-\log n-O(1)$ questions but a comment in shortlist can achieve better so I am not gonna post it. My $f$ was something like a knock-out tournament but I prefered to use Step 1 of @pinetree1 because it was already written.

Z K Y

The post below has been deleted. Click to close.

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

dgrozev

2461 posts

dgrozev

#13 h Oct 4, 2020, 12:00 PM • 1 Y

Y by Adventure10

IMO 2019 only won with choosing C5 (IMO 2019 p3) instead of this one. For any fixed vertex, there is no chance to find out whether its out-degree is 2 or more with less than $n-2$ questions. So, upon first reading it seems the main difficulty lies in dropping the estimate from $O(n^2)$ to $O(n)$ . Surprisingly (and disappointing for me) it's very easy to construct an algorithm that does the job with less than $C\cdot n$ questions (e.g. $C=5$ ) and the main point is to optimize it and attain $C=4$ . (some more comments in my blog).
The essential point is phase 3 in the official solution, or step 2 in #3 in this thread (Evan Chen). It's curious to see how PSC graded both problems C5 (social network) and C8 (this one). One may see the document here. You see, the difficulty of this one was rated more than one point higher. I wonder why, but that was for good in the end.

This post has been edited 2 times. Last edited by dgrozev, Oct 4, 2020, 12:08 PM

Z K Y

The post below has been deleted. Click to close.

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

Supercali

1261 posts

Supercali

#14 h Oct 10, 2020, 7:02 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

EDIT: Just realized that my initial process, with a few modifications, gives the $4n$ bound,

Here is a 4 step process involving coloring that proves the bound. At every moment one vertex would be a "pivot".

Step 1: Red

Choose a random vertex to be the pivot. Do the following process: Query the edge between the pivot (call it $A$ ) and any non-red vertex (say $B$ ). If the edge is directed $A \rightarrow B$ then turn $A$ red, color edge $AB$ red and move pivot to $B$ . Else color $B$ red, color edge $AB$ red and don't change pivot. Keep doing this till we end up with $n-1$ red vertices and as many red edges. We have used $n-1$ queries.

Step 2: Reddish Blue

The pivot (call it $A$ ) currently is uncolored, and is adjacent to at least 1 red edge. Do the following process: Query the edge between $A$ and any non-blue vertex (say $C$ ) such that $AC$ is not red. If the edge is directed $A \rightarrow C$ then color $A$ as well as edge $AC$ red, else color $C$ as well as edge $AC$ blue (in both cases don't change the pivot). Suppose we create $k$ blue vertices before $A$ turns red. Then we require $k+1$ queries in this step.

Note that if we remove the pivot, the red edges form an acyclic graph. This is because the only way to form a cycle is if we query 2 red vertices.

Step 3: Blueish Red

Initially keep the same pivot as step 2. Do the following process: Query the edge between the pivot (call it $A$ ) and any non-blue vertex (say $B$ ) that is not adjacent to $A$ via a red edge. (note that after one point the pivot from Step 2 either turns blue or becomes the required vertex with at most 1 outdegree). If the edge is directed $A \rightarrow B$ then turn $A$ blue, color edge $AB$ blue and move pivot to $B$ . Else color $B$ blue, color edge $AB$ blue and don't change pivot. Finally we will reach a position where every vertex except the pivot is either blue or is red and is adjacent to the pivot via a red edge. Shift the pivot to any other red vertex and continue the process.

In the end, suppose there are $s$ red vertices left. Note that the pivot from Step 2 isn't one of them. Every pair of them must be connected to each other via a red edge, since otherwise we can continue the process. If $s \geq 3$ then there must exist a cycle among them, impossible because the pivot isn't one of them. Hence $s \leq 2$ . So this step takes $n-k-s \leq n-k$ queries.

Step 4: Blue

Query every red vertex left with every other vertex. This takes at most $2n$ queries since $s \leq 2$ .

Overall we have used at most $(n-1)+(k+1)+(n-k)+2n=4n$ queries.

This post has been edited 2 times. Last edited by Supercali, Oct 12, 2020, 5:14 AM

Z K Y

The post below has been deleted. Click to close.

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

Eyed

1065 posts

Eyed

#15 h Feb 1, 2021, 4:04 AM • 8 Y

Y by ForeverAPenguin47, AwesomeYRY, kevinmathz, Adventure10, uvuvwevwevwe, mathleticguyyy, sabkx, Mango247

I am Alice:

To make this writeup easier, I am Alice, and a computer that answers my questions is the King of Hearts. Define the phrase "ask U and V" as asking the computer the direction between towns U and V. Also let wonderland be a graph, and towns be nodes. Define $U\rightarrow V$ means the road goes from $U$ to $V$ , and vice versa.

First, we will create a tree of the $n$ towns, such that it's rooted, and every road goes from a node to its parent. This is how we do this:

Define current as a variable that stores a node. First, let current be an arbitrary node. This is the recursion: Pick a random node $U$ (that hasn't been chosen), and ask $U$ and current. If $U\rightarrow$ current, then repeat the above step (chose another vertex $T$ , ask current and $T$ , and so forth). Otherwise, let current be $U$ , and repeat.

First, this will create a tree, since we ask every node, but we don't repeat, which means it must form a tree. Furthermore, every road goes from it to its parent, since we only switch current once we have an road going out from the node. Thus, it will create a tree directed to the head.

Let the head of this tree be $H$ , and let the tree be $T$ . I claim at most $2$ towns that are not $H$ can have outdegree at most $1$ . This is because, consider two nodes $U, V$ that are not $H$ , such that $U$ is not the parent of $V$ , and $V$ is not the parent of $U$ . Then, both $U$ and $V$ have outdegree (at least for now) of $1$ . When we ask $U$ and $V$ , one of $U$ or $V$ will increase their outdegree by $1$ , so one of $U$ and $V$ can not have outdegree at most $1$ . Thus, the only possible nodes that can have outdegree $1$ that's not $H$ are parent and children nodes, which means there can be at most $2$ such nodes.

Now, start asking $H$ to $V$ , for every $V\neq H$ and $V$ is not a child of $H$ in $T$ . If at some point $H$ will have outdegree $2$ , then terminate at this point, and assume $r$ edges have been drawn. If we never terminate, then we can say the answer is yes (as $H$ will have outdegree at most $1$ , and we would've asked less than $2n$ questions), so assume it terminates after $r$ questions. Then, every time we've asked $H$ to $V$ , and it went $V\rightarrow H$ , then $V$ can not have outdegree at most $1$ (it has outdegree $2$ to its parent and $H$ ), so just ignore $V$ . Since there are exactly $2$ nodes $Q$ that we've asked $H$ and $Q$ and gotten a response $H\rightarrow Q$ , this means we are ignoring $r-2$ nodes, so there are $n-1-(r-2) = n+1-r$ nodes not including $H$ that we still care about.

Since we know that $H$ can't have outdegree at most $1$ , we can effectually ignore $H$ as well. So far, we've asked $n-1 + r$ questions. Now, let $S$ be the set of $n+1-r$ nodes left that we aren't ignoring (the ones we care about). Arbitrarily ask $U$ and $V$ such that $U,V\in S$ and $U$ and $V$ do not have a parent-child relationship. If $U\rightarrow V$ , then remove $U$ from the set, and vice versa. If $U\rightarrow V$ , this means $U$ has outdegree $2$ (to it's parent and $V$ ). Basically, we're only removing a node from a set once it has outdegree $2$ . Observe that we can keep doing this until there is $2$ nodes left in $S$ , since if there was more than $2$ nodes in $S$ , then one vertex $V\in S$ will have a node that's not it's parent in $T$ that's also in $S$ . Since after each question, we also removed a node, this means we've asked $|S| - 2$ questions, and since $|S| = n+1-r$ , we've asked $n+1-r-2 = n-1-r$ questions. Combining with the $n-1 + r$ questions we've asked from earlier, we've asked a total of $2n - 2$ questions.

Let these two vertices in $S$ be $U$ and $V$ . Now, ask $U$ and $K$ for all $K$ such that $K\neq U, V$ , and ask $V$ and $K$ . This will result in another $2(n-2)$ questions. Finally, if $U$ and $V$ are not parent-children, ask $U$ and $V$ . Thus, we've asked at most $2n-2 + 2(n-2) + 1 = 4n - 5$ questions. Since we know that $U$ and $V$ are the only possibilities to have at most one outdegree, and we also know the direction of each road with $U$ or with $V$ , then we can determine whether $U$ has outdegree at most $1$ , or $V$ does. This means we can determine whether wonderland has a vertex with outdegree at most $1$ , so we conclude.

Z K Y

The post below has been deleted. Click to close.

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

IndoMathXdZ

691 posts

IndoMathXdZ

#16 h Feb 17, 2021, 3:15 PM • 4 Y

Y by Adventure10, GorgonMathDota, Aritra12, Mathological03

Let $G$ be the obvious directed graph representation of the problem. We define $\mathcal{V}_0$ to be the set of vertices of outdegree $0$ , $\mathcal{V}_1$ to be the set of vertices of outdegree $1$ and $\mathcal{V}_{\ge 2}$ to be the set of vertices of outdegree greater than or equal to $2$ .

We start with an empty graph, which means all of the vertices are elements of $\mathcal{V}_0$ and our task is to connect edges such that we can determine whether $\mathcal{V}_0 \cup \mathcal{V}_1$ could be empty or not. This could not be empty if there is at least one town in Wonderland with at most one outgoing road, and could always be empty otherwise.

The obvious algorithm is of complexity $O(n^2)$ , therefore we seek to see any algorithm of $O(n)$ time complexity, before we further continue our problem.

Fact 01. Connecting two vertices from $\mathcal{V}_0$ reduces the member of $\mathcal{V}_0$ by exactly one.
From this fact, since we start with an empty graph of $|\mathcal{V}_0| = n$ , we could reduce it to $|\mathcal{V}_0| = 1$ by adding exactly $n - 1$ edges, which forms a tree, since if we connect an edge $u \to v$ in a particular round, we won't connect the remaining vertices with $u$ as $u \notin \mathcal{V}_0$ . Furthermore, it is easy to see that these edges passes through all vertices of the graph (as we tested all $n$ vertices).

From here, it is quite easy to find an algorithm that terminates in $5n + O(1)$ steps.
After the first $n - 1$ steps, we have $|\mathcal{V}_0| = 1$ and $|\mathcal{V}_{1}| = n - 1$ . Now doing the same for the $n - 1$ vertices in $\mathcal{V}_1$ , we could reduce this to $|\mathcal{V}_1| = 2$ by adding $n - 3$ edges (as it is possible that the last two edges are already connected in the previous round, and for any $|\mathcal{V}_1| \ge 3$ , since the first graph is not a tree, we can always connect edges between two vertices that hasn't been connected before, which reduces $\mathcal{V}_1$ by one.) Now, we have $|\mathcal{V}_0| = 1$ and $|\mathcal{V}_1| = 2$ . There are several possible cases.

If the unique ingoing edge of the vertices in $\mathcal{V}_0$ is not a member of $\mathcal{V}_1$ ,
$[asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=blue] (1,0) circle (3 pt); \draw[red,dashed,->,very thick] (1,0) -- (4,0); \draw[fill=blue] (4,0) circle (3 pt); \draw[fill=yellow] (6,2) circle (3 pt); \draw[green,dashed,->,very thick] (4,0) -- (6,2); \draw[red,thick] (0,-2) -- (5,-2) -- (5,1) -- (0,1) -- cycle; \node[brown, font=\small] at (2.5,-1) {$\mathcal{V}_1$}; \draw[fill=yellow] (8,2) circle (3 pt); \draw[green,dashed,->,very thick] (8,2) -- (10,0); \draw[fill=blue] (10,0) circle (3 pt); \draw[red,thick] (9,-1) -- (11,-1) -- (11,1) -- (9,1) -- cycle; \node[brown,font=\small] at (10,-0.5) {$\mathcal{V}_0$}; \end{tikzpicture}");[/asy]$
Then draw $2$ edges that connect vertices in $\mathcal{V}_0$ with each vertices in $\mathcal{V}_1$ , notice that if both of the edges are outgoing edges from the vertex in $\mathcal{V}_0$ , then we now have $|\mathcal{V}_0| = 1$ and $|\mathcal{V}_{\ge 2}| = n - 1$ , and therefore connecting the vertex in $\mathcal{V}_0$ with all the remaining edges suffice. If at most one of the edges is outgoing, then we have $|\mathcal{V}_1| = 2$ and $|\mathcal{V}_{\ge 2}| = n - 2$ . Connect these two edges with the remaining $n - 3$ points, this algorithm suffice. In either cases, $4n$ questions suffice.
If the unique ingoing edge of the vertices in $\mathcal{V}_0$ is indeed a member of $\mathcal{V}_1$ ,
$[asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=blue] (1,0) circle (3 pt); \draw[red,dashed,->,very thick] (1,0) -- (4,0); \draw[fill=blue] (4,0) circle (3 pt); \draw[red,thick] (0,-2) -- (5,-2) -- (5,1) -- (0,1) -- cycle; \node[brown, font=\small] at (2.5,-1) {$\mathcal{V}_1$}; \draw[fill=blue] (10,0) circle (3 pt); \draw[red,thick] (9,-1) -- (11,-1) -- (11,1) -- (9,1) -- cycle; \draw[red,dashed,->,very thick] (4,0) -- (10,0); \node[brown,font=\small] at (10,-0.5) {$\mathcal{V}_0$}; \end{tikzpicture}");[/asy]$
Now, connect the vertex in $\mathcal{V}_0$ with the unique vertex not connected to it, if it forms an acyclic triangle, then we have $|\mathcal{V}_1| = 2$ and $|\mathcal{V}_{\ge 2} | = n - 2$ , and our algorithm from the previous case suffices. Otherwise, we have a cyclic triangle, as follow:
$[asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=blue] (1,0) circle (3 pt); \draw[red,dashed,->,very thick] (1,0) -- (4,0); \draw[fill=blue] (4,0) circle (3 pt); \draw[fill=blue] (2.5,2.2) circle (3 pt); \draw[red,dashed,->,very thick] (4,0) -- (2.5,2.2); \draw[red,dashed,->,very thick] (2.5,2.2) -- (1,0); \draw[violet,thick] (0,-1) -- (5,-1) -- (5,3) -- (0,3) -- cycle; \node[green,font=\small] at (2.5,-0.5) {$\mathcal{V}_1$}; \end{tikzpicture}");[/asy]$
Since we have $|\mathcal{V}_1| = 3$ and $|\mathcal{V}_{\ge 2}| = n - 3$ , connecting each of the vertices from $\mathcal{V}_1$ to the remaining vertices suffice, and this would take a total of $5n + O(1)$ steps in total.

The main difficulty of this problem is to find a way to reduces our algorithm of $5n + O(1)$ steps to $4n$ steps. I'll borrow a term from my friend alexiaslexia

Define a death triangle to be a triangle formed by vertices $x,y,z$ such that the directed edges are cyclic, that is $x \to y$ , $y \to z$ and $z \to x$ .
From our previous algorithm, a death triangle where $|\mathcal{V}_1| = 3$ , and all of the vertices of the triangle are elements of $\mathcal{V}_1$ would makes us lose at least $3n + O(1)$ questions. Therefore, we need to prevent these triangles from appearing.

Inspired from the previous algorithm, we use the exact first moves:
Move 1: In the first $n - 1$ turns, connect any two vertices from $\mathcal{V}_0$ .

After this move is done, we will have $|\mathcal{V}_0| = 1$ and $|\mathcal{V}_{1}| = n - 1$ . For convenience, let the unique vertex in $\mathcal{V}_0$ be $v_0$ .

Move 02: Use $m \le n - 2$ questions to determine $v_0$ .
We'll now connect $\text{edge}(v_0, v)$ for any vertices $v \in \mathcal{V}_1$ , that is not already connected to $v_0$ Now, there are two possible cases:

If we have $v_0 \to v$ for some $v \in \mathcal{V}_1$ , then $v_0$ stays in its set, and $v \in \mathcal{V}_{\ge 2}$ .
Otherwise, if $v \to v_0$ for some $v \in \mathcal{V}_1$ , then $v_0 \in \mathcal{V}_{i + 1}$ if previously $v_0 \in \mathcal{V}_i$ , and $v$ stays in the particular set.

Let $m$ be the minimal number of questions needed so that $v_0 \in \mathcal{V}_{\ge 2}$ after the $m$ th operation. We'll assume this exists or otherwise we will have $v_0 \in \mathcal{V}_0 \cup \mathcal{V}_1$ after connecting $v_0$ with all of the other vertices, and we can conclude that $v_0$ is the desired vertex, with less than $(n - 1) + (n - 2) < 4n$ questions. Therefore, we have $m \ge 2$ . Furthermore, since we assume $m$ is minimal, then we now have $|\mathcal{V}_1| = (n - 1) - (m - 2) = n - m + 1$ and $|\mathcal{V}_{\ge 2}| = (m - 2) + 1 = m - 1$ .

Move 03: Use $n - m - 1$ questions to reduce $\mathcal{V}_1$ to $|\mathcal{V}_1| = 2$ .
This is inspired by the previous algorithm. Now, connect any two vertices in $\mathcal{V}_1$ will reduces the member of $\mathcal{V}_1$ by exactly one, and we could do this until $|\mathcal{V}_1| = 2$ (since we have that the first graph is not a tree, then the subgraph induced by the vertices in $\mathcal{V}_1$ is also a tree, and therefore if $|\mathcal{V}_1| \ge 3$ , we could connect edges between two vertices that hasn't been connected before, which reduces $\mathcal{V}_1$ by one.) Since we have $|\mathcal{V}_1| = n - m + 1$ , we could use $n - m - 1$ questions.

Last Move. Use $2n - 4$ questions to connect each vertices in $\mathcal{V}_1$ to all of the other vertices to check.
This is pretty straightforward, as we wanted to connect every vertices in $\mathcal{V}_1$ and $\mathcal{V}_{\ge 2}$ , which needs $2(n - 2) = 2n - 4$ questions.

In total, our algorithm above needs
$n - 1 + (n + m - 1) + (n - m - 1) + 2n - 4 = 4n - 6 < 4n \ \text{questions.}$ Hence, we are done.

Remark. The main motivation of this above algorithm is the $O(n)$ algorithm we found in the beginning that would solve the problem in $5n + O(1)$ questions. This pretty much build the whole point of our algorithm, however, we our wasting too much time by the appearance of the death triangle. Therefore, we want to somehow prevent the triangle from appearing, and the best way to do this, is to start deleting the vertex from $\mathcal{V}_0$ after the first moves (since we know that the main cause of death triangle is the vertex from $\mathcal{V}_0$ ).
Now, we are wasting time by connecting each vertices $\mathcal{V}_0$ with $\mathcal{V}_1$ without any checking, therefore, we would like to minimize our time, and introducing the variable $m$ , the number of minimum questions needed such that we could have $v_0 \in \mathcal{V}_{\ge 2}$ is introduced. Calculating the number of vertices in $\mathcal{V}_1$ and $\mathcal{V}_{\ge 2}$ after this move shows that $\mathcal{V}_1$ has now $n - m + 1$ vertices, thanks to the $m$ we introduced earlier. Now, the rest is essentially the same as our original algorithm of $5n + O(1)$ steps, however, this time, we won't have to worry about the appearance of such triangle since the graph $G$ induced by $\mathcal{V}_1$ is a tree, and therefore we could force $|\mathcal{V}_1| = 2$ with the exact same method. Until now, we have only used $n - 1 + m + (n - m - 1) = 2n - 2$ questions, and we have $|\mathcal{V}_1| = 2$ , following our exact same step from before, this is our win.

Z K Y

The post below has been deleted. Click to close.

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

Loppukilpailija

155 posts

Loppukilpailija

#17 h Aug 21, 2021, 10:17 PM

Y by

Take the obvious graph representation. At each step in the procedure, maintain the following sets:

$A$ : vertices for which we know that the outdegree is at least $2$ .
$B$ : vertices for which we know that the outdegree is at least $1$ but for which we do not know it is at least $2$
$C$ : vertices for which we do not know that the outdegree is at least $0$

Initially all vertices are in set $C$ . Label the vertices initially $v_1, v_2, \ldots , v_n$ .

Step 1. Query $v_1$ and $v_2$ . One of the vertices moves to $B$ . Denote the one which does not by $v$ , call it the active vertex. Then always query the active vertex $v$ and $v_3, v_4, \ldots , v_n$ . At each step either $v$ or $v_i$ moves on to $B$ . If $v$ moves to $B$ , call $v_i$ the active vertex.

After step 1 we have $|C| = 1$ and $|B| = n-1$ . We have used $n-1$ queries. Note that the induced subgraph given by the vertices of $B$ is a forest and so acyclic.

Step 2. Query some pair of vertices of $B$ which have not yet been queried. One of the vertices moves to $A$ . Keep doing this. As long as $|B| \ge 3$ , we can do this: otherwise we would have a clique of size $3$ in the induced subgraph of $B$ , which contradicts $B$ being acyclic.

After step 2 we have $|C| = 1$ and $|B| \le 2$ . Step 2 takes at most $n-2$ queries.

If $|B| = 1$ , we have only two candidates for a vertex with outdegree $\le 1$ . We may check whether they really have outdegree $\le 1$ by brute force in $\le n-1$ queries for each of them. We thus complete in $\le 4n - 5$ queries.

If $|B| = 2$ , then the vertices of $B$ are connected, as otherwise in step 2 we would still query them. This means that they have been connected in step 1. This in turn implies that there is no edge between the vertex of $C$ with the vertices of $B$ . Query the two edges between the vertex of $C$ and the vertices of $B$ . After this at least one vertex of $B \cup C$ has moved on to $A$ . We may then again brute force the remaining two vertices. This completes in $\le 4n - 3$ queries.

Z K Y

The post below has been deleted. Click to close.

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

mathleticguyyy

3217 posts

mathleticguyyy

#18 h Dec 19, 2021, 3:06 AM • 1 Y

Y by Inconsistent

We divide our solution into 4 stages. Label the vertices as $v_1,v_2\ldots v_n$

Step 1: We will build a spanning tree in $n-1$ queries. Designate a "focus vertex" that's initially $v_1$ . On the $i$ th query, suppose that the focus vertex is $v_{j}$ ; we query the edge between $v_j$ and $v_{i+1}$ , and out of the two, we choose the one with an ingoing edge as the new focus vertex. At the end of this step, we will have a spanning tree where $n-1$ vertices have outdegree at least $1$ and $1$ vertex has outdegree at least $0$ . Call the former group fighters and the latter group referees.

Step 2: We will eliminate almost every fighter in a knockout tournament. Denote a martyr as a vertex with outdegree at least $2$ . On each query, if there exist two fighters that aren't connected by an edge, we choose the edge between them. The fighter with an outgoing edge becomes a martyr and we can ignore it for the remainder of this step.

Claim: When any two fighters are connected by an edge, at most $2$ fighters will remain.

Proof. Suppose that $m\ge 3$ fighters will survive. Then, the complete subgraph between them must contain a cycle. However, each edge queried in step $2$ eliminates a fighter, and step $1$ does not create any cycles.
Call the surviving fighter(s) insurgents. There will be either $n-2$ or $n-3$ martyrs, for $n-2$ or $n-3$ queries during this step.

Step 2.5: If two insurgents exist, then we query the edges between either of them and the referee. Each ingoing edge to the referee eliminates an insurgent, and if both edges from the referee are outgoing, the referee is eliminated.

Step 3: Since there are at most two vertices with outdegree at most $1$ ("survivors") at this point, we can just query every unknown edge between either a survivor and a martyr, or two survivors. This takes at most $2n-3$ queries and finishes the problem.

Summing up each step, we have a bound of $(n-1)+(n-2)+2+2n-3<4n$ queries.
Q E fri*king D.

This post has been edited 4 times. Last edited by mathleticguyyy, Dec 19, 2021, 3:13 AM

Z K Y

The post below has been deleted. Click to close.

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

math90

1476 posts

math90

#19 h Jul 27, 2022, 9:30 AM • 2 Y

Y by Mango247, Mango247

We divide our solution into $4$ stages. Let $G$ be our graph. Label the vertices $v_1, v_2, \ldots , v_n$ .

Step 1. We build a spanning tree in $n-1$ queries. Define $v_1$ as our initial pivot. On the $i$ th query, we query the edge between our current pivot and $v_{i+1}$ . We then choose the vertex with the ingoing edge to be our new pivot.

At the end of step 1, let $x$ be our final pivot and let $G_1$ be the subgraph whose edges are the currently queried ones. So $G_1$ is a directed tree with each vertex except $x$ has outdegree $1$ , while $x$ has outdegree $0$ . Since $G_1$ is a tree, then $G_1$ is $2$ -colorable so $G_1\setminus\{x\}$ is $2$ -colorable as well. Let us color $V(G)\setminus\{x\}$ in black and white so that in each color, no two vertices are joined in $G_1$ . Let $B,W$ be the sets of white and black vertices, respectively. Let $G_B,G_W$ be the induced subgraphs of $G$ on $B,W$ respectively. Since $n\ge 2$ we can assume WLOG $B\ne\emptyset$ .

Step 2. Label the vertices of $B$ arbitrarily and perform step 1 on $B$ .

Let $y_B$ be the pivot of $B$ at the end of step 2. Since $E(G_B)\cap E(G_1)=\emptyset$ , it follows that every vertex of $B$ except $y_B$ has outdegree at least $2$ in $G$ , while $y_B$ has outdegree $1$ . So step 2 takes $|B|-1$ queries.

Step 3. Label the vertices of $W$ arbitrarily and perform step 1 on $W$ .

If $W\ne\emptyset$ , let $y_W$ be the pivot of $W$ at the end of step 3. Since $E(G_W)\cap E(G_1)=\emptyset$ , it follows that every vertex of $W$ except $y_W$ , if it exists, has outdegree at least $2$ in $G$ , while $y_W$ has outdegree $1$ . So step 3 takes $\max(|W|-1,0)$ steps.

Step 3.5 If $y_W$ exists, query $y_B$ and $y_W$ . Then $y_B$ or $y_W$ has outdegree at least $2$ .

At the end of step 3.5, at most two vertices have current outdegree at most $1$ . Steps 3 and 3.5 together take $|W|=n-1-|B|$ queries.

Step 4. Let $y\in V(G)\setminus\{x\}$ be the vertex with current outdegree $1$ . Query all remaining edges connecting $x$ or $y$ . This process takes at most $2n-3$ queries and finishes the problem.

So the total number of queries is at most $(n-1)+(|B|-1)+(n-1-|B|)+(2n-3)=4n-6$ .

This post has been edited 11 times. Last edited by math90, Mar 25, 2023, 1:46 PM

Z K Y

The post below has been deleted. Click to close.

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

JAnatolGT_00

559 posts

JAnatolGT_00

#20 h Oct 16, 2022, 8:06 PM

Y by

We interpret the problem as follows. There is a graph-clique, whose each edge is directed and colored white, and each vertex colored red. With each move we are allowed to paint any edge black; if after a move from some red vertex outgoes at least $2$ black edges, then we paint this vertex blue. Our goal is by at most $4n$ questions make the situation when either

there is at least one red vertex which incident only with black edges;
all vertices are blue.

Step 1. Place a bug to an arbitrary vertex, and do $n-1$ moves, by repeating operations of type:

if bug sit at vertex $A,$ pick any vertex $B,$ which hasn't outgoing black edges, and paint edge $AB$ black;
let bug move according to the direction of $AB.$

Thus we create a directed tree $T$ , where vertex $X$ with bug hasn't outgoing black edges, and all other vertices has exactly one such edge.

Step 2. Start painting black all white edges incident with $X$ . If there left no such edges and $X$ is red, then we are done by at most $n-1+n-2<4n$ moves, so we suppose the opposite. Say that after $k$ moves $X$ became blue (with $k-2$ other vertices).

Step 3. Start painting black white edges incident with two red vertices until it is possible; every such move decreases number of red points by $1,$ and suppose we have $m$ red vertices at the end.

Claim. We have $m\leq 2.$
Proof. Assume the opposite; obviously $m<4,$ so we have $m=3.$ In that case graph of red vertices is a cycle $P\rightarrow Q\rightarrow R,$ whose some edge (WLOG $PR$ ) isn't presented in $T.$ Then $P$ has some outgoing black edge, different from $PQ,$ so it's blue, contradiction $\Box$

Step 4. Paint black all white edges, incident with red vertices - they either all become blue, or at least one of them stays red and incident with black edges only. Thus we are done by at most $(n-1)+k+(n-k)+2(n-2)=4n-5<4n$ moves.

Z K Y

The post below has been deleted. Click to close.

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

trying_to_solve_br

191 posts

trying_to_solve_br

#21 h Mar 25, 2023, 10:08 PM • 1 Y

Y by jrsbr

Sketch of a solution with @jrsbr

Take the Graph interpretation and let $G$ be the graph. Firstly, we make $n-1$ questions to get the structure of the graph and we do the following: pick a random vertice $V$ and ask question about his neighbors until we get a $deg out$ neighbor wrt $V$ . If there is none, then $V$ satisfy the statement. Suppose there is no $V$ (because if there is we're done) and do this to the whole graph (we pass through the whole graph as it is a directed clique). Then we get a directed path with disjoint arrows to the vertices of this path. Let $P,Q,R$ be the last three vertices of the path, in this order (it is easy to solve if the path has length one or two).

Notice that for every two vertices with out deg at least one we can compare them (if they weren't compared yet) and "exclude" the one with deg out greater than or equal to two. Call this process "sus". Also, I say we exclude a vertice if it can't be good anymore.

We now do the following: call a vertice good if it satisfies the statement. Now, suppose $R$ is neighbor with $X$ vertices and there are $K$ vertices out of the path, not counting with $N(R)=X$ ones. Then, ask about $R,Q$ totalizing $n$ questions. Notice we know every vertice except for $R$ has deg out at least one. Now we divide in two cases:

$P \to R$ : Then sus all the vertices except for one out of the path by asking $K+X-1$ questions and then sus all the vertices except by two consecutives and $R$ (they are the only ones we can't sus as they are already asked and $R$ may be still with deg out < 1), and we can do this by asking $N-K-X-3$ questions. Then, notice we only have two consecutive vertices from the path ( $Y,Z$ ), one out of the path (call this $J$ ) and $R$ . Notice that $P$ has out deg at least two ( $P \to Q, P \to R$ ) and thus $P \neq Y,Z$ . We used $2n-4$ questions until now. Then we check cases to see that two of the four remaining vertices are not good (i.e. compare $J$ with $Y$ and exclude one of them and then compare $RJ$ , $RY$ , $RX$ and exclude two of them). Now we have two vertices, and $2n-1$ questions asked at most (with the case work) and we may now ask for each one of them at most $n-1$ questions to know if they are good or not and thus we asked at most $4n-3$ questions in this case.

$R \to P$ : Then, we compare $R$ with $B$ vertices in the rest of the graph, and if he points to some vertice, $R$ isn't good anymore. If $R$ just points to $P$ of the whole graph then $R$ is good and gg we won. Now, we can suppose we excluded $R$ . Suppose $R$ excluded $A,B$ vertices from the path and from out of the path, respectively, and note that if we apply the same algorithm to the $N-K-X-A$ from the path and to the $K+X-B$ vertices from out of the path totalizing more $N-A$ questions, and thus we have asked $2N-A-1$ questions and we end up with two from inside the path (different from $Q,R$ ) and one from outside, and by casework we can exclude one of them (it is important none of them is $R$ to do the casework) with two questions. To finish, we can ask $N-1$ at maximum for each of the two last vertices from the three to check with "everybody" if they're good, ending up with $4N-A \le 4N$ questions in total. gg

Z K Y

The post below has been deleted. Click to close.

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

Rexaria112

48 posts

Rexaria112

#22 h May 4, 2023, 1:53 PM

Y by

My solution goes through 4 steps, using the obvious graph interpretation.
Call a town "safe" if it has at least two outgoing roads and "suspect" if we haven't proven yet that it is "safe".

Step 1: Forming the tree:
First Alice chooses an arbitrarly town (vertex) $a_1$ , then repeats the following algorithm which constracts the tree:
If the current chosen town is $a_i$ , then Alice asks the king about $a_iv$ for vertex $v$ not asked about before such that $a_i\leftarrow v$ until she gets the case $a_i\rightarrow v$ , then $v$ becomes $a_{i+1}$ . assume the last town asked about is $a_t$
This step requires $\boxed{n-1}$ questions.

Step 2: No triangles allowed...?
In this step Alice asks about $a_tv$ so that $a_tv$ is not asked about before, she keeps asking questions until she gets two different vertices $v_1$ , $v_2$ such that $a_t\rightarrow \{v_1,v_2\}$ , and notice that if she didn't get those vertices then $a_t$ is the needed town and she stops here.
Notice that if $a_i\leftarrow v_j$ then $v_j$ is safe as there is already an outgoing road from it. Let $k$ be the number of safe cities that we've proven in this step.
Notice that this step requires at most $\boxed{t+1}$ questions.

Step 3: Well... no triangles allowed here.
Now keep asking about random non-adjacent suspect vertices $v_iv_j$ and notice that for each question we will get a new safe vertex, because each suspect has already an outgoing road. Repeating this process will lead us eventually to at most 2 vertices, because for any three vertices of the tree there is at least two non-adjacent vertices.
This requires at most $\boxed{n-t-1}$

Step 4: Check the remaining suspects...
This requires at most $\boxed{2n-4}$

So overall, we need at most $\boxed{4n-5}$

An easy construction to 5n-c
My motivation

This post has been edited 1 time. Last edited by Rexaria112, May 10, 2023, 5:44 PM

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5001 posts

IAmTheHazard

#23 h Mar 3, 2024, 2:47 PM

Y by

Alice first designates every vertex as bad. Alice constructs a directed tree as follows: while at least two bad vertices $v,w$ exist, she queries them; if she learns that $v \to w$ , then $v$ loses its "bad" status. Hence the bad vertices are precisely those where no outedge is known. This takes a total of $n-1$ queries, with the result being that Alice has exactly one bad vertex $x$ , and the graph of known edges is evidently a directed tree $T$ pointing towards $x$ .

She now designates every vertex other than $x$ as meh. While there exist two meh vertices $v,w$ such that $\{v,w\}$ is not an edge in the tree (in either direction), she queries them; if she learns that $v \to w$ , then $v$ loses its "meh" status. Hence the meh vertices are precisely those where exactly $1$ outedge is known. When this process terminates we are left with at most $2$ (and at least $1$ ) meh vertices: if there were three, then there would be a (not necessarily directed) triangle in $T$ , which is absurd. If Alice is left with $2$ vertices, this process takes $n-3$ queries, else this process takes $n-2$ .

At the end of these two steps, Alice knows that all but at most $3$ vertices (the bad or meh ones) have outdegree at least $2$ . If there exist $2$ meh vertices $y,z$ , Alice queries $\{x,y\}$ and $\{x,z\}$ . Then,

If $y \to x$ , we remove the meh status of $y$ —we have found two outedges
If $z \to x$ we do the same
Otherwise, $x \to y$ and $x \to z$ , so we remove the bad status of $x$ —we have found two outedges.

The result of this is that there are at most $2$ vertices with oudegree at least $2$ , and at this point we have used at most $2n-1$ queries. Then we can just query every pair of vertices containing at least one of these, which takes at most $2(n-1)$ queries, and clearly finish. $\blacksquare$

Remark: I never really found the $5n$ move strategy. In fact, most of the solution was found in order, since I started with the rather natural question of solving the problem for outdegree at least $1$ instead of $2$ . The creation of the tree in the first step seems very helpful in the actual problem too, so we commit to it and then work from there by trying to repeat it.

This post has been edited 2 times. Last edited by IAmTheHazard, Mar 3, 2024, 2:48 PM

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1891 posts

cj13609517288

#24 h Mar 25, 2024, 7:21 PM

Y by

We have a tournament on $n$ vertices, and we want to make $4n$ edge queries to find if there exists a node with outdegree at most $1$ (if this exists, call this an amazing node). If an edge goes from $a$ to $b$ , say that $b$ is better than $a$ . Note that "better than" is not transitive. $n=1$ is trivial so assume $n\ge 2$ .

Phase 1 (n-1 queries)
Label the cities $1$ to $n$ . First compare cities $1$ and $2$ . Then compare the better city with city $3$ . Then compare the better city with city $4$ , etc. After these $n-1$ comparisons are over, each city besides the "winner" will be worse than exactly one other city. Call the undirected graph of the queries in this phase $G'$ .

Phase 2 (m queries, we will define m later)
Compare the winner to each city besides itself and the one it beat to become the winner. As soon as the winner loses its second time, terminate this phase and let $m$ be the number of queries this phase took. If the winner doesn't lose at least twice, Alice has already won at most $2n-3$ queries.

Phase 3 (n-m-4 queries)
Let $S$ be the set of vertices that could possibly be better than the winner, that is, the two cities it lost to and the ones that weren't checked yet(not including the one it beat in phase 1). Note that everything besides the cities in $S$ already have no chance. Now take the subgraph induced in $G'$ by $S$ , call it $H$ . Then take any edge in the complement of $H$ (this can't be the empty graph if $|S|\ge 3$ ) and query it. This will eliminate exactly one city as an amazing node, so remove that option from $S$ . Perform this procedure repeatedly until $|S|$ is at most $2$ .

Phase 4 (at most 2n-2 queries)
Now there are only two possible candidates left as an amazing node, so simply query all of the edges involving them to decide the answer.

We have used a total of at most $(n-1)+m+(n-m-4)+(2n-2)=4n-7$ queries, so we win! $\blacksquare$

### SETUP ###
QUERY_COUNT = 0
def better(a,b):
  assert a != b and 1 <= a <= n and 1 <= b <= n
  global QUERY_COUNT
  QUERY_COUNT += 1
  if QUERY_COUNT > 4*n: raise Exception("Too many queries!")
  ans = int(input(f"Which one is better? {a} or {b} "))
  assert ans in [a,b]
  return ans
 
n = int(input("Enter n: "))
if n == 1:
  print("YES")
  exit()
 
### PHASE 1 ###
best = 1
graph = {i:set() for i in range(1,n+1)}
for i in range(2,n+1):
  graph[best].add(i)
  graph[i].add(best)
  best = better(best,i)
 
### PHASE 2 ###
losses = 0
ignore = n if best != n else n-1
m = 0
s = {*range(1,n+1)}-{best,ignore}
for i in {*range(1,n+1)}-{best,ignore}:
  m += 1
  s -= {i}
  if better(best,i) == i:
    losses += 1
    if losses >= 2:
      break
else:
  print("YES")
  exit()
 
### PHASE 3 ###
while len(s) > 2:
  toQuery = tuple()
  for v in s:
    for w in s:
      if w not in graph[v]: toQuery = (v,w); break
    if toQuery: break
  a,b = toQuery
  s -= {a+b-better(a,b)}
 
### PHASE 4 ###
for v in s:
  ct = 0
  for w in {*range(1,n+1)}-{v}:
    if better(v,w) == w: ct += 1
    if ct >= 2: break
  if ct <= 1:
    print("YES")
    exit()
print("NO")

### SETUP ###
QUERY_COUNT = 0
def better(a,b):
  assert a != b and 1 <= a <= n and 1 <= b <= n
  global QUERY_COUNT
  QUERY_COUNT += 1
  if QUERY_COUNT > 4*n: raise Exception("Too many queries!")
  ans = int(input(f"Which one is better? {a} or {b} "))
  assert ans in [a,b]
  return ans

n = int(input("Enter n: "))
if n == 1:
  print("YES")
  exit()

### PHASE 1 ###
best = 1
graph = {i:set() for i in range(1,n+1)}
for i in range(2,n+1):
  graph[best].add(i)
  graph[i].add(best)
  best = better(best,i)

### PHASE 2 ###
losses = 0
ignore = n if best != n else n-1
m = 0
s = {*range(1,n+1)}-{best,ignore}
for i in {*range(1,n+1)}-{best,ignore}:
  m += 1
  s -= {i}
  if better(best,i) == i:
    losses += 1
    if losses >= 2:
      break
else:
  print("YES")
  exit()
  
### PHASE 3 ###
while len(s) > 2:
  toQuery = tuple()
  for v in s:
    for w in s:
      if w not in graph[v]: toQuery = (v,w); break
    if toQuery: break
  a,b = toQuery
  s -= {a+b-better(a,b)}
  
### PHASE 4 ###
for v in s:
  ct = 0
  for w in {*range(1,n+1)}-{v}:
    if better(v,w) == w: ct += 1
    if ct >= 2: break
  if ct <= 1:
    print("YES")
    exit()
print("NO")

Z K Y

The post below has been deleted. Click to close.

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

kingu

220 posts

kingu

#25 h Apr 22, 2024, 7:28 PM • 1 Y

Y by MathLuis

Solved with @MathLuis.

Assume the graph interpretation of the problem, where initially there's $n$ vertices without edges, and at each question made by Alice the king adds a directed edge. We describe an algorithm with at most $4n$ steps required for Alice to reach her objective.

Definitions:
A vertex is wanted if it has $0$ out degree, sus if it has $1$ , and safe otherwise.

Notice that we can have at most $3$ sus vertices in the final configuration, and we have $3$ of them only if they form a directed cycle.

Step 1: Alice queries for a wanted vertex with another wanted vertex that was not queried before, this process creates a spanning tree with $n$ vertices, requiring $n-1$ questions, with one wanted vertex left, say $u$ .
Step 2: Alice queries about $u$ with the sus vertices, stopping when it becomes sus, otherwise $u$ is the desired vertex with at most $2n$ questions being required. For the former case, assume it took $t$ questions, then we have that the number of sus vertices is now $n - t$ .
Step 3: Analogously to step 1, we repeat that process, with at most $3$ vertices sus, in case we have at most $2$ vertices, just query for each one of the sus vertices against every other vertex to reach Alice's objective, and notice that the case with $3$ remaining is impossible, as these edges couldn't have been added in the last step as one of them would have become a safe vertex, thus, they were added in the first step, however this is a clear contradiction with the fact that a tree is acyclic. Therefore, requiring at most $n - t - 1 + 2(n-1)$ queries.

In total, Alice can reach her objective in at most $n - 1 + t + n - t + 2(n-1) = 4n - 3$ queries.

Remark: When attempting this problem solo, I couldn't figure out at first how to overcome the irritating triangle, in retrospect the initial steps are natural, and the structure created in the first step is key.

This post has been edited 2 times. Last edited by kingu, Apr 22, 2024, 8:43 PM

Z K Y

The post below has been deleted. Click to close.

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

naonaoaz

329 posts

naonaoaz

#26 h Apr 30, 2024, 3:54 PM

Y by

Let $G$ be the graph using the information Alice has. Start at any vertex and do the following:

Keep a set of visited vertices $V$ .
Pick a random edge that connects the current vertex to any vertex not in $V$ .
If the edge is into the current vertex, then add the new out-vertex to $V$ . If it's an out of the current vertex, then move to that new vertex and add it to $V$ .
Repeat bullet points $2$ and $3$ .

Now, $G$ should be a directed tree with all vertices of degree $1$ except one has degree $0$ , which is the final vertex we end at. Call it $v$ . This takes $n-1$ queries.

Now query all the not queried edges that are coming out of the out degree $0$ vertex. This takes less than $n-1$ queries. If $v$ has out degree $\le 1$ , we're done, so assume it's $\ge 2$ .

Now, let $S$ be the set of vertices with out degree $\le 1$ in $G$ .
Claim: There are $\le 3$ cities with out degree $\le 1$ cities in Wonderland, implying $|S| \le 3$ .
Proof: If there are $\ge 4$ , then, just considering their $6$ roads, there must be $\ge 6$ out degrees in total for the $4$ vertices. Thus, by expectation, one of them will have out degree $\ge 2$ , a contradiction.
Claim: Furthermore, $|S| \le 2$ or else we're done.
Proof: Lets say $|S| = 3$ , then there exists a directed triangle in $G$ . We do casework to finish:

If the directed triangle has $v$ , then we just need to query each edge coming out of two other vertices. Since $|S| \le 3$ and $v \in S$ , we are done. This takes $\le 2n$ steps for $\le 4n$ total.
If the directed triangle does not contain $v$ , then remove $v$ and all edges from $v$ out of $G$ . The remaining graph is the tree mentioned after the bullet points. However, this tree thus contains a directed triangle, a contradiction.

Thus, this case can not exist, so we're done.

Now, if $|S| \le 2$ , we just query each edge coming out of these two vertices and we're done since this takes $\le 2n$ moves for $\le 4n$ total.

This post has been edited 2 times. Last edited by naonaoaz, Apr 30, 2024, 3:58 PM

Z K Y

The post below has been deleted. Click to close.

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

Physicsknight

641 posts

Physicsknight

#27 h Jul 17, 2024, 6:09 PM • 1 Y

Y by ehuseyinyigit

For $n$ is large enough, Alice has the stategy to determine the vertex has $\deg = 1$ in $3n + \mathcal{O}(1)$ questions like that scheme.
At first, we could cluster the set of vertices to each triple contain $3$ vertices.
In each triple, make $3$ question to determine those relations. After determining the direction bw them, we could sort them into $2$ category: $\text{Type 1}\, (\star)$ is a $K_3$ graph, each vertex has $\deg = 1$
$\text{Type 2}\,(\square)$ is a segment with one endpoint has $\deg = 1,$ the second has $\deg = 0.$
In this step, we use $\lfloor\frac{n}{3}\rfloor +\mathcal{O}(1)$ question.
$N_1$ group $(\star)$ and $N_2$ group $(\square),$ with $N_1 + N_2 = \lfloor \frac{n}{3}\rfloor= N.$
See this figure, with the number in each vertex is its deg value such that
$[asy] import graph; size(300); pair A = (0,0); pair B = (1,0); pair C = (0.5,sqrt(3)/2); draw(A--B, Arrow); draw(B--C, Arrow); draw(C--A, Arrow); label("1", (A+B)/2, N); label("1", (B+C)/2, E); label("1", (C+A)/2, W); pair D = (2,0); pair E = (3,0); pair F = (2.5,-sqrt(3)/2); draw(D--E, Arrow); draw(E--F, Arrow); draw(F--D, Arrow); label("2", (D+E)/2, N); label("1", (E+F)/2, NE); label("0", (F+D)/2, SW); draw((4,0)--(5,0), Arrow); draw((5,0)--(4,0), Arrow); label("1", (4.5,0), N); draw((6,1)--(6,0), Arrow); label("0", (6,0.5), E); label("1", (6,1), N); [/asy]$

Process those groups of $N_2$ first. In sequence, take 2 group $N_2,$ and make three question to query about those directions bw them. We get a group of $(\star),(\square)$ after this process with $\lfloor\frac{N_2}{2}\rfloor$ steps, we have $N_3$ groups $(\star)$ and $N_4$ groups $(\square),$ with $N_3 + N_4 = \lfloor\frac{N_2}{2}\rfloor.$ Continue this process with $N_4$ grp, until we carry out all $(\square)$ .

The number of questions need to process all $(\square)$ is $3\left(\lfloor\frac{N_2}{2} \rfloor+ \lfloor\frac{N_4}{2}\rfloor + \hdots + \lfloor\frac{N_{2k}}{2}\rfloor\right)$
$[asy] size(300); pair A = (0,1); pair B = (1,1); pair C = (0,0); pair D = (1,0); draw(A--B, dashed); draw(B--D, Arrow); draw(C--D, Arrow); draw(A--C, Arrow); label("(1)", (A+B)/2, N); label("(2)", (C+D)/2, S); pair E = (0,2); pair F = (1,2); pair G = (0,1); pair H = (1,1); draw(E--F, dashed); draw(F--H, Arrow); draw(G--H, Arrow); draw(E--G, dashed); draw(E--H, dashed); label("(1)", (E+F)/2, N); label("(2)", (G+H)/2, S); label("2", (E+G)/2, W); label("1", (F+H)/2, E); pair I = (2,2); pair J = (3,2); pair K = (2,1); pair L = (3,1); draw(I--J, dashed); draw(J--L, Arrow); draw(K--L, Arrow); draw(I--K, dashed); draw(I--L, dashed); label("(1)", (I+J)/2, N); label("(3)", (I+L)/2, SW); label("(2)", (K+L)/2, S); label("2", (I+K)/2, W); label("1", (J+L)/2, E); pair M = (1.5,0.5); pair N = (2.5,0.5); draw(M--N, Arrow); label("Type 2", (2,0.5), S); pair O = (3.5,0.5); pair P = (4.5,0.5); draw(O--P, Arrow); label("Type 1", (4,0.5), S); draw(P--O, Arrow); label("Type 2", (4,0), S); [/asy]$

Finish, process those groups of N1. Here, we have in total $N_1 + N_3 +\hdots N_{2k}+1$ groups like $(\star).$
In sequence, take 2 group $N_1.$ Make 3 questions to query about those directions bw them. In that case, we complete one $N_1$ and left one group $N_1.$ Continue this process, until we handle out all group $(\star)$ .

The number of questions need to process all groups type $(\star)$ is
In final, the total number of questions we need to find out the desire vertex has $\text{degree = 1 is} \,N_1 + N_3 +\hdots + N_{2k+1};$ with $N_3 + N_4 = \lfloor\frac{N_2}{2}\rfloor, N_5 + N_6 =\frac{ N_4}{2},\hdots$
questions = $N_1 + N_3 +\hdots+ N_{2k+1 }+ 3\left(\lfloor\frac{N_2}{2}+\hdots+\lfloor\frac{N_{2k}}{2}\rfloor\right) + N +\mathcal{ O}(1) \leq 3n + N + \mathcal{O}(1) =4n+\mathcal {O}(1)\,\mathrm{ questions}$
$[asy] size(300); pair A1 = (0,0); pair B1 = (1,0); pair C1 = (0.5,sqrt(3)/2); draw(A1--B1, Arrow); draw(B1--C1, Arrow); draw(C1--A1, Arrow); label("1", (A1+B1)/2, N); label("1", (B1+C1)/2, E); label("1", (C1+A1)/2, W); pair A2 = (2,0); pair B2 = (3,0); pair C2 = (2.5,sqrt(3)/2); draw(A2--B2, Arrow); draw(B2--C2, Arrow); draw(C2--A2, Arrow); label("1", (A2+B2)/2, N); label("1", (B2+C2)/2, E); label("1", (C2+A2)/2, W); pair A3 = (4,0); pair B3 = (5,0); pair C3 = (4.5,sqrt(3)/2); draw(A3--B3, Arrow); draw(B3--C3, Arrow); draw(C3--A3, Arrow); pair D1 = (A1+B2)/2; draw(A1..D1..B2, Arrow); label("1", D1, N); pair E = (1,0.5); pair F = (2,0.5); draw(E--F, Arrow); label("1", (E+F)/2, N); pair G = (3,0.5); pair H = (4,0.5); draw(G--H, Arrow); label("1", (G+H)/2, N); pair I = (5.5,0.5); pair J = (6.5,0.5); draw(I--J, Arrow); label("1", (I+J)/2, N); [/asy]$

Footnote-

Start by running a knock-out tournament. Consider a road $A\to B$ as a game where $A$ loses to $B.$ After $n-1$ games you have a tournament tree.

Now in phase 2 we do double elimination. In each iteration

Take the deepest tree node that hasn't lost twice resolving ties in some deterministic order.
Match it against another node that hasn't lost twice and such that they have not played each other.
Prefer the root as the opponent.

In all games of phase $2$ except possibly one somebody gets eliminated.

At some point you get stuck because the deepest uneliminated node A has played against every other uneliminated node. There are at most $n$ games in phase $2.$

Now in phase $3$ the remaining nodes play games against everybody they haven't played. If there are $1$ or $2$ nodes left, that's at most $2n$ more games, for a total of $< 4n.$

Now let's assume there are more than 2 nodes left after phase $2.$

Those remaining nodes have to be: $\text{A, A's }$ parent and root. It can't be A's children cause A is the deepest remaining, and it can't be anybody else because a game between A and anybody other than A's parent or the root would have eliminated one of them. The root lost to A.

Since $A$ is at depth $\geq 2,$ all the games in phase 2 were either:

some node at depth $\geq 2$ losing against the root, or
A winning against somebody

So in all the games of phase $2$ one of the 3 remaining nodes was involved. Those games won't get repeated in phase $3.$ So the total of phase $2 +$ phase $3$ is at most 3n games, for a grand total of $< 4n.$

This post has been edited 1 time. Last edited by Physicsknight, Jul 18, 2024, 5:56 PM

Z K Y

The post below has been deleted. Click to close.

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

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#28 h Sep 7, 2024, 5:11 PM

Y by

Use the obvious graph interpretation. After each question, label each vertex with its "known outdegree," the number of known edges that point away from the vertex.

If there are at least two vertices with label $0$ , we can choose any of them. The edge connecting them cannot be known, so Alice can query this edge to decrease the number of vertices with label $0$ until there is one left.

If there are $n \ge 3$ vertices with label $1$ , we claim that at least one edge connecting two of them is unknown. Since the number of known edges among these vertices is at most $n$ and the total number of edges is $\tbinom{n}{2}$ , we must have at least one unknown edge if $n \ge 4$ . If $n=3$ , then the only possibility without an unknown edge is if the three edges between them form a directed cycle. Consider the step when the last of these edges was determined. This must be a query between two vertices with labels $0$ and $1$ ; however, this never happens in our algorithm. Thus, Alice can always query until there are two vertices with label $1$ .

If there is an unknown edge between the two vertices, $u$ and $v$ , with label $1$ , then Alice can query this edge to make one of the vertices have label $2$ . If there is a known directed edge from $u$ to $v$ , then Alice can query the edge between $w$ , the vertex with label $0$ , and $v$ . If $v \rightarrow w$ , then $v$ will have label $2$ . Otherwise, $w$ will have label $1$ . Notice that we couldn't have had either $w \rightarrow u$ or $u \rightarrow w$ , as this would contradict $u$ and $w$ having labels of $1$ and $0$ , respectively. Thus, we can query the edge between $u$ and $w$ to make one of the vertices have label $2$ .

Either way, we have two remaining vertices with label less than $2$ and all other vertices with label $2$ . Since each query increases the sum of the labels by $1$ , this takes at most $2n-2$ queries. Alice can then query each of the unknown edges with endpoint at one of the two remaining vertices, which takes at most $2n-2$ queries. Thus, she can figure out whether each vertex has outdegree at least $2$ in $4n-4$ queries, as desired. $\blacksquare$

This post has been edited 1 time. Last edited by CyclicISLscelesTrapezoid, Sep 7, 2024, 5:11 PM

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

746 posts

Mathandski

#29 h Oct 9, 2024, 5:27 AM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

This post has been edited 1 time. Last edited by Mathandski, Oct 9, 2024, 5:28 AM
Reason: Bumping MOHs

Z K Y

The post below has been deleted. Click to close.

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

N3bula

261 posts

N3bula

#30 h Nov 6, 2024, 11:00 AM

Y by

If $n \leq 5$ it is clear that that by asking $4n$ or less questions she can
determine if their is a road with outdegree $\leq 1$ . Now we can consider $n \geq 6$ . For
$n\geq 6$ we can first preform an algorithm such that we label the vertices $1$ , $2$ , \dots, $n$ ,
we start on vertice $1$ and draw an edge to vertice $2$ , the the edge is such that $1 \rightarrow 2$ we move to vertice $2$ and
ignore vertice $1$ if $2\rightarrow 1$ we look at the edge from $1$ to $3$ , we repeat this process until we get
that we have $n-1$ vertice that we know have at least $1$ outgoing edge and one vertice with $0$ outgoing edges,
and we have used $n-1$ moves, now let $k$ be the vertice that so far has $0$ outgoing edges, now look at edges connected to $k$
until $k$ has outdegree of $2$ , after this preform a greedy algorithm where one selects two vertices which have outdegree of $1$ ,
and connects them if they arent already connected.
Claim
The greedy algorithm can be preformed until there is a maxium of $2$ vertices of degree $1$ left.

Suppose that there are $k$ vertices left after the greedy algorithm is preformed as each vertice has outdegree $1$ if
any of the vertices could be tested this would result in there being less than $k$ vertices left,
thus a $k$ clique must have been tested in the first move however the algorithm preformed in the first section
creates a tree thus there can't be more than $2$ vertices left over.

Claim
In the second set of moves at most $n+1$ moves were made

Every move other than the move that increased the degree of $k$ from $0$ to $1$ created a vertice with degree $2$ , thus
after this process we end up with at most $n$ vertices of degree $2$ thus at most $n+1$ moves were made.

Thus after this process at most $2n$ moves have been made and the number of vertices that could have outdegree $\leq 1$ is $2$ ,
thus by checking each vertice we end up with at most $4n-2$ moves being made which is less than $4n$ and we know if a vertice with outdegree $1$ exists.

Z K Y

The post below has been deleted. Click to close.

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

atdaotlohbh

185 posts

atdaotlohbh

#31 h Apr 6, 2025, 9:24 AM

Y by

When making a query $AB$ , if the result is WLOG $A \rightarrow B$ , say $B$ won in the match with $A$ .
We first arrange an olympic system (Round 1), so after $n-1$ matches every team except one has one loss and one team is undefetead, call that team $W$ . Let $L_1,\ldots,L_k$ be all the teams which lost to $W$ . Then no pair $L_iL_j$ has played so far because otherwise the loser of the match would have two losses. (Round 2) Hence, we can arrange an olympic system on $L_1,\ldots,L_k$ . After that one team, say $L_1$ , remained with only one loss, while all others already have at least two losses. Let the teams not mentioned so far be $M_1,\ldots,M_{n-k-1}$ . Now we make $L_1$ play with every $M_i$ until $L_1$ loses. There are two cases:
Case 1: $L_1$ finally lost. Then now it also has two losses. We continue to arrange matches between teams with one loss each until there are no more. Suppose after that process at least $3$ teams with one loss remained. Then every pair of them has already played in Round 1 which is impossible in the olympic system. Suppose two teams with one loss remained. Then they have already played in Round 1, say $X$ lost and $Y$ won. Because $Y \not \in \{L_1,\ldots,L_k \}$ , $Y$ and $W$ have never played so far. $X$ and $W$ also haven't played since otherwise $X$ would have two losses already. So we make two matches: $XW$ and $YW$ . If in $YW$ or $XW$ the team $W$ won, then either $X$ or $Y$ has lost twice. If in both $W$ lost, then $W$ lost twice. If after the process described earlier 1 team with one loss remained, we already have only two teams with at most one loss.
And so just like that we now after at most $(n-1)+(n-1)=2n-2$ games have at most two teams with at most one loss. We can play all matches possible with that two teams now, which is $2n-3$ more matches, to completely check both teams. And so we are done in at most $2n-5$ games.
Case 2. $L_1$ never lost. Then in (Round 2) it won everyone except for the teams it won in the Round 1. We can then continue to make matches between team with one loss each, until we are left with $L_1$ and some team $T$ . The key observation here is that $L_1$ has already played almost everyone else. It now only needs to play $k-1$ teams, $W$ needs to play $n-1-k$ teams and $T$ needs to play $n-1$ teams. Sum everything up to get $(n-1)+(k-1)+(n-1-k)=2n-3$ . In Round 1 and Round 2 $(n-1)+(n-2)=2n-3$ matches were played it total, thus we are done in just $4n-6$ matches.

This post has been edited 1 time. Last edited by atdaotlohbh, Apr 6, 2025, 9:25 AM

Z K Y

N Quick Reply