All points (x,y) with integer coordinates where 1≤x≤200 and 1≤y≤100 are marked in the coordinate system, 20000 points in total. How many lines of length 5 whose ends are marked points are there? (Mea Bombardelli)
Solution
A line segment of length 5 between two integer points must have a vector v=(a,b) with a2+b2=5. The integer solutions are (±1,±2) and (±2,±1).
So, the possible displacements are (1,2), (1,−2), (−1,2), (−1,−2), (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 1≤x≤200, 1≤y≤100.
Let us consider (a,b) with a=1,b=2.
The starting point (x,y) must satisfy 1≤x≤200−1=199 and 1≤y≤100−2=98.
So, for (1,2), the number of such segments is 199×98.
Similarly, for (1,−2), 1≤x≤199, 3≤y≤100 (since y+2≤100⟹y≤98, y≥1; for y−2≥1⟹y≥3), so 199×98.
For (2,1): 1≤x≤198, 1≤y≤99, so 198×99.
For (2,−1): 1≤x≤198, 2≤y≤100, so 198×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)
Calculate:
199×98=(200−1)×98=200×98−98=19600−98=19502
198×99=(200−2)×99=200×99−2×99=19800−198=19602
Sum: 19502+19602=39104
Total: 2×39104=78208
Answer:78208
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.