Bob and Alice play a game. Bob sends a sequence of positive numbers to Alice and using that information she forms a directed graph.

  • For each number in the sequence, she splits it into two non-empty parts without any leading zeroes and adds a directed edge from the vertex in the left part to the one in the right. For example, if she gets the integer $12034$, she can add an edge from vertex $1$ to vertex $2034$ or from vertex $120$ to vertex $34$ or from vertex $1203$ to vertex $4$.
    (12|034 is not a valid split because the right part contains a leading zero)

  • Alice splits each number in such a way that the resultant graph after adding all the edges has no cycles.

Before starting the game, Bob lets Alice know that there is an edge from vertex $1$ to vertex $1010$.

Can Bob find a strategy to send a sequence such that Alice always ends up with a graph containing an edge from vertex $1$ to vertex $21$?

  • $\begingroup$ Bonus: Originally I was trying to come up with a solution where Alice starts with an empty graph but couldn't reach one. Is it doable with that constraint? $\endgroup$ Nov 6, 2022 at 19:41
  • 1
    $\begingroup$ What happens if Bob sends a two-digit number followed by its reverse (e.g. 46 then 64)? Alice can only split them as 4->6 and 6->4, forming a cycle. $\endgroup$
    – fljx
    Nov 6, 2022 at 20:02
  • $\begingroup$ @fljx Then Alice cannot split it without a cycle so there are 0 valid options. Bob needs to send numbers such that Alice has at least one valid choice and for every choice an edge 1 -> 21 is there. $\endgroup$ Nov 6, 2022 at 20:06
  • $\begingroup$ Can't Bob just send 121 twice ? Alice might do 12->1 the first time around but the second time, she has to do 1-21 . $\endgroup$ Dec 21, 2022 at 17:45
  • $\begingroup$ @HemantAgarwal All numbers are sent at once so even if you send 121 twice, its fine to interpret both as 12 -> 1. $\endgroup$ Dec 22, 2022 at 7:54

2 Answers 2


If I'm understanding loopy walt's answer correctly, Bob only needs

five numbers

to force Alice to make an edge from $1$ to $21$. The process:

Step one: make $10$ maximal through $21$ and $110$. The remark about the alphabet is helpful, but the only symbols we need are 12A.
Step two: set up z with $10101$. Now there's a path from $2$ to $101$, so
Step three: set up y with $1012$. Now there's a path from $1$ to $12$, so we can finish with $121$.


First, note that as we cannot split before a zero, sequences of the form d00...00 behave like atoms. I.e. the whole problem is equivalent to one with countably many letters none of which behaving specially. As long as Bob sends a finite sequence of sequences we can assume the alphabet to be finite, as well.

Grouping whatever Bob sends by the number of letters we find:

1. 2-letter sequences must be consistent as they leave Alice no choice.

2. Without the given 1->AA edge (where we've written A for 10) Alice can for x>2 always choose to split all x-letter sequences (x-1)->1. As there are no edges ending at multi letter vertices at all it is clear that this is cycle free and does not contain 1->21. This answers the bonus.

3. With the given 1->AA all Bob needs to do is make vertices A>1 maximal amongst 1-letter vertices by sending sequences 1A,21,31,41,... and send all 3 letter sequences. To avoid the cycle 1->AA->z->1, all AAz (z!=A) must then split A->Az. To avoid the cycle A->Az->y->A all Azy (z!=A) must split A->zy, in particular, A->12 is in the graph. To avoid the cycle 1->A->12->1, 121 must split 1->21. As Alice can choose to split all sequences 1->(x-1) this is also consistent.

  • $\begingroup$ So the answer is "yes", right? $\endgroup$
    – justhalf
    Nov 7, 2022 at 4:27
  • $\begingroup$ What does making vertices A -> 1 maximal mean? $\endgroup$ Nov 7, 2022 at 5:06
  • $\begingroup$ @justhalf --- yes. $\endgroup$
    – loopy walt
    Nov 7, 2022 at 6:22
  • $\begingroup$ @ManishKundu It's A>1. And I mean A actually maximal, every single letter vertex has a forward path to A, and 1 just below, every single letter vertex except A has a forward path to 1. $\endgroup$
    – loopy walt
    Nov 7, 2022 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.