All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Dotty Right Triangle (Posted on 2005-06-09)

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?

 See The Solution Submitted by Richard Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 1 of 6

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

 Search: Search body:
Forums (0)