In a grid rectangle 20210 × 1505, two diagonals are drawn, and all the cells containing segments of diagonals are painted. How many cells are painted?

  • $\begingroup$ Do you count cells or lines? I.e. 20210 x 1505 cells meaning 20211 horizontal lines and 1506 vertical lines or 20210 x 1505 grid intersection points meaning 20209 x 1504 cells? $\endgroup$ – loopy walt Apr 4 at 7:42

The answer is

42986 cells

That's because

in a $94\times7$ rectangle (1/46225th of the original one, since GCD of 20210 and 1505 is 215), a single diagonal will paint the following cells: a segment in row 1 (lowermost), then another segment in row 2, etc. up to row 7. The segments form a "ladder" (since the diagonal continuously rises when running left-to-right) and always overlap by 1 cell (since 94 and 7 are coprime, the diagonal does not run through the lattice points). The total length of the 7 segments is 94 (the entire width of the rectangle) plus 6 overlappings of 1 cell each, totaling to 100 (precisely, the columns 14, 27, 41, 54, 68 and 81 will be painted twice - the numbers are $\mathrm{ceil}\left(\frac{94k}{7}\right), k=1,2,\dots,6$).

In a large $20210\times1505$ rectangle, each of the diagonals runs through 215 such smaller $94\times7$ rectangles (if we divide the large rectangle into 46225 small ones). So, the two diagonals cover $2\times215\times100=43000$ squares, but 14 of them is covered by both (since $1505$ is an odd number, the diagonals intersect on the edge of a cell, not on a lattice point). So, we must subtract 14, and 42986 is the final answer.

  • 2
    $\begingroup$ Small nitpick: The diagonals do not intersect inside a cell. They should intersect exactly in the middle which with parities of numbers of rows and columns unequal must fall on a grid line. $\endgroup$ – loopy walt Apr 4 at 8:03
  • $\begingroup$ What is plus 6 ?? $\endgroup$ – MathR Apr 4 at 9:03
  • $\begingroup$ Thanks for pointing it out! Of course, they will interest strictly inside of a cell only when both width and height are odd. $\endgroup$ – trolley813 Apr 4 at 9:04
  • $\begingroup$ @Reza 7 segments will have 6 overlapping, namely those between segments #1 and #2, #2 and #3, etc. up to #6 and #7. $\endgroup$ – trolley813 Apr 4 at 9:05

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.