# Directed Graphs from numbers

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$$?

• 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? Nov 6, 2022 at 19:41
• 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.
– fljx
Nov 6, 2022 at 20:02
• @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. Nov 6, 2022 at 20:06
• 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 . Dec 21, 2022 at 17:45
• @HemantAgarwal All numbers are sent at once so even if you send 121 twice, its fine to interpret both as 12 -> 1. Dec 22, 2022 at 7:54

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.

• So the answer is "yes", right? Nov 7, 2022 at 4:27
• What does making vertices A -> 1 maximal mean? Nov 7, 2022 at 5:06
• @justhalf --- yes. Nov 7, 2022 at 6:22
• @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. Nov 7, 2022 at 6:28