Wikipedia:Reference desk/Archives/Mathematics/2012 November 14

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 14

2012x2015

Hello all. This is a puzzle that was in the newspaper (no prize or anything like that, don't worry); usually they are pretty easy but this one had me stumped. It went: Consider a 2012x2015 rectangle. Divide it into unit squares (1x1). How many of these unit squares does a diagonal of this rectangle pass through? I did some back of the envelope work with simpler squares (2x3, 3x5) and estimated that it had to be in the ballpark of 4030, but I couldn't find an exact answer (as 2012 and 2015 are coprime). I think I'm missing something really simple but my brain isn't working today. Help? 24.92.74.238 (talk) 03:49, 14 November 2012 (UTC)

Well, if it was exactly square, the answer would be the length of a side. Since it's slightly off square, I'd say it should be about double the longest length, or 4030. I assume that's how you got that answer. Not sure how to find the exact answer, though. StuRat (talk) 06:32, 14 November 2012 (UTC)

The answer is 4026. If you look at the line $y={\frac {2012}{2015}}x$, a segment of $x\in [m,m+1]$ will usually pass through 2 squares, but only one if for some integer n, $n\leq {\frac {2012}{2015}}x<{\frac {2012}{2015}}(x+1)\leq n+1$. This happens if $2012m\in \{0,1,2,3\}\ \mathrm {mod} \ 2015$ or equivalently $3m\in \{0,2012,2013,2014\}\ \mathrm {mod} \ 2015$. The solutions are $m\in \{0,671,1343,2014\}$. -- Meni Rosenfeld (talk) 06:35, 14 November 2012 (UTC)

I just ran a simulation and got 4025. You didn't count both (0,0) and (2012,2015) as squares, did you ? StuRat (talk) 07:07, 14 November 2012 (UTC)

No, I didn't. My result is also confirmed by 1Ouch0's solution, which is much more elegant (and general) than mine and easily verifiable for some simple special cases such as nXn and nX1.

Can you share your code? -- Meni Rosenfeld (talk) 07:45, 14 November 2012 (UTC)

Included below. StuRat (talk) 08:26, 14 November 2012 (UTC)

Simulation code (FORTRAN).

program DIAGONAL implicit none logical*1 TILE_OCCUPIED(0:2016,0:2016) integer*2 I,J,K,COUNT real*8 X,Y Initialization: do I = 0,2016 do J = 0,2016 TILE_OCCUPIED(I,J) = .false. enddo enddo COUNT = 0 Body: do K = 1,2015 X = 1.0*K - 0.00000001 Y = X*2012/2015 I = X ! Truncates. J = Y ! Truncates. if (.not. TILE_OCCUPIED(I,J) .and. (I .gt. 0) .and. (J .gt. 0)) then TILE_OCCUPIED(I,J) = .true. COUNT = COUNT + 1 print *,"Tile",COUNT,"= (",I,",",J,")" endif X = 1.0*K + 0.00000001 Y = X*2012/2015 I = X ! Truncates. J = Y ! Truncates. if (.not. TILE_OCCUPIED(I,J) .and. (I .gt. 0) .and. (J .gt. 0)) then TILE_OCCUPIED(I,J) = .true. COUNT = COUNT + 1 print *,"Tile",COUNT,"= (",I,",",J,")" endif enddo Termination: print * print *,"Count = ",COUNT end

Simulation solution set.

Tile 1 = ( 1 , 1 ) Tile 2 = ( 2 , 1 ) Tile 3 = ( 2 , 2 ) Tile 4 = ( 3 , 2 ) Tile 5 = ( 3 , 3 ) Tile 6 = ( 4 , 3 ) Tile 7 = ( 4 , 4 ) Tile 8 = ( 5 , 4 ) Tile 9 = ( 5 , 5 ) Tile 10 = ( 6 , 5 ) Tile 11 = ( 6 , 6 ) . . . (See the rest here: [1].) . . . Tile 4016 = ( 2010 , 2007 ) Tile 4017 = ( 2010 , 2008 ) Tile 4018 = ( 2011 , 2008 ) Tile 4019 = ( 2011 , 2009 ) Tile 4020 = ( 2012 , 2009 ) Tile 4021 = ( 2012 , 2010 ) Tile 4022 = ( 2013 , 2010 ) Tile 4023 = ( 2013 , 2011 ) Tile 4024 = ( 2014 , 2011 ) Tile 4025 = ( 2015 , 2012 ) Count = 4025

Your solution set is missing (2014,2012). Which is a result of using an incorrect offset for the diagonal. In your calculation x=2 corresponds to the right edge of the leftmost square, which means the corresponding y-value is 1 + 2012/2015, and not 2*2012/2015 as in your code. By the time it gets to x=2015-ε, it is thinking it is exiting (2014,2011) through a corner.

It's better to think of leftmost square as [0,1]X[0,1], and since you round down the real values, it should be denoted (0,0). So you should let K run from 0 to 2015, and instead of $I>0,\ J>0$ require that $0\leq I\leq 2014,\ 0\leq J\leq 2011$. -- Meni Rosenfeld (talk) 12:51, 14 November 2012 (UTC)

The part which confused me is that my values seemed to match your statement that "The solutions are $m\in \{0,671,1343,2014\}$". That is, I only get one tile on each of those columns, including the 2014 column. If I shift to allow tiles (0,0) and (0,1), and exclude tile (2015,2012), then I do get 4026 tiles, but, oddly, there are now two tiles in column 2014, at (2014,2011) and (2014,2012). StuRat (talk) 19:47, 14 November 2012 (UTC)

If (0,0) is the bottom-left square, then (0,1) shouldn't be in the solution set, so something is still off. I think you shifted by decreasing both X and Y by 1 (which gives you the same wrong offset), where what you should have done is decrease X by 1 and calculate Y based on the new X (meaning it decreases by 2012/2015). -- Meni Rosenfeld (talk) 22:03, 14 November 2012 (UTC)

(ec) Sturat and Meni beat me to it.

You were almost there...

X and Y are coprime, that means that the diagonal will only enter one square at a vertex, it will enter (Y - 1) squares via the bottom line, and (X - 1) squares via the left - so the answer is X + Y - 1, whether you are looking at 2x3, 3x5, or 2012x2015.

If X and Y are not coprime, subdivide the problem into n rectangles of size p times q, where p and q are coprime. So it'll be n (p + q - 1) which reduces to X + Y - n, n being the gdc of X and Y.

Cheers. - ¡Ouch! (^{hurt me} / _{more pain}) 06:59, 14 November 2012 (UTC)

Another way to express essentially the same reasoning (coprime case only): your diagonal has to cross X-1 vertical lines and Y-1 horizontal lines (excluding the borders of the grid). If X and Y are coprime the diagonal never passes through an interior vertex of the grid, that is it doesn't cross a vertical line and a horizontal line at the same time. Hence the diagonal intersects grid lines at X+Y-2 distinct points, and is thus divided in X+Y-1 distinct intervals. That is, it crosses exactly X+Y-1 unit squares of the grid. --FvdP (talk) 12:21, 16 November 2012 (UTC)