Thursday, September 24, 2009

Positive integer solutions to 4x + 5y < 1001

Find the number of solutions to the inequality 4x + 5y < 1001, where x and y are positive integers.
Posted by at
Labels: ,

2 comments:

  1. DavidSeptember 26, 2009 at 12:44 AM

    The answer is 24800.

    Integer solutions correspond to lattice points inside the right triangle with vertices (0,0), (250,0), and (0,200), together with the points on the hypotenuse, but excluding (250,0) and (0,200).

    We start with the rectangle with corners (0,0), (250,0), (0,200), and (250,200). The rectangle contains 251*201 = 50451 lattice points.

    The diagonal from (250,0) to (0,200) contains 51 lattice points. Of the remaining 50400 lattice points, half of them (or 25200) lie below the diagonal.

    To get the final answer, we add back the lattice points on the diagonal, and then subtract the lattice points on the axes.
    So the answer is 25200 + 51 - 200 - 250 - 1 = 24800.

    ReplyDelete
  2. UnknownSeptember 26, 2009 at 10:35 PM

    ;; Brute forced in scheme:
    (define (potd x c) (if (> 1001 (* 5 x)) (potd (+ 1 x) (+ c (floor (/ (- 1000 (* 5 x)) 4)))) c))
    (potd 1 0)

    ReplyDelete

Subscribe to: Post Comments (Atom)