The Lumber Room

"Consign them to dust and damp by way of preserving them"

Archive for November 7th, 2008

Lattice points visible from the origin

with 16 comments

[A test of LaTeX-to-Wordpress conversion. Bugs remain, point them out. Original PDF]

Here is a problem I love. It is simple to state, and it has a solution that is not trivial, but is easy to understand. The solution also goes through some beautiful parts, so I can promise it’s worth reading :-)

[The solution is not mine. Also, the question is just an excuse for the ideas in the solution. :P]

Question. Suppose you are standing on an infinite grid in the plane. You can see infinitely in all directions, but you cannot see through grid points: a point is hidden from view if some other grid point lies in your line of sight. What fraction of the grid points can you see?

Let us first imagine that we are standing at the origin, and that the grid is that of the lattice (integer) points.

The blue points are visible; the grey points are not

The blue points are visible; the grey points are not


Read the rest of this entry »

Written by S

Fri, 2008-11-07 at 15:00:30

Posted in public

Tagged with , ,