Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

The Jumping Frog of Coordinate County

Date: 11/03/2009 at 12:56:16
From: Ryan
Subject: Fun and Interesting Math Problem Involving Coordinates

My friend gave me this problem and bet I couldn't solve it:

A frog starts at (0,0) on the Cartesian plane, and each minute jumps a
distance of exactly 1 unit to a point with rational coordinates.

(a) Show that it is possible for the frog to reach the point (1/5,1/17)

(b) Show that the frog can never reach the point (0,1/4)

I'm not sure, but I think this is one way you can do it. For part (a),
draw the circle with radius 1 and center (0,0) and also with radius 1
and center (1/5,1/17). Where these two circles intersect is where the
frog can jump to from (0,0) and then it will also be 1 unit away from
(1/5, 1/17) since it is the intersection of the two points. We just
need to show that the intersection of the two circles occurs on a
point with rational coordinates.

Similarly, you can do that with the point (0,1/4), and show that the
intersections of the two circles does not occur on rational coordinates.

I only have two issues with this way:

1) I don't know how to find the intersection points of two circles
2) The method I used only has the frog moving twice. There might be a
way the frog can go to the given coordinates in more than 2 moves.

Help is very much appreciated :)




Date: 11/06/2009 at 06:32:25
From: Doctor Jacques
Subject: Re: Fun and Interesting Math Problem Involving Coordinates

Hi Ryan,

You've done some good thinking, but as you said, your method assumes
exactly two jumps, which is a pretty strict limitation.  We need to
think in a more general case.  Let us start with some preliminary
observations.

When the frog jumps from one rational point to another, the
coordinates of the movement vector are differences of rational
numbers, and therefore rational numbers themselves.  We may write that
movement vector as (p/q, r/s), where p, q, r, s are integers, and we
may assume that both fractions are in lowest terms, i.e., gcd(p,q) =
gcd(r,s) = 1; we also assume that the denominators q and s are
positive.

If this vector has length 1, the Pythagorean Theorem gives:

  (p/q)^2 + (r/s)^2 = 1
  p^2*s^2 + q^2*r^2 = q^2*s^2      [1]

Let us look at [1] more closely. q^2 divides the LHS, and,
obviously, q^2 | (q^2*r^2) ("|" means "divides").  We can therefore
conclude that q^2 | (p^2*s^2).  As we assumed that gcd(p,q) = 1, this
implies that gcd(p^2,q^2) = 1 and q^2 | s^2.  In the same way, we can
show that s^2 | q^2.  The conclusion is that q^2 = s^2; as we wrote
the fractions with positive denominators, this shows that q = s : if
the fractions are written in lowest terms, the denominators are the
same.

This allows us to write the movement vector as (p/q, r/q), and we
have:

  p^2 + r^2 = q^2                   [2]

where p, q, and r are integers and gcd(p,q) = gcd(r,q) = 1.  Note
that this implies gcd(p,r) = 1, since any common factor of p and r
divides q.  In other words, (p,q,r) is a primitive Pythagorean triple
(PPT).  If you are not familiar with those, you can read more in our
FAQ:

  Pythagorean Triples
    http://www.mathforum.org/dr.math/faq/faq.pythag.triples.html 

Let us return to the problem at hand.  To go from (0,0) to
(1/5,1/17), we may try to combine two movements: (1/5,0) and
(0,1/17).  Furthermore, to execute the movement (1/5,0), we may try
to use only rational points whose coordinates are multiples of 1/5
(there may be other methods, be we must only show that the movement
is possible).

If we "zoom in" by a factor of 5, we will only use points with 
integer coordinates, but our movement vectors will have length 5
instead of 1.  If (x,y) is one such vector, we will have:

  x^2 + y^2 = 5^2                    [3]

For each movement (x,y), (x,y,5) is a Pythagorean triple (not
necessarily primitive).  There are essentially two types of PT with 5
in the third position:

 (1) : (4,3,5)
 (2) : (5,0,5)

and those that can be obtained from them by changing the sign of one
or both coordinates, and by interchanging x and y.  In the original
grid, these movements correspond to (4/5, 3/5) and (1,0).  Note that
we cannot use only movements of type (2), since that would only allow 
us to reach integer points in the original grid.

In the zoomed grid, we must reach the point (1,0), and we will try
to do this using the vectors (4,3), (5,0) and those obtained by
changing signs and swapping x and y.

As we may use the vectors (5,0) and (0,5), we may try to solve the
problem using only vectors of type (1) (associated with (4,3)) and
working modulo 5.  To summarize, we reduce the problem to:

Find a list (possibly with repetitions) of vectors from the set:

  {(4,3),(4,-3),(-4,3),(-4,-3),(3,4),3,-4),(-3,4),(-3,-4)}

such that the sum of the vectors of the list is congruent to (1,0)
(modulo 5).

Note that we may use integer coefficients to express the fact that a
vector is used more than once; for example, we may write:

  2(4,3) = (4,3) + (4,3)
         = (8,6)
         = (3,1)  (mod 5)

and, as for each vector (x,y), there is a corresponding vector 
(-x,-y), we may also use negative integers, by interpreting
(-1)(x,y) as (-x,-y).  This allows us to use all the facilities of
modular arithmetic.

In this case, we will try to use only the vectors:

  u = (4,3)
  v = (4,-3)

and we must find integers m and n such that:

  mu + nv = (1,0)   (mod 5)                [4]

By equating corresponding coordinates, [4] can be written as two
congruences:

  4m + 4n = 1   (mod 5)                    [5]
  3m - 3n = 0   (mod 5)

The second congruence shows that we must take m = n (mod 5), and the
first congruence becomes:

  8m = 3m = 1   (mod 5)                    [6]

The general technique for solving this type of congruence is to use
the Extended Euclidean Algorithm; you can read more on this in:

  Euclid's Extended Algorithm
    http://mathforum.org/library/drmath/view/51616.html 

However, in this case, we can easily find the solution m = 2 by
trial and error.  Using the fact that n = m, we substitute in [4],
and we find:

  2u + 2v = 2(u + v)
          = 2(8,0)
          = (1,0)   (mod 5)

as expected.

To get the solution to the original problem, we must retrace the
other steps backward.  First, we convert the congruence modulo 5 to
an ordinary sum.  As we actually have:

  2u + 2v = (16,0)

we see that, in order to get (1,0), we must subtract 3 times the
vector (5,0), or, equivalently, we must add three times the vector
(-5,0).

In the zoomed grid, this gives:

  2(4,3) + 2(4,-3) + 3(-5,0) = (1,0)

where all the steps have length 5.  In the original grid, we divide
everything by 5, and we get:

  2(4/5,3/5) + 2(4/5,-3/5) + 3(-1,0) = (1/5,0)

and this shows that we have executed a movement of (1/5,0) in seven
steps of length 1.

In this particular case, there is a shorter solution, using the
vectors (3/5,4/5) and (3/5,-4/5):

  (3/5,4/5) + (3/5,-4/5) + (-1,0) = (1/5,0)

in which we reach the target in three steps.  I did not start with 
that one, because I wanted to illustrate the solution of the 
congruence [6], which may be required in the general case.

To get to the point (1/5,1/17), we must still execute a movement
(0,1/17).  The technique is the same, and I will let you work this
out, using the fact that:

  8^2 + 15^2 = 17^2

Before looking at the second part of the problem, let us examine
what we did.  We wanted to build a movement of (1/q,0) (to get
(p/q,0), we simply repeat the movement p times).  We started with a
primitive Pythagorean triple (a,b,q), and we tried to find an
integer m such that:

  m(a,b) + m(a,-b) = 2m(a,0) = (1,0)  (mod q)

which leads to:

  m(2a) = 1    (mod q)      [7]

Because (a,b,q) is a primitive triple, we have gcd(a,q) = 1.  *If q
is odd*, we also have gcd(2a,q) = 1, and this is precisely the
necessary condition for the congruence [7] to have a solution
(because any common divisor of 2a and q must divide 1).  This means
that the above technique will work if both of these conditions are
met:

  (1) There must be a primitive Pythagorean triple with q in the third
      position.
  (2) q must be odd

(in fact, the second condition results from the first, since the
third member of any PPT is always odd).

Note that neither of these conditions is satisfied with q = 4.  This
shows that we cannot use the same technique to get to the point
(0,1/4); however, this does not exclude the existence of another
method.  To prove that no such method exists, we must think a little
further.

Remember that we showed that any rational vector of length 1 can be
written as (p/q,r/q), where both fractions are in lowest terms, and
the denominators are the same.

We will now show that the common denominator q must be odd.  Assume
that q is even, and that (p/q,r/q) has length 1.  We have:

  p^2 + r^2 = q^2             [8]

As q is even, q^2 is a multiple of 4.  This means that p and r must
be both odd or both even.  The first case cannot happen, because, if
p is any odd number, we have p^2 = 1 (mod 4), and [8] becomes:

  1 + 1 = 0   (mod 4)

which is obviously false.  We conclude that p and r are both even,
but this contradicts the fact that p/q and r/q are in lowest terms.

This shows that rational vectors of unit length always have odd
denominators when written in lowest terms.  However, to get a sum of
such vectors equal to (0,1/4), we would need to have at least one
vector with a denominator divisible by 4, and we have just showed
that this is impossible.

Please feel free to write back if you require further assistance.

By the way, nice problem !


- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 




Date: 11/06/2009 at 15:33:40
From: Ryan
Subject: Thank you (Fun and Interesting Math Problem Involving
Coordinates)

Thank you so much.  You are the greatest :).
Associated Topics:
College Coordinate Plane Geometry
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/