## Monday, January 30, 2006

### Not All Odd. Topic: Number Theory/Geometry. Level: AIME.

Problem: Show that there do not exist four lattice points such that the pairwise squares of the distances between the points are all odd integers.

Solution: WLOG, assume that one of the points is the origin. We can do so because it can just be translated to any other point in the plane. Let the other points be $(x_1,y_1)$; $(x_2,y_2)$; and $(x_3,y_3)$.

Since the origin is one of our points, we know $x_1^2+y_1^2$, $x_2^2+y_2^2$, and $x_3^2+y_3^2$ are all odd. So each pair $(x_i,y_i)$ for $i= 1,2,3$ must have one odd and one even (so that the sum of the squares will be odd). Then by Pigeonhole, we have two $x$'s with the same parity. Then since the $y$'s have the opposite parity as the $x$'s, they are also the same.

Let $(x_a,y_a)$ and $(x_b,y_b)$ be the points with the same parity on both coordinates. Then $x_a-x_b$ and $y_a-y_b$ are both even. Hence the square of the distance between these two points is $(x_a-x_b)^2+(y_a-y_b)^2$, which is even because the sum of two even numbers is even. Therefore, not all the pairwise squares of distances can be odd. QED.

--------------------

Comment: Originally came from a different problem, which I misread and came up with a solution for this problem instead. Well, anyway, it's not particularly difficult, but it's nice to WLOG a point to the origin and make things cleaner, as you can probably tell.

--------------------

Practice Problem: (Olympiad Problem Solving MidTerm) Show that there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers. (Note: They don't have to be lattice points; that's where I misread it.)