Aritra741's blog

[HELP]Number of lattice points (integer points) on a line segment with fractional endpoints
By Aritra741, history, 5 years ago, In English

Hi. I've been struggling to solve this problem from UVA.

It asks for the number of lattice points ( points with integer co-ordinates ) on a given line segment. But the endpoints on the segment can be fractions. I'll appreciate it a lot if someone tells me how this problem can be solved.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I looked at the problem; there's a pretty important point made in the problem statement. The points of the segment have exactly one digit after the decimal. One really common trick here (pops up when you deal with dollars as well, which have two points after the decimal point) is to multiply everything by a number so that your points are all integers. Here you can multiply by 10, and then your problem is reduced to finding all the integer lattice points (x, y) such that x and y are multiples of 10. Do you think figuring that out would be easier?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great observation, Thanks. It does sound easier, but I can only think of ways to find the number of total lattice points of the new line after multiplying by 10, not exactly the number of points which are multiples of 10. Could you please give more hints about how it can be done?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Hint: it's not a geometry problem, it's a number theory problem.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks. Kindly let me know if this approach is correct: Initially I have the equation of the line that goes through those two points, which is a linear diophantine equation. Multiplying that equation by 10 will produce a new equation. Now the task is to find the number of solutions of this new equation inside the given constraints*10.

        → Reply