A "dot" (commonly also called a "lattice point") is a point with integer coordinates.
In the plane, what is the total number of dots inside or on the boundary of the triangle with vertices (0,0), (x,0), (x,y) where x and y are positive integers?
In the event that it is not utterly obvious from the form of your answer that a whole number is being specified, give an independent argument to show this.
What total do you get if you count the three vertex dots together as just half a dot and any other boundary dots as half a dot each?
The formula I came up with is .5(x+1)(y+1) + 1 + .5(gcd(x,y)-1)
Explanation: (x+1)(y+1) would be the rectangle whose 4th corner is (0,y), but we only need half of this. Doing so cuts two of the corners off by a total of 1. Also each boundary point along the hypotenuse is cut in half, so you have to add those in.
Why is this a whole number? .5(x+1)(y+1) will be a whole number unless x and y are both even. .5(gcd(x,y)-1) will also be a whole number unless x and y are both even. If they aren't whole numbers they are both multiples of .5 so they will sum to a whole number.
The final answer is .5(x+1)(y+1) + 1 + .5(gcd(x,y)-1) - 2.5 - .5(gcd(x,y)-1) - (x-1) - (y-1)
= .5xy + .5x + .5y + .5 + 1 - 2.5 -x + 1 - y + 1
= .5(xy - x - y + 1)
= .5(x-1)(y-1)
|
Posted by Jer
on 2005-06-09 17:42:57 |