TTN's Winning Entry

Rectangular grid has x intersections with segments AB.
(A(0,0),B(p,q)).

These x points made x-1 segments and obviously each of these segments goes 
through exactly one unit square so if we find the number of intersections 
we'd solve the problem.

Segment AB intersects with p+1 vertical and q+1 horizontal lines in
rectangular grid. It goes through gcd(p,q)+1 points which have both coordinates
integer (gcd(p,q)is greatest common divider of p and q).

So, at last we get
x= p+1+q+1-(gcd(p,q)+1)=p+q-gcd(p,q)+1

The answer is:
line AB passes through p+q - gcd(p,q) unit squares.

This project of the month is solved by the group TTM from V. gimnazija,
Zagreb,Croatia.

Tim's Winning Entry

Read Tim's Web Page

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

© 1994-2009 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.