Communications of the ACM

It's amazing how little we know about good old plane geometry. Last month (August 2010, p. 128) we posted a trio of brainteasers, including one as yet unsolved, concerning figures on a plane. Here, we offer solutions to two of them.

P Albert

The solution to the first problem was quite elegant, but I got stuck trying to parse "can be reduced only through stacking" (I think "can be only reduced through stacking", i.e., stacking can only reduce the area, not increase the area, was intended). Nonetheless, the proof works.

I am not convinced that that is the case for the second puzzle. You have not actually shown that it is impossible to place 10 points such that one hexagonal pattern cannot simultaneously cover all 10 points.

Because you do not permit overlap, the coins cannot be independently randomly placed. Furthermore, in order to get to the 91% coverage, the first coin can be randomly placed, but then the only remaining degree of freedom - if the hexagonal pattern is to be obtained - is the rotation of the pattern and that is fixed once the second coin is placed.

Because the disks are all not randomly placed, only the hexagonal pattern is randomly placed, the 90.69% value is the probability that one randomly selected point is covered by one randomly selected hexagonal pattern. So, at best, you have proven that when ten hexagonal patterns are selected, one for each point, there must be some instances where every point was covered by its hexagonal pattern, not that there are some instances where all ten points are covered by one pattern.

However, you haven't even proven that. Granted, if a given set of 10-bit words averaged more than 90% 1's, the set must have included at least one 10-bit word that is all 1's. However, it is not a certainty that if bits are randomly selected with p(1)=0.9069 and p(0)=1-p(1) that the the average number of 1's must be greater than 90%. Likely, with a large enough set, but never a certainty.

Anonymous

These probabilistic arguments are tricky if you are not used to them.
In the analogy with 10-bit words, if you pick 10 random (independent or dependent) bits with p(1)=0.9069 then the EXPECTED (or "average") number of ones is equal to 10*p(1), which exceeds 90%. (This is a consequence of "Linearity of Expectation.")
-- G. Rote