Buffon’s Needle and the Perimeter of Planar Sets of Constant Width

Here is an answer to “Test your intuition (8)”. (Essentially the answer posed by David Eppstein.)

BuffonNeedle_700

(From Wolfram Mathworld)

Buffon’s needle problem asks to find the probability that a needle of length \ell will land on a line, given a floor with equally spaced parallel lines at distance one apart. The problem was posed by Georges-Louis Leclerc, Comte de Buffon (1707 – 1788).

There is a familiar computation showing that when \ell \le 1 the probability is 2\ell/\pi. A computation-free proof can be found in these pages on geometric probability written mostly by Molly McGinty. (They were pointed to me by Sergiu Hart.)

Briefly the computation-free argument goes as follows:

1) Consider the expected number of crossings of a needle with the lines rather than the probability of crossing.

2) Allow also polygonal needles.

3) Show, based on linearity of expectation, that for a polygonal needle the expected number of crossings is a linear function c\ell of the length \ell of the needle.

4) Consider now a circular needle of radius 1/2. Note that with probability one it has two crossings with the lines. Deduce that c=2/\pi.

This gives a proof for Buffon’s needle problem. But now consider any closed planar curve with constant width one. Again with probability one it will have two crossings with the parallel lines. Therefore, it has the same perimeter as the circle.

Update: The argument above Continue reading

Test Your Intuition (7)

Consider the following game: you have a box that contains one white ball and one black ball. You choose a ball at random and then return it to the box. If you chose a white ball then a white ball is added to the box, and if you chose a black ball then a black ball is added to the box. Played over time, what is the probability that more than 80 percents of the chosen balls are white?

Continue reading

Test Your Intuition (6)

This is not as clear cut a question as the earlier ones, and if you do not know an answer then it will be difficult to figure one out just based on intuition. (But perhaps possible).

If you are intrigued by the question and would like to explore what an answer could be, I would be interested to know how you tried to find an answer.  Asked a colleague? Looked at a book (which?)? Looked online (where?)? 

Here is the question:

A differentiable complex function automatically has derivatives of every order. (In contrast to differentiable real functions that need not have even second derivatives at any point.) 

Can you describe this “miracle” as part of a more general phenomenon?

Answer To Test Your Intuition (4)

Let G be a graph and u and v two vertices.

(1) Let H be a random graph where every edge of G is chosen with probability ½. Let p be the probability that there is a path between u and v in H.

(2) Let T be a random orientation of the graph G. Namely, every edge {x,y} is directed from x to y with probability ½ and otherwise it is directed from from y to x. Let q be the probability that there is a directed path from u to v in T.

What is the relation between p and q?

Answer: p=q

This is an old theorem of Colin McDiarmid: Continue reading

Answer to Test Your Intuition (3)

Question: Let X=[0,1]^d be the d-dimensional cube. Turn X into a torus T^d by identifying opposite facets. What is the minumum (d-1)-dimensional volume f(d) of a subset Y of X which intersects every non-trivial cycle in T^d.

Answer: Taking Y to be all points in the solid cube with one coordinate having value 1/2, gives you a set Y that seperates all cycles and has (d-1)-dimensional volume equals d. It is not difficult to prove that f(d) \ge C\sqrt d. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of Y which seperates all cycles with vol(Y) =O(\sqrt d). A simpler argument was found by Noga Alon and Boaz Klartag.  For an even simpler treatement of this result along with several discrete analogs see this paper by Noga.

Test Your Intuition (2)

Question: Let Q_n=[-\frac 12,\frac 12]^n\subseteq {\bf R}^n be the cube in {\bf R}^n centered at the origin and having n-dimensional volume equal to one.  What is the maximum (n-1)-dimensional volume M(d) of (H\cap Q_n) when H \subseteq {\bf R}^n is a hyperplane?

Can you guess the behavior of M(n) when n \to \infty? Can you guess the plane which maximizes the area of intersection for n=3?

Test your intuition before reading the rest of the entry.

Continue reading