4
$\begingroup$

Consider a chessboard of size $8$ units $×$ $8$ units (i.e. each small square on the board has a side length of $1$ unit). Let $S$ be the set of all the $81$ vertices of all the squares on the board. What is the number of line segments whose vertices are in $S$, and whose length is a positive integer? (The segments need not be parallel to the sides of the board.)

This problem is from RMO 2017 Maharashtra and Goa Region.
I think I have successfully calculated the number of lines parallel to either of the sides of the chess board.
I found it to be $$1×9×2+2×9×2+3×9×2+...+8×9×2$$ (Am I right?)
Now, I am ready to count the number of non parallel lines. I find that there are only two pythagorean triplets-$(3,4)$ and $(8,6)$ up to $8$. What next? How to proceed? (Please tell me if I am wrong anywhere)

$\endgroup$
1
$\begingroup$

You did ok for the straight lines

Non-paralels are 3right4up, 3r4d, 4r3u, 4r3d and similar for 6,8

There is 4*6*5+4*3*1

$\endgroup$
  • $\begingroup$ Yes I also got $5×6×2×2$. Let me check the other. $\endgroup$ – ami_ba Oct 15 '17 at 15:14
  • $\begingroup$ Yes I also get $3×2×2×1$ $\endgroup$ – ami_ba Oct 15 '17 at 15:21
  • $\begingroup$ Please see my comment on the question $\endgroup$ – ami_ba Oct 15 '17 at 15:26
  • $\begingroup$ @Amityas that is correct, you see just move vector (3,4) around table, it may be placed on 30 positions. Same for vectors (3,-4),(4,3),(4,-3) $\endgroup$ – Djura Marinkov Oct 15 '17 at 15:27
  • $\begingroup$ you mean the PDF's? $\endgroup$ – ami_ba Oct 15 '17 at 15:29
4
$\begingroup$

To count the line segments parallel to an edge, first you pick a direction, horizontal or vertical, $2$ ways, then you pick a line $9$ ways, then you pick two points on the line $9 \choose 2$ ways. $2 \cdot 9 \cdot {9 \choose 2}=648$

For line segments not parallel to an edge, they must be the hypotenuse of a pythagorean triangle with sides less than or equal to $8$. The only ones of those are $3,4,5$ and $6,8,10$. For $6,8,10$ the $8$ has to be all the way across the board. There are three of those near each edge and two choices of the third point, so $4 \cdot 3 \cdot 2=24$ but we have counted each one twice as the triangle has two orientations for $12$. For $3,4,5$ the L of the $3,4$ can go in eight orientations, the $3$ can go in six locations in its row and the $4$ can go in five locations in its row. $8 \cdot 6 \cdot 5=240$ but again we have counted each one twice, so $120$

The grand total is $648+12+120=780$

$\endgroup$
  • $\begingroup$ Yes, I got the parallel lines correct. $\endgroup$ – ami_ba Oct 15 '17 at 15:10
  • $\begingroup$ I am not able to understand how it is $8×6×5$ $\endgroup$ – ami_ba Oct 15 '17 at 15:16
  • $\begingroup$ You counted some of them twice $\endgroup$ – Djura Marinkov Oct 15 '17 at 15:20
  • $\begingroup$ This is for Ross(my at the rate key is not working!)- I think Djura's ans. is correct $\endgroup$ – ami_ba Oct 15 '17 at 15:23
  • $\begingroup$ Please see my comment on the question $\endgroup$ – ami_ba Oct 15 '17 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.