Maths Olympiad Prep

Library / /72 of 120

Geometry Difficulty 5.7 AIME, harder Prove it Croatia

All points (x,y)(x, y) with integer coordinates where 1x2001 \le x \le 200 and 1y1001 \le y \le 100 are marked in the coordinate system, 20000 points in total. How many lines of length 5\sqrt{5} whose ends are marked points are there? (Mea Bombardelli)

Solution

A line segment of length 5\sqrt{5} between two integer points must have a vector v=(a,b)\vec{v} = (a, b) with a2+b2=5a^2 + b^2 = 5. The integer solutions are (±1,±2)(\pm 1, \pm 2) and (±2,±1)(\pm 2, \pm 1).

So, the possible displacements are (1,2)(1,2), (1,2)(1,-2), (1,2)(-1,2), (1,2)(-1,-2), (2,1)(2,1), (2,1)(2,-1), (2,1)(-2,1), (2,1)(-2,-1).

For each such vector, we count the number of segments whose endpoints are both in the grid 1x2001 \le x \le 200, 1y1001 \le y \le 100.

Let us consider (a,b)(a, b) with a=1,b=2a = 1, b = 2.

The starting point (x,y)(x, y) must satisfy 1x2001=1991 \le x \le 200 - 1 = 199 and 1y1002=981 \le y \le 100 - 2 = 98.

So, for (1,2)(1,2), the number of such segments is 199×98199 \times 98.

Similarly, for (1,2)(1,-2), 1x1991 \le x \le 199, 3y1003 \le y \le 100 (since y+2100    y98y + 2 \le 100 \implies y \le 98, y1y \ge 1; for y21    y3y - 2 \ge 1 \implies y \ge 3), so 199×98199 \times 98.

For (2,1)(2,1): 1x1981 \le x \le 198, 1y991 \le y \le 99, so 198×99198 \times 99.

For (2,1)(2,-1): 1x1981 \le x \le 198, 2y1002 \le y \le 100, so 198×99198 \times 99.

Similarly for the negatives, but each segment is counted twice (once from each endpoint), so we only count each vector once and multiply by 2.

So, the total number is:

2×[(199×98)+(198×99)]=2×(199×98+198×99)2 \times [(199 \times 98) + (198 \times 99)] = 2 \times (199 \times 98 + 198 \times 99)

Calculate:

199×98=(2001)×98=200×9898=1960098=19502199 \times 98 = (200 - 1) \times 98 = 200 \times 98 - 98 = 19600 - 98 = 19502

198×99=(2002)×99=200×992×99=19800198=19602198 \times 99 = (200 - 2) \times 99 = 200 \times 99 - 2 \times 99 = 19800 - 198 = 19602

Sum: 19502+19602=3910419502 + 19602 = 39104

Total: 2×39104=782082 \times 39104 = 78208

Answer: 7820878\,208

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.