This can also be found in chapter 7.5 of Graham/Knuth/Patashnik "Concrete Mathematics". On Tue, Sep 16, 2014 at 7:17 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Is this perhaps related to Raney's lemma?
R.H. Jeurissen Raney and Catalan Discrete Mathematics Volume 308, Issue 24, 28 December 2008, Pages 6298–6307 http://www.sciencedirect.com/science/article/pii/S0012365X07009806
WFL
On 9/16/14, James Propp <jamespropp@gmail.com> wrote:
Can anyone with access to a copy of Yaglom and Yaglom's two-volume work "Challenging Problems with Elementary Solutions" give me a reference for their proof of the fact that, given a sequence of length 2n+1 consisting of n terms equal to -1 and n+1 terms equal to +1, there's exactly one integer k between 0 and 2n such that cyclically shifting the original sequence k positions to the left yields a sequence in which all non-empty partial sums are positive?
I know a nice picture proof of this, a version of which appears in Yaglom and Yaglom: Draw a lattice path of length 2n+1 consisting of diagonal steps in the (+1,+1) direction and (+1,-1) direction (northeast and southeast if you prefer), with northeast steps corresponding to +1's in the sequence and southeast steps corresponding to -1's in the sequence. Now repeat this finite lattice path infinitely often in both directions, obtaining a periodic infinite path whose slope is 1/(2n+1). Draw a line of this slope above the lattice path, and start lowering it until it just touches the lattice path. We need to show that the contact points are 2n+1 units apart in the horizontal direction. But this follows from the fact that n and n+1 are relatively prime.
I'd like to refer to the Yaglom and Yaglom problem and solution in an article I'm writing. I don't have a copy of Yaglom and Yaglom, but I bet many of you do!
(I think Y&Y use rightward and eastward steps, rather than northeast and southeast steps. But these memories are thirty years old.)
Thanks,
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun