3

I read a book containing competition level problems. I was unable to solve the following:

Consider an $n\times m$ grid. A paintbrush whose width is the same as the width of a grid square is used to paint a line from one corner of the grid to the opposite corner. How many squares will have paint in their interiors?

How can I solve this?

student
  • 33
  • 2
    Making a picture of an example would be helpful in seeing what happens. When the brush begins to leave the first corner square, what adjoining squares must also receive paint? Which ones get paint as the next square along the diagonal is painted? Is there an easy way to count the squares on either side of the squares along the diagonal, and thus produce a formula for the total number of squares with paint on them? Does the ratio of $ \ n \ $ to $ \ m \ $ affect the result? – colormegone May 29 '13 at 19:06
  • At least the center of the paintbrush goes throught $m+n-(m,n)$ points but I don't see how many extra squares gets paint as the brush width is positive. – student May 29 '13 at 19:11
  • @student You'd need to clarify how the paintbrush moves. Is the paintbrush held perpendicular wrt the diagonal? Or is it held parallel wrt to one of the grid lines? This could affect the answer slightly. – Calvin Lin May 29 '13 at 19:14
  • @CalvinLin True. That wasn't explained in the problem. – student May 29 '13 at 19:18
  • 1
    I am assuming the intent of the problem is that the brush is used in the broadest fashion. You could think of the lattice formed by the vertices of the square; the diagonal line passes from (0,0) to (n,m). The brush has width 1; we will want to count a square for every lattice point that the line with slope m/n passes within 1/2 unit of. (The formula should also be "symmetrical" for an exchange of m and n, since it doesn't matter whether the overall rectangle of squares is oriented "long-ways" or "tall-ways".) – colormegone May 29 '13 at 19:19
  • @RecklessReckoner: correct, but it may differ depending on whether the brush is along the $m$ direction or the $n$ direction. For example, in a $ 2 \times 20$ rectangle, if the brush is along the $2$ direction every square will get paint. If it goes the other way, it will be rather fewer. – Ross Millikan May 29 '13 at 20:16
  • @RossMillikan I'm afraid I don't follow that: the brush is to be taken diagonally through the rectangle; at least, that is how I'm interpreting "opposite corner" of the grid. Otherwise, the problem isn't all that interesting. – colormegone May 29 '13 at 20:23
  • @RecklessReckoner: True, but if in my $2 \times 20$ example, the $20$ direction is horizontal, the brush is horizontal, and the center of the brush starts at $(\frac 12, 2)$ and ends at $(19\frac 12,0)$, then the lower left $8$ squares and the upper right $8$ squares get no paint. – Ross Millikan May 29 '13 at 20:33
  • @RossMillikan I think I see the source of the disagreement here: we are picturing different starting points. I am considering starting the brush with its width perpendicular to the diagonal at all times, beginning the stroke with the center of the brush right at the vertex, and continuing until the center of the brush reaches the far vertex. In that case, whether you work with a 2 x 20 or a 20 x 2 grid is just a matter of which direction you view it. We are tracing parallel, but shifted, paths (I think possibly different brush orientations as well...). – colormegone May 29 '13 at 20:49
  • @RecklessReckoner: I am also keeping the brush within the grid. I don't know if that is required in the original problem. – Ross Millikan May 29 '13 at 21:09

1 Answers1

3

Hint: how many vertical and horizontal lines does the paintbrush cross? You need to think about the width of the brush. Draw a picture for a few small cases.

Ross Millikan
  • 374,822