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?

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 Half solution | Comment 2 of 6 |
The number of points on the diagonal
is the gcd(x,y)+1 (this is counting
the two vertices).
If we look at the number of points
in or on the corresponding rectangle
  (0,0) (x,0) (x,y) (0,y)
it is (x+1)*(y+1).
If we subtract the number of points
on the diagonal, divide by two, and
add back the points on the diagonal
we get the number of points in or on
the triangle:
  [ (x+1)*(y+1) + gcd(x,y) + 1 ] / 2

   x     y    (x+1)*(y+1)  gcd(x,y)
  even  even      odd        even
  even  odd       even       odd
  odd   even      even       odd
  odd   odd       even       odd
The numerator in all cases is even.
Have not looked at the second part yet.


  Posted by Bractals on 2005-06-09 18:43:12
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information