How many squares does a line between two points pass through? Suppose I have a square, let's say the sides have length 1. I will then partition the square into $N^2$ sub-squares, where $N \in \mathbb{N}$ and the sub-squares are all the same size. Now, suppose we place two points $A$ and $B$ randomly within the large square a distance of $D$ apart from each other, and then draw the line segment $AB$. The question is, what is the expected number of small squares that $AB$ will pass through?
I have no idea how to solve this analytically, and was thinking of attempting to get a sense using simulation, but was curious what I could learn about it here. (This isn't a homework question; it's related to a problem I'm working on in economics research.)
 A: Suppose that you divide your square into $N^2$ sub-squares, where $N\in\mathbb{N}$. Then suppose that $A=(x_{1},y_{1})$ and $B=(x_{2},y_{2})$ where $x_{1},x_{2},y_{1}$ and $y_{2}$ are real numbers in $[0,1]$. Then the segment $AB$ must pass through at least $N|y_{2}-y_{1}|$ squares in the $y$ (or vertical) direction and at least $N|x_{2}-x_{1}|$ squares in the $x$ (or horizontal) direction. So, we would expect the segment $AB$ to pass through $N|x_{2}-x_{1}|+ N|y_{2}-y_{1}|$ squares.
A: I broadly agree with @Byron Schmuland's answer, which seems correct, but I have some additional suggestions.
I am assuming that the size of a small square is 1, for simplicity, compared to a distance of D.
If the question is to place A and B "randomly" with a given distance of D apart, this may fall foul of Bertrand's paradox: that this concept of randomness is not clearly enough defined.
However, it seems to make sense to place A first, suggesting we should place B on an arc with centre A and radius D. The arc will be restricted depending on how close it is to the edge of the square.
Let's imagine that we choose the point A, and then the angle $\theta$ is chosen randomly.
Each direction $\theta$ is equally likely (by assumption here and by symmetry of the square).
Then the number of squares passed through will be $D|\sin(\theta)|+D|\cos(\theta)|+1$ from Byron's work and using a right-angled triangle.
$$E[D|\sin(\theta)|+D|\cos(\theta)|+1]$$
$$= D \cdot E[|\sin(\theta)|+|\cos(\theta)|] + 1$$
$$= 4D/\pi + 1$$
Or, considering $(1/N)$ to be the length of a little square (according to the question as given)
$$= 4ND/\pi + 1$$
In the case where $N = 2$ ($2$ little squares per side) and $D = 0.5$ ($D$ is half the length of a long side), we expect to pass through $2.27$ squares. Seems right. Sometimes it will pass through only $1$, but more often $3$.
This will break down badly when D gets long compared to the side of the big square, I imagine ($D>1$?), when the line no longer has the option of being horizontal or vertical. 
A: Imagine the subdivided square as an $N\times N$ chessboard of subsquares. 
Every point on the board belongs to one subsquare with coordinates $(r,c)$, where $r$ (the row index)
ranges from $1$ to $N$ and similarly for the $c$ (the column index).
Now the number of subsquares that the line segment $\overline{AB}$ between two uniformly selected points $A$ and $B$ touches equals $d(A,B)=|A(r)-B(r)|+|A(c)-B(c)|+1$. 
Here $A(r)$ means row index for $A$, and similarly for the other notation.  The points $A$ and $B$ are in "general position" because of the randomness, 
so the segment always passes through the maximum number of subsquares. The segment doesn't hit any corners. 
Since the random variables $A(r),B(r),A(c),B(c)$ are independent and uniformly 
distributed on $\{1,\dots, N\}$, it is not hard to calculate that the expected number is 
$$\mathbb{E}(d(A,B))=1+{2(N^2-1)\over3N}.$$      
