MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf), found here:

"We have a rectangular carpet and an indefinite supply of perfect pennies. What is the probability that if we drop the pennies on the carpet at random no two of them will overlap? This problem is one of the most important problems in statistical mechanics. If we could answer it we would know, for example, why water boils at 100C, on the basis of purely atomic computations. Nothing is known about this problem.”

I was wondering if this problem goes by a more popular name and whether or not some form of progress has been made on it. In particular, references would be highly appreciated!

share|cite|improve this question
The authors phrased this badly: 'indefinite supply' is misleading. What they mean is 'n perfect pennies'. – TonyK Sep 1 '10 at 23:22
Perhaps "indefinite supply" stands for "unknown number". – sleepless in beantown Sep 2 '10 at 5:48
The model as described above is somewhat related to what's known as "random sequential adsorption", see e.g. the references in my answer here In RSA one discards pennies that overlap and then keeps adding more until it is impossible. In the hard disks model as described by Matthew Kahle below, one is studying the properties of a uniformly random configuration of nonoverlapping disks. – j.c. yesterday
up vote 9 down vote accepted

This is the two-dimensional hard spheres model, sometimes called hard discs in a box.

See Section 4 of Persi Diaconis's recent survey article, The Markov Chain Monte Carlo Revolution. The point here is that even though it very hard to sample a random configuration of nonoverlapping discs by dropping them on the carpet (because the probability of success is far too small for any reasonable number of discs), but it is nevertheless possible to sample a random configuration via Monte Carlo.

share|cite|improve this answer

One variation that was solved by Baxter is the hard hexagon model, a discrete version where the pennies are hexagons and they are constrained to have their centers on the vertices of a triangular lattice. This example is rather famous because the solution involves the Rogers-Ramanujan identities. See Baxter's book for more details. As far as I know, the analogous "hard square model" has not been solved.

share|cite|improve this answer

Rota (on page $viii$ of his introduction, page 10 of the pdf file) is talking about the difficulty of having an analytic solution for statistical mechanics in the 2-dimensional and 3-dimensional cases, while it is possible to attack the problem somewhat in the one-dimensional case.

He also mentions how stochastic methods and simulation can be used to come up with a quick-and-dirty approximation of the answers by modeling the physical sysyem and using Monte Carlo methods: iterating the system with random steps.

Topics to research would be Monte Carlo methods, stochastic models, random walks, etc. Can you say a little more about exactly what it is that you wish to study or examine?

share|cite|improve this answer

I suppose one could phrase the question this way: given $r$, $s$, $n$, and $\epsilon$, what is the probability that of $n$ points, selected uniformly and independently at random from a rectangle of dimensions $r$ by $s$, no two will be within $\epsilon$ of each other.

In the theory of uniform distribution modulo one, there is a concept of discrepancy which can be brought to bear on this problem. I hope that gives you a few keywords to look for.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.