Directed Graphs from numbers

Question

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

Answer 1

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

Answer 2

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.