Why we need to choose direction in the "marry the arrows" algorithm?

Question

In the article "Division by three" following algorithm is suggested for building a bijection between sets A and B, given that there's a bijection between {0,1}*A and {0,1}*B. First, we build a special kind of directed cycle graph where each edge designates an element from A or B, and direction is determined by whether we start/end in (0, _) or (1, _). Here's an illustration from the article itself.

Next, following algorithm is described (by matching parentheses it is meant to arrows in different directions):

So if there are only necklaces, and no infinite strings, we proceed as follows. We treat each necklace separately. First we try matching parentheses. If this, works, fine. If not, all the unmatched parentheses face the same way around the loop, and the way they face determines a direction around the loop. Let us say that the direction in which the arrows point is ‘down the street’; that is, the open ends of the unmatched parentheses face ‘up the street’. The unmatched parentheses alternate in color, so if every blue parenthesis marries the next unmatched (red) parenthesis up the street, we will have successfully paired up all the parentheses on the street.

What I miss from this is why we need to determine direction - why it won't be sufficient to just choose one direction, whether it will be up the street or down the street and "marry" the arrows?

Answer 1

This exact point was discussed in that paper few paragraph before your quote:

Imagine for a moment that the strings of arrows represent streets— circular drives, in the case of necklaces, and long boulevards in the case of infinite strings. If the arrows are good, straight, American arrows, it is very natural for each arrow to dream of marrying the arrow next door. The only difficulty is that there are two arrows next door, because there are two next doors. Of course since each arrow has a direction associated to it, it might be that they have in mind the arrow that their head is connected to, but this is going to cause all kinds of conflicts. For instance, in the example above, both b and c are going to want to marry $z$. $$$$ If only all the streets were one-way streets, then the blue arrows could resolve to marry the red arrow just up the street, and the red arrows could resolve to marry the blue arrow just down the street, and everything would be dandy. If only someone would go around and decide somehow or other for each street which way the traffic should go! But this is exactly the kind of thing we’re not allowed to ask for, if we want to steer clear of the axiom of choice. Unless we can describe a rule for determining the direction along a street, we’re out of luck

(Emphasize by me)

• as semi related note, the paper has a typo in the end of the paragraph that is immediately after what I quoted, it should have $g(a)=x,g(b)=z,g(c)=y$.

To me more precise, given a single necklace, we can choose a direction and match the red and blue arrows of this necklace using the "one way street" method, but the problem is that we may have infinitely many necklaces! We cannot chose a direction to all of the at the same time without choice (note that there is no difference between "downstreet" and "upstreet", choosing "upstreet" or "downstreet" is similarly to choose "left" and "right" from a pair, you can fix "left" and "right" for a single pair, but given infinite set of pairs, you cannot fix "left" and "right" for all of them at the same time without AC).

---

If you continue to read the infinite string case, the method they are using is exactly to "choose" direction for the string, but that choice is not random, they do some work to show that there is a way to determine the direction without the axiom of choice