Dots On A Line

Alright, I think I've finally run out of puzzles if I'm going to post this one. It is a rather crazy one that I solved with Matt many years ago and I absolutely love the answer to it. Sadly there isn't really a clean way to solve the puzzle, you have to do it the hard way, and its really not very illustrative of why the final answer is what it is, but thats just life. I initially found this puzzle at cut the knot:
Consider the unit interval between 0 and 1. Select N points randomly on that interval (random with uniform distribution). From each selected point "color in" the part of the interval between it and the closest neighboring point. In the limit as N goes to infinity, what fraction of the interval is colored in on average?

Terrible, I know. To clarify, suppose we had N=5 and selected the points 1/10, 2/10, 4/10, 7/10 and 8/10. Then from 1/10 we would color to 2/10, from 2/10 we would color back to 1/10 (not that that does anything), from 4/10 we color back to 2/10, from 7/10 we color to 8/10 and from 8/10 we color back to 7/10 (again does nothing). Then the colored region would be [1/10,4/10] ∪ [7/10,8/10] so in total 4/10 of the interval was colored in, in this case.

4 comments:

JonBen said...

Are 0 and 1 points for purposes of determining nearest point? Your example sort of addresses the answer to this, but not entirely.

My understanding is that they are not points, so 0 and 1 will always belong to uncoloured sets. Is this correct?

Kory Stevens said...

Yeah, in the way that it is worded 0 and 1 are not to be considered as selected points, and as such always belong to uncolored sets.

You can consider them to be selected points if you like however, because in the limit as N goes to infinity it will always be a very small distance to the next point anyway, so the N->infinity answer comes out the same.

JonBen said...

Right, that makes sense. Having applied almost no thought to problem I want the answer to be one half (except it seems that it should somehow be less than that).

This is the type of problem that I would much rather just code to find the solution. Sure I'll have no deep insight or beautiful moment of realization... but I probably wouldn't have gotten to that point if I tried the analytic approach anyway. At least with a code I'll probably have the right answer :)

I'll let you know how it goes tomorrow at boardgames. Also, I bought a new game this week. It's about mining the moon of Pluto... fun times!

JonBen said...

Ouch my face! What kind of answer is that? I'll need a magic ball to work that back into a rational fraction...