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

Home > Numbers
Dotty Right Triangle (Posted on 2005-06-09) Difficulty: 3 of 5

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?

  Submitted by Richard    
Rating: 4.5000 (2 votes)
Solution: (Hide)
The rectangle with vertices (0,0), (x,0), (x,y), and (0,y) contains (x+1)(y+1) dots, and it contains two copies of the given triangle which share the same hypotenuse. Thus

2N - H = (x+1)(y+1)

where N is the number of dots that we are trying to find, and H is the number of dots on the hypotenuse. Now a dot is on the hypotenuse if and only if its coordinates (m,n) satisfy n/m=y/x. Thus nx and my are common multiples of x and y and therefore nx and my are each the same multiple of the least common multiple of x and y, namely xy/d, where d is the greatest common divisor of x and y. Hence nx=my=kxy/d so that n=ky/d and m=kx/d. The values of k that work are then 0, 1, ..., d so that H=1+d. Hence the formula

N = [1+d+(x+1)(y+1)]/2.

We may independently verify that this is a whole number by noting that if x and y have the same parity then d has that same parity as well, but if x and y have different parity then d has odd parity.

When the boundary dots are treated partially as described, the total then comes out to be exactly the area of the triangle.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re(2): SolutionRichard2005-06-14 22:05:26
re(2): Half solution -- the second halfBractals2005-06-09 21:17:31
re: SolutionCharlie2005-06-09 20:06:46
Solutionre: Half solution -- the second halfCharlie2005-06-09 19:36:35
SolutionHalf solutionBractals2005-06-09 18:43:12
SolutionSolutionJer2005-06-09 17:42:57
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information