How many cigarettes can you arrange so that every cigarette touches every other?
(You can't bend the cigarettes.)

Riddle forum thread: Click here

ucb.class.cs170 newsgroup post 4129, 4/27/2002 9:24AM: cigarette riddle and 3D cliques

I've been stuck on a very interesting riddle. I'm posting it here because I really think we can use cs170/270 principles to solve it, but I'm not sure how; perhaps someone could help me out.

The riddle is very simple:

What is the maximum number of cigarettes you can place on a table such that every cigarette touches every other cigarette? (You can't bend the cigarettes.)

Note that you can't just do a star configuration, like an asterisk. Remember that a cigarette has a finite thickness, and thus can't be treated as a line of infinitesimally small width. Thus, in an asterisk configuration of six cigarettes, there will be a hexagonal hole in the middle, and any one cigarette would only touch the cigarettes adjacent to it, and not the ones across from it. Also, you can't just do a loop of cigarettes, because then each cigarette would only be touching the cigarettes directly to the right and left of it -- the riddle wants every cigarette to touch each other directly, not just be somehow indirectly connected to every other cigarette.

Some example valid configurations: for 3 cigs, arrange an equilateral triangle. For 4 cigs, put a cig on top of the equilateral triangle so that it touches the corner of one triangle, and the midpoint of the cig opposite to that corner.

I got the problem from a friend, Hansen Bow, who said he read it in some random book a long time ago. The supposed solution, which we also arrived at by merely playing with with cigarette-like objects on desks (pens, pencils, markers ... we don't smoke), has 7 cigarettes. However, neither of us can prove that it's optimal.

But perhaps we can use graph theory to prove/disprove that 7 is optimal? My idea is to represent every cigarette with a vertex, and every direct connection between two cigarettes with an edge. Then any valid configuration of cigarettes would actually be a big clique -- a set of vertices such that every vertex has an edge connecting it to every other vertex! However, this graph representation of the cigarette problem is not exactly correct. There are some restrictions we must consider. For instance, we can't let an infinite number of edges connect to a vertex, because in real-life, cigarettes have a finite surface area dictated by their length and radius, and therefore only a finite number of cigarettes can directly touch a cigarette. Let us denote the radius by R and the length by L. Then we can restrict the degree of a vertex to the following upper-bound:

4(L/(2R)) + 8 = 2L/R + 8

(To get this formula, I noticed that for a given 2R slice of a cigarette C, I could only put four cigs around that slice, perpendicular to the long side of C's surface. Then there are L/(2R) slices along the long side. Then I could bundle a group of four cigs so that all of their ends touch one of C's ends, and then do the same for the other side.)

The graph representation of this riddle is still incomplete at this point: it's fnot true that for every graph G, there exists a realizable real-world cig configuration that maps to G. First of all, our graphs must be 3 dimensional. It's around here that I get stuck. My hypothesis is that any valid graph representation must be planar, and only use straight-edges, since we can't bend the cigarettes. (Are more restrictions necessary???) If these are all the necessary restrictions, then if you translate the valid configuration for 4 cigs into a 3D planar graph with only straight edges, you get a tetrahedron -- a 3D clique of size 4:

... translate to 3D:

Similarly, the graph representation for 5 cigs gives you a diamond-like polyhedron (concatenate two tetrahedrons on one face, and then draw an edge connecting the vertices farthest apart from each other -- this last edge is denoted by the dotted line in the image below):

To get the 6-clique, I would float a sixth vertex inside the 5-clique polyhedron above, and connect that sixth vertex to all other vertices from the inside, resulting in the structure below (red lines are edges added to the 5-clique, all inside the surface of the polyhedron):

To get the 7-clique, I would just float a seventh vertex inside the 6-clique polyhedron, and connect the seventh vertex to all other vertices. Then I was hoping that if you inserted an eighth vertex inside the 7-clique polyhedron, and then tried to connect the eighth vertex to all other vertices, it would be impossible to maintain planarity, thereby proving that the optimal solution is 7. However, I think I was actually able to draw an 8-clique on paper, so there's a flaw somewhere -- not all polyhedra in my analysis can map to a real-world cigarette configuration.

It is also unclear to me whether gravity is a relevant factor. The solution for 7 cigarettes will actually stand up on a planet with gravity. But perhaps more cigarettes could be somehow added in gravity's absence?

Lastly, I'm intrigued by what happens when we tweak the riddle slightly, and replace the cigarettes with quarters, or soup cans. All three of these objects share the property of being right cylinders, just with different radii and heights. How can we generalize this problem? Given right cylindrical widgets all of radius R and height H, how many can we arrange so every widget touches every other widget? And is there already some beautiful CS/topology theorem that describes all this?

Help?

- William Wu
wwu@cory.eecs.berkeley.edu

6/20/2002 2:57AM: cigarette riddle update

no newsgroup replies from the cs170 staff. dr. rao also didn't know. however, john leen told me that there's a math theorem which says you can construct a 3D clique of any size you like. so this rules out my idea that the optimal solution would occur when i cannot construct a larger 3D clique. maybe this is more of a geometry problem?

- William Wu
wwu@ocf.berkeley.edu

7/30/2002 7:27AM: cigarette riddle update, post-slashdot

Well, four months have passed and this nasty riddle is still stuck in my head, awaiting a proof.

To all the disbelievers, here are configurations for six and seven cigarettes:

Again, this does not constitute a solution. We need a proof that this is the optimal solution. Also, I want to generalize the problem for cylindrical objects of radius r and height h.

From James Fingas via e-mail: "One simplified way to state the problem mathematically is to ask 'how many lines can be created in 3-space such that the minimum distance from each line to every other line is exactly a'. Of course this is for infinitely long cigarettes... Now how much would those cost?"

Click here to check out the riddle forum thread for this problem.

- William Wu
wwu@ocf.berkeley.edu

7/31/2002 11:54AM: cigarette riddle update, post-slashdot

I have located the Calvin University extra credit math assignment which references this problem. Click here to check it out. Note that the assignment references "stoutness" of cylindrical objects: R/L, where R is radius and L is height. This is a key consideration when proving the generalized solution.

- William Wu
wwu@ocf.berkeley.edu

8/1/2002 3:31AM: cigarette riddle update, post-slashdot

I was browsing mathworld.wolfram today and did a search for cylinders, and whaddaya know, they've got the seven cigarettes solution configuration! Click here to check it out (more about cylinders than you ever wanted to know).

"It is possible to arrange seven finite cylinders so that each is tangent to the other six, as illustrated above."

No optimality proof provided.

Still helpful though. "Finite" cylinders. This implies that the infinite length model suggested in the bulletin board and in earlier e-mails may not be a good idea, even if we impose restrictions that ignore the weird intersections created from antiparallel lines far out in space. Also, note that mathworld.wolfram.com says "tangent to the other six". Not just adjacent ... tangent. Meaning mathworld is not considering configurations where one cigarette touches the small circular face of another cigarette.

From: James Fingas
To: William Wu, Brandon Schwartz

I have been thinking about the problem, and the simplification of infinitely long cigarettes is not completely applicable. It is at best a vaguely related problem which has an easier-to-find answer. However, it may offer some insight to the problem.

The solution to the infinite-cigarette problem seems to me to be somewhere between five and seven (inclusive) cigarettes. I have come to this conclusion by looking at it from a degrees-of-freedom standpoint:

However, the best solutions to the finite cigarette problem use the ends of the cigarettes extensively, indicating that finite and infinite cigarettes don't have the same solutions. Furthermore, for short cigarettes, you likely can't do any better than four (think of the similar marble problem).

Somewhere in between the infinitely-long cigarettes that don't have any ends and the really short marble-like cigarettes are the real-length cigarettes. However, it is not obvious to me how we can bridge the gap between these extremes.

As for representing the cigarettes as rays (only one finite end), we could do this, but as soon as you put an end on the cigarettes, the geometry gets difficult. I'll try my degrees-of-freedom approach again for one-ended cigarettes (at least you can light these ones ... but not inhale. Maybe these are what politicians use when they are teenagers):

These same calculations apply to double-ended cigarettes, so maybe this is an upper bound to the solutions. However, it may also be that for very special arrangements, you can have more cigarettes than that.

This summarizes my estimations on the problem. The minimum bounds are definite, while the maximum bounds are less so.

- James Fingas

- William Wu
wwu@ocf.berkeley.edu