[math-fun] Seeking Yaglom and Yaglom help
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
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
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
This can also be found in chapter 7.5 of Graham/Knuth/Patashnik "Concrete Mathematics".
Which I find available online at https://notendur.hi.is/pgg/(ebook-pdf)%20-%20Mathematics%20-%20Concrete%20Ma... Whit
participants (4)
-
Fred Lunnon -
James Propp -
Michael Collins -
Whitfield Diffie