Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Imagine an infinitely long sequence of squares where one of these squares contains a frog, and another square contains a fly.

For simplicity, let's number all of the (infinitely many) squares by assigning each an integer. We'll say that the frog starts in position 0, and will assign positive integers to the squares to the right of the frog and negative numbers to the squares to the left of the frog.

The frog can hop across the squares forward and backward, but can only make jumps of two different lengths: 3 and 7. For example, to get to square five to eat the fly, the frog might might jump forward seven squares to square 7, forward seven squares again to square 14, then back three squares three times to squares 11, 8, and (finally) 5.

1) Prove that, starting at position 0, the quantum frog can move to any square using only jumps of length 3 and 7.

2) Prove that in an optimal series of jumps from square 0 to square k, all jumps of the same distance must be made in the same direction. That is, all of the frog's jumps of distance 3 must be in the same direction, and all of the frog's jumps of distance 7 must be in the same direction (though these two directions don't have to be the same).

3) Prove that in an optimal series of jumps from square 0 to square k, the frog can never use jumps of size three more than six times.

share|improve this question
    
Taken verbatim from stanford.edu/class/archive/cs/cs103/cs103.1132/handouts/… –  Austin Mohr Jul 3 '13 at 4:03
4  
This question appears to be off-topic because it is about defacing your own posting to remove the actual question. –  Amzoti Jul 3 '13 at 5:46
add comment

2 Answers

up vote 2 down vote accepted

For question 2, if the frog made two jumps of the same length in opposite directions, it could omit those two jumps and end up at the same final destination. For question 3, if the frog made 7 or more jumps of size 3, then by question 2 they're all in the same direction, so 7 of them could be replaced by three jumps of size 7, leading to the same final result with fewer jumps.

share|improve this answer
add comment

Because $7 - 2 \times 3 = 1$, you can think of a jump of length 7 to the right followed by two jumps of length 3 to the left as a single jump of length 1 to the right. Reversing this will give a jump of length 1 to the left instead.

Now that we know how to jump one square at a time, it's easy to see why we can reach all the squares using only jumps of length $3$ and length $7$.

In general, this will always be possible if the two jump lengths have no common prime factors (coprime).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.