A programmable robotic mouse is placed at an intersection on a square grid, the borders of which are extendable as needed.

From its initial location the mouse moves one cell forward. It turns right with its next move incrementing by 1. This incremental process continues up to a certain constraint whereby the mouse resumes the process with a move of one space until that constraint is met again; continue this process until you either return to your starting position or you evidently will never return. What generalisations can be made about how variations of the value of the constraint affect the path forced upon the mouse?

M

Note:It will be necessary to test a range of constraining values.

Well, the problem wasn’t very specific for what kind of constraints there could be on the mouse. So I realize that what I have here does not cover the full scope for a generalized answer. But I think it is a start.

I looked at a constant constraint, such as "start over after your step is x units long" where x is constant from iteration to iteration. So the step pattern would be, for example: (1, 2, 3), (1, 2, 3), (1, 2, 3)…

I first checked out X=1 through X=3 and I started to think that as long as X is constant, you would always get back to your start spot. But then I checked out X=4 and found out that this was not the case because in this case you will never reach your start spot.

Then I noticed there had been a pattern and was pretty sure that I would find that for all X that are multiples of 4 you will never get back to your start spot, but for all other X you would. I checked out X=5 and X=6 just to make sure I wouldn’t have any immediate surprises, and then I felt comfortably sure about the following generality.

If Xmod4=0, you will never reach your start spot.
If Xmod4=1 or 3, you will reach your start spot after 4 iterations. If Xmod4=2, you will reach your start spot after 2 iterations.

Here’s why:

Let’s look at where the mouse starts an iteration of steps, noting not just her location, but her orientation as well.
After the iteration of steps, we again note her location and her orientation.
This relative change (translation and rotation) from beginning of iteration to end of iteration will be the same from one set of iterations to the next since the constraint is constant.

When Xmod4=0, her orientation at the end of the iteration will be the same as it was at the beginning of the iteration. This means the relative change from the beginning to the end of an iteration will only be a translation, no rotation. This means that iteration after iteration, her location will keep translating away and away in the same direction. So she will never get back to her original start spot.

When Xmod4=1 or 3, her orientation at the end of the iteration will be 90 degrees off from what it was at the beginning of the iteration (either CW or CCW). This means the relative change from the beginning to the end of an iteration will be a translation with a 90 degree rotation. Which means that if you draw a straight line from the beginning point to the end point of an iteration, the line to the end point of the NEXT iteration will be at a right angle to the first line. That probably made no sense. Let’s say the mouse starts at point A. She goes through her set of steps and completes her first iteration at point B. She goes through another set of steps and completes her second iteration at point C. AB will be perpendicular to BC. And the length of AB will be equal to BC. Do this two more times and we will have constructed a square. Because of this she will always end up back at her start spot after 4 iterations.

When Xmod4=2, her orientation at the end of the iteration will be 180 degrees off from what was at the beginning of the iteration. This means the relative change from the beginning to the end of an iteration will be a translation with a 180 degree rotation. Which means if you drew a straight light from the beginning point to the end point of an iteration, the line to the end point of the NEXT iteration will be 180 degrees from the first line. Let’s say the mouse starts at point A. She goes through her set of steps and completes her first iteration at point B. She goes through another set of steps and completes her second iteration at point C. The angle between AB and BC will be 180 degrees, and the length of AB will be equal to BC. Well, these are just two lines that are on top of each other. So that means we just constructed a line and retraced it. Because of this she will always end up back at her start spot after 2 iterations.

Now, it wasn’t explicitly stated that the constraint has to be a constant number. The constraint could be consecutive
whole numbers: (1), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5)…
odd numbers: (1), (1, 2, 3), (1, 2, 3, 4, 5)…
prime numbers: (1, 2), (1, 2, 3), (1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6, 7), (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)…
Fibonacci numbers: (1), (1), (1, 2), (1, 2, 3), (1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6, 7, 8)… *I know, I kind of skipped 0 and I kind of didn’t.

I did not look into these non-constant types of constraints so I have no generalizations on them at this time.

Posted by nikki on 2008-01-18 18:51:22