General Question

sunssi's avatar

Working out how many left and right turns I can take before I run into my path?

Asked by sunssi (120points) June 13th, 2011

http://www.youtube.com/watch?v=Gx5D09s5X6U&feature=player_detailpage#t=45s

Got the question from this but I can’t seem to work it out

watch the video for a better understanding of the question

Observing members: 0 Composing members: 0

5 Answers

6rant6's avatar

Hm….

Well if there are 10 segments, then there are 9 joins.

Each joint can be bent left, right or straight. So an upper bound would be 3^9 = 19683.
That doesn’t account for the “fail” when a snake crosses itself. So the answer is less than that.

You can’t just tally the lefts or rights either. Because LLSLSL is okay, but LLLLSS is not.

roundsquare's avatar

Not sure what the answer is, but I would bet you can use induction. Try to compare n segment snakes to n-1 segment snakes.

gasman's avatar

Can a path begin with four left turns or four right turns? Is that considered a “collision” or self-intersection? Or does it depend on the next turn after that?

gasman's avatar

I found a whole book on self-avoiding walks at Amazon for a mere $79.11.

But at Wolfram MathWorld it says:
Consider a self-avoiding walk on a two-dimensional n×n square grid (i.e., a lattice path which never visits the same lattice point twice) which starts at the origin, takes first step in the positive horizontal direction, and is restricted to nonnegative grid points only. The number of such paths of n=1, 2, ... steps are 1, 2, 5, 12, 30, 73, 183, 456, 1151, ...

It links to a longer list of

Number of inequivalent self-avoiding walks of length n on a 2-D lattice which start at origin, take first step in {+1,0} direction and if any steps are vertical, a step up is taken before a step down.”

*1, 2, 5, 13, 36, 98, 272, 740, 2034, 5513, 15037, 40617, 110188, 296806, 802075, 2155667, 5808335, 15582342, 41889578, 112212146, 301100754, 805570061, 2158326727, 5768299665, 15435169364, 41214098278, 110164686454

These numbers are how many different paths of a given length you can take before ever running back into yourself.

gasman's avatar

Correction: That’s how many paths fit in an N x N grid, not paths of length N.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther