Walking Across a Chess Board.

I was thinking about the old Buffon's needle problem, and I came up with the following question:

Create a black and white chess board pattern on an 8 by 8 grid of square cells. From the set of all lines that pass through the grid, randomly select a line. Count the number of white cells that the line passes through. Repeat the process many times using more randomly selected lines. What is the average number of white cells that a line passes through? Make a guess and then determine the answer (by using either a Monte Carlo method, or by finding the exact answer).

Note: Ignore all lines that pass exactly through the intersection of two grid lines (consider the probability of this occurrence to be zero).

Carl G.

Thanks for pointing out the ambiguity of the definition of 'random line'. I considered giving a detailed description on how to select the lines, but it was late and I posted the message without one. Now that I have had some time to think about it, I agree that one would get a different answer depending on how they defined 'random line'. For the purposes of this problem, the random lines are obtained as follows:

1. Select a point from a uniform distribution of points that are in the interior of the 8 by 8 grid (e.g., pick two random numbers between 0 and 8, using a uniform distribution, and use them as the X and Y coordinates of the point). 2. Select an angle from a uniform distribution of angles from 0 to 180 degrees (or 0 to 360, I don't think it makes a difference). 3. The random line is the line that passes through the random point and forms the random angle with the horizontal.

Carl G.

OK, first some estimating.

My intuition isn't working overtime on this, but looking at any given point, the orthogonal-ish values will mostly be 4's, and the diagonals can be anywhere from 1 to 8. If we look just at diagonals running through the middles of each white square (as a surrogate for all reasonably diagonal lines starting from anywhere), the distribution looks a bit like: 1 white: 2 2 4 3 6 4 8 5 10 6 12 7 14 8 8 The weighted average of these diagonals is 5.12. If we have about half and half diagonals and orthogonals, then the true answer might be about midway between them, or about 9.1/2 = 4.5-4.6.

Now the Monte Carlo. I made some bogus simplifications in my program, so I'm not at all confident of the results, but I appear to be getting about 4.7-4.9, somewhat higher than my estimate.

Is calculus is the real way to approach this?

Say, here's a way to bring up the estimate a bit: if we look at the lines sweeping through diagonally, the ratio of those lines to the orthogonal ones is roughly sqrt(2):1, ignoring the fact that they're all uncountable anyway. That would shift the weighting to (5.12*sqrt(2) + 4) / (sqrt(2) + 1), or about 4.7

I tried attacking the integrals directly. If you think about it, you only need to handle the angles from -45° to +45° due to the fourfold symmetry of the problem. Furthermore, counting the white squares from -45° to 0° is the same as counting the black squares from 0° to 45°, so the problem is the can be solved by counting all squares from 0° to 45° and dividing by 2. Divide up the angles from 0° to 45° into 22 subdomains (atan(0),atan(1/8)),(atan(1/8),atan(1/7)),..., (atan(7/8),atan(1)) separated by the angles of the lines that can intersect more than one lattice point. For each angle in a given subdomain we can divide up the chessboard into areas of constant number of total squares intersected by at line of that slope. Then we add up area*number of squares intersected and integrate over all angles in the subdomain. Add up results for all subdomains and divide by the area of chessboard*90° and we have the average value. 'Value' below is my purported result; 'value1' is a check (should be 1/2.)

program buffon implicit none integer, parameter :: dp = selected_real_kind(15,300) real(dp) :: num(23) = (/0,1,1,1,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,5,6,7,1/) real(dp) :: den(23) = (/1,8,7,6,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,6,7,8,1/) real(dp) theta(23) integer n real(dp) phi real(dp) value real(dp) value1 integer i0, j0 real(dp) frac(0:8) logical top logical bottom real(dp) a1, a2, a3 real(dp) b1, b2, b3 integer nsq integer i, j

value = 0 value1 = 0 theta = atan(num/den) do n = 1, 22 top = .TRUE. bottom = .FALSE. a1 = 0 a2 = 0 a3 = 0 nsq = 0 phi = (theta(n)+theta(n+1))/2 i0 = 0 j0 = 0 do frac = i0-((/(j,j=0,8)/)-j0)*tan(phi) j = maxloc(modulo(frac, 1.0_dp), 1, frac > -1 .AND. frac < 8)-1 i = ceiling(i0-(j-j0)*tan(phi)) if(top) then b1 = i*j b2 = 0.5_dp*i**2 b3 = 0.5_dp*j**2 if(j0

Actually I think that Carl G. asked the question and Jim Gillogy was the first to provide an approximation to the solution.

But the answer to this form of the question is too easy: since each square presents a target 1/8 the size of the entire chessboard to a line coming in at a fixed angle, it will be struck at 1/8th the frequency that the entire chessboard is. Since there are 32 such small targets (the squares of a single color) the frequency with which they will be struck is (1/8)*32 = 4 times the frequency with which the big target (the entire chessboard) is struck. Thus the average number of squares of a given color intersected by any line of this random description is 4.

Your method looks quite elegant. Doing your integrals in Excel, I got their sum to be

3.375399182813160

After multiplying by 4/pi and adding 1/2, I got

4.797691718824460

So I suspect the problem lies in Mathcad rounding to single precision at some point.