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 cigarettelike objects on desks (pens, pencils, markers ... we don't smoke), has 7 cigarettes. However, neither of us can prove that it's optimal.
7/30/2002 7:18AM UPDATE: I have crossed out the following arguments because I'm getting emails from many confused people. The graphs below are supposed are graph theory representations of the problem, not the actual configurations  a vertex represents a cigarette, and an edge represents an adjacency between two cigarettes. Anyways, it's probably all wrong so just forget it. However, you're welcome to read it through the strikeouts if you want.

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 reallife, 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 upperbound:
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 realworld 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 straightedges, 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 diamondlike 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 6clique, I would float a sixth vertex inside the 5clique 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 5clique, all inside the surface of the polyhedron):
To get the 7clique, I would just float a seventh vertex inside the 6clique polyhedron, and connect the seventh vertex to all other vertices. Then I was hoping that if you inserted an eighth vertex inside the 7clique 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 8clique on paper, so there's a flaw somewhere  not all polyhedra in my analysis can map to a realworld 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
