It seems neither Gareth McCaughan's proof nor my problem are really new... Wm.Feller: Probabillity Theory, vol I, section III.9 (see also III.1) discusses "Galton's rank order test" and gives essentially the same result & proof, plus a bit more, although I like G.McC's proof's details more. It seems some version of this result has been rediscovered at least 4 times. Apparently Francis Galton in 1876 was looking at some data of Ch.Darwin and deduced a totally unjustified conclusion from it because he did not understand that, due to G.McC's proof, the vector domination probability is actually quite large. His name was then immortalized in honor of his stupid error. J.L.Hodges Jr: Galton's rank order test, Biometrika 42 (1955) 261-262. Balazs Montagh: A simple proof and a generalization of an old result of Chung and Feller, Discrete Mathematics 87,1 (Jan. 1991) 105-108. K.L. Chung and W. Feller: Fluctuations in coin tossing, Proc. Nat. Acad. Sci. USA 35 (1949) 605-608. Montagh proves it using this CYCLIC LEMMA: For any k with 1<=k<=N, if a1,a2,...,aN is a sequence of integers with sum=1, then there is exactly one cyclic shift of this sequence having exactly k positive partial sums. Lemma attributed to G.N.Raney, Trans.Amer.Mathl Soc. 94 (1960) 441-451. A more general version of the cycle lemma is given by Nachum Dershowitz & Shmuel Zaks: The Cycle Lemma and Some Applications, European J. Combinatorics 11,1 (1990) 35-40 http://www.cs.tau.ac.il/~nachum/papers/CL.pdf http://www.sciencedirect.com/science/article/pii/S0195669813800534 who also give references showing it too has been rediscovered some ghastly number of times. So anyhow, in Gareth McCaughan's proof, we could at some point consider the 2N-character strings over the 2-letter alphabet "(" and ")" having exactly N of each, regard bigrams ((=2, ()=)(=0, ))=-2 to get a N-integer sequence, adjoin the number "1" to said sequence, apply cyclic lemma to deduce exactly 1 cyclic shift of each sequence has all partial sums positive and hence yields balanced parentheses in original problem.