Problem #150

A lattice points puzzle
Public 08/06/14 10xp Math 100.0%

Condider A(x_a,y_a), B(x_b,y_b), C(x_c,y_c), D(x_d,y_d) lattice points in the first quadrant (i.e. coordinates with integer x,y; x>=0 and y>=0).

AB segment is parallel to DC and AD parallel to BC.

Consider N points (M1, M2,..,MN) on BC segment that split BC into N equal segments:
For x_c>x_b and y_c>y_b
M1(x_b+1*(x_c-x_b)/N, y_b+1*(y_c-y_b)/N),
M2(x_b+2*(x_c-x_b)/N, y_b+2*(y_c-y_b)/N),
MN(x_b+N*(x_c-x_b)/N, y_b+N*(y_c-y_b)/N)=C(x_c,y_c)

M1, M2,..,MN are not necessarily lattice points but all the line segments drawn from A to M1,M2,..,MN cross BD segment at lattice points.

What is the smallest area of ABCD you can get for N=1000?

Input format: Area(ABCD) Mod 10^9.

You need to be a member to keep track of your progress.

Time may end, but hope will last forever.

Other Challenge Sites