Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources

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.

The full text of this article is premium content


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.


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

Displaying all 2 comments

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account