The Jumping Frog of Coordinate CountyDate: 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 :). |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/