Shortest pattern

Question:

Hansel and Gretel are taking a walk in the forest and want to find their way home. As they walk, they leave a repeating pattern of 1s and 0s behind them that they can follow home. What is the length of the shortest pattern such that if you happen along their trail, you can determine with certainty which direction they were going?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: One solution is 010011, and it is probably the shortest. In a repeating series of this pattern, we may get . . . 11010011010011010011010011 . . . . If we are to look through the sequence, we find that we can match the pattern 010011 but not the reverse pattern, 110010. Hence we know which direction the person was traveling.

Answer: 010011.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s