Sunday, May 12, 2013

Putnam 2010: Part 2

Today, I took the second part of the 2010 Putnam. This part was actually a lot harder than previous one, so I'm not surprised I only got one problem here as well. My solutions plus preliminary work put my score at maybe a 24-25, which is actually outside the top 500 for this exam, which is quite dismal.
I am going to chalk it up to my not thinking straight, coupled with some stress due to upcoming exams.

Given that A, B, and C are noncollinear points in the
plane with integer coordinates such that the distances
AB, AC, and BC are integers, what is the smallest
possible value of AB?

For convenience, let A be (0,0). (If you have a triangle that satisfies the statements, you can translate it any of its points to the origin, as you are subtracting integers from all the coordinates)

After some experimentation, I got a value of 3. (Achieved by B=(0,3), C=(4,0), or, if that's too mainstream for you, (10,24)).

I will now proceed to prove that this is as small as you can get, i.e. that AB=1 and AB=2 result in some ridiculous things.

The only way we can get AB=1 or AB=2, is if B=(0,1) or (0,2) (we can switch x and y coordinates, or replace them with negatives, but this can really just be fixed by flipping or switching our axes, so we don't really care), this is true because if B is not on the y-axis, then it has points (x,y), such that x^2 + y^2=1 or 4, and x,y are integers, which obviously cannot happen without one of them being 0.

If AB=1, the B=(0,1), let C be the point (x, y+1). Since AC is an integer, we have that x^2 + (y+1)^2=d^2 (by the Euclidean distance formula) Similarly, since BC is an integer, we have x^2 + y^2=c^2, so we get d^2=c^2+2y+1. However, y<c*, and (c+1)^2=c^2+2c+1>c^2+2y+1, so d^2 is between c^2 and (c+1)^2, so it cannot be the square of an integer. Thus we have a contradiction and AB cannot be 1.

if AB=2, then we do the same thing, except call C (x, y+2).

Using similar, equations, we get d^2=c^2+4y+4.  However, y<c, and (c+2)^2=c^2+4c+4, so c^2<d^2<(c+2)^2, so d^2=(c+1)^2, as d^2 is the square of an integer. So, 4y+4=2c+1, which is false because the left hand side is even (multiple of 4), and the right hand side is odd (one plus a multiple of 2).  Again, we reach a contradiction. So AB cannot be 1 or 2, and thus has smallest value 3.

*y<c because x is not equal to 0, and x^2+y^2=c^2. If x was 0, then both B and C would be on the y-axis, and then A,B,C would be co-linear.



No comments:

Post a Comment