

Title: HARD: Cigarettes Max Clique Post by william wu on Jul 22^{nd}, 2002, 3:30am i need a mathematical solution to the following problem: http://www.ocf.berkeley.edu/~wwu/riddles/cigarettes.shtml i know it exists, because i googled this riddle and found a calvin university extra credit math assignment. no answers online though. 

Title: Re: cigarettes Post by Garth Johnson on Jul 23^{rd}, 2002, 11:25pm Well three is obvious. I have a few different for four. I have one for five. Five: two side by side, one lying across the two bottom rotate 90 degress, one at either end nestled between the valley between the two on the bottom, resting on the one in the center meeting at a peak above the single middle cig. Do we have to assume that no cigarettes are bent or otherwise broken but still connected. This could drastically alter the possibilities. 

Title: Re: cigarettes Post by Bob Baddeley on Jul 23^{rd}, 2002, 11:53pm I think you're operating under a false assumption. Your diagram is nice, and works for other problems, but doesn't apply here. You can see that not every cigarette is touching every other cigarette (the red ones are not touching).http://www.engr.orst.edu/~baddeley/cig1.gif This is a problem. What I've come up with only has five cigarettes, but they all touch each other. Imagine holding a pair of chopsticks in each hand so that the ends in your hands touch. Now put the chopsticks on top of each other so each stick touches the two sticks on the other hand. Now grab a fifth stick with both of the pairs of chopsticks, and you have 5 sticks touching each other http://www.engr.orst.edu/~baddeley/cig2.gif The two reds touch, the two purples touch, the reds are resting on top of the purples, so those four all touch each other, and there is a fifth stuck through the middle touching all four. The problem is that two lines make a plane, and two planes intersect at a line. You have two cigarettes defining two planes, and one cigarette at the line intersecting those planes, which is what the following solution looks like. I don't see any other way.http://www.engr.orst.edu/~baddeley/cig3.gif I don't know how to get more than that in there, so my way probably isn't correct, but I think it's a step in the right direction. If you have any questions or find out another answer, my email address is baddeley@engr.orst.edu 

Title: Re: cigarettes Post by G. Toye on Jul 24^{th}, 2002, 1:56am I'm not convinced that there is a straight forward mathematical solution. The physical 3dimensionality of cigarettes are not well accounted for in the math theory you are proposing. Making assumptions about a problem's solution is the quickest way to get blocked from a potentially more logical solution. In this case, I would suggest that you reexamine your assumption that an extracredit problem in a math course necessitates a mathematical solution, as opposed to a logically deduced solution. I've found that math teachers love to throw in deductive logic problems in math course. It's often easier to first deduced the answer, then prove it mathematically. The other deadly assumption (not stated in the problem) is that only endpoints are touching. The post by Garth Johnson and Bob Badeley's first solution is likely on the right track. Like Bob, I also come up with 5 (2 configurations). I have a hard time visioning Bob's second solution, but I think we differ in our second solution. Solution 1 with reasoning explained: [I believe this is the same as the one offerred by Garth & Bob] A line and a point defines a plane. While it is possible to use 2 touching skew lines for which no plane contains both lines, I could not find any benefit in taking this approach for organizing the possible configurations. In any one plane, 2 cigarettes can simultenously touch all others (i.e. each other). They can be parallel or form a V. If they form a V, these two cigarettes define the plane. If the cigarettes are parallel, the number of possible simultaneous contact points are reduced. By configuring one plane stacked on top of the other, the two parallel planes can simultaneously touch at more than a single line. Doing so gives us 4, if arrange the cigarettes in each plane in a Vconfiguration, and 90 degrees apart in orientation between planes (i.e. in one plane, we have "<" and in the other plane we have "V"). So long as the angular rotation between the two planes is nonzero (i.e. exactly the same, one on top of the other) We can sneak in a 5th cigarette by placing the 5th cigarette perpendicular to two parallel planes and inbetween the V's. We do this by closing the angle of each V in each of the two planes so that the 5th cigarette touches all 4 cigarettes, we have 5. Solution 2: We have 2 cigarettes in a V configuration in the first plane. In a perpendicular plane we have a second pair of cigarettes also forming a V. Each V has 2 exposed legs, and a connecting vertex. We position this second V so that one exposed leg touches the exterior of the vertex of the first V, and the other exposed leg touches the interior of the same vertex. Now all 4 cigarettes are simultaneously touching. What this configuration reminds me of is... using one pair of tweasers to pickup another pair of tweasers on a table. It is now possible to stick another (5th) cigarette directly under the cigarettes in the first plane with the body of this 5th cigarette touching the vertex and its length aligned along the midline of the V, and its length bisected by the vertex of V in the first plane. The body of this last cigarette touches both exposed leg ends in the second V to form an enclosing triangle in the second plane (i.e. the inverted V in the second plane sits on top of the body of the 5th cigarette). 

Title: Re: cigarettes Post by G. Toye on Jul 24^{th}, 2002, 3:02am Ahh, yes  clarification. A line and a point define a plane. 2 lines in general do not define a plane, but 2 "intersecting" lines do define a plane. There is no such thing as 2 touching skew lines. By definition, 2 skew lines cannot interset. Two nonintersecting lines would violate the constraints of the problem. Thus, it would not be feasible to have any skew lines as part of the solution for this problem. So thinking in terms of container planes and interconnections across planes is a good idea. 

Title: Re: cigarettes Post by william wu on Jul 24^{th}, 2002, 3:12am Hi! Thanks for visiting the site! The reason I'm quite confident that there's a mathematical solution is because the Calvin University challenge sheet which I saw (but can no longer find) asked the students to repeat the riddle for different cylindrical objects, such as quarters and soup cans. And after that, it asked them to generalize. To derive a formula that takes as input the radius and height of the cylinders, and outputs the maximum number of such cylinders for which a clique can be formed. You can do better than 5. Here's 6: You can even get 7! I'll leave that as an exercise. I'd like to note that even if someone posts a configuration that gets you 8 cigarettes (7 is the most I can get), that's not really what i'm looking for if he or she can't prove the optimality of that configuration. I'm looking for a formula, a proof. Thanks! 

Title: Re: cigarettes Post by Hart Woolery on Jul 25^{th}, 2002, 12:46am I would have to argue the maximum number is six (or possibly seven). If you consider that the cigarettes are of three dimensional thickness, cylindrical, and presumably unbendable, this seems the only number possible for the following logical reason. Given any plane, you can only have a maximum of 3 cigarettes touching eachother (some kind of triangle MUST be formed, 4 cigarettes cannot touch eachother in the same plane). This cigarette "plane" can only fully contact one other plane of three cigarettes, giving you a total of 6 cigarettes. Now for the seventh cigarette, which is questionable, there is only one possible area left for it to go, perpendicular to the two intersecting planes inside of both triangles. The triangles would have to be small enough to inscribe a circle of the cigarettes diameter. Now doing this cigarettes would force them to overlap because of their length to diameter ratio. This makes it next to impossible to fully intersect your 2 planes, though I haven't proven it can't be done. I would like to see the configuration 7. :P Hart Woolery, University of California, San Diego 

Title: Re: HARD: Cigarettes Max Clique Post by Gamer555 on Jul 29^{th}, 2002, 8:31pm Wow! We got the big dudes out here ;) I agree, I don't think more than 6 is possible... 

Title: Re: HARD: Cigarettes Max Clique Post by ScottP on Jul 30^{th}, 2002, 1:13am If you want to see an image of how to arrange the seven, have a look at... http://www.puzzles.com/PuzzlePlayground/SixPencils/SixPencilsSol2.htm ...I guess the maths lies in finding the diameter to length ratios of objects for which this arrangement works. 

Title: Re: HARD: Cigarettes Max Clique Post by william wu on Jul 30^{th}, 2002, 4:00am SEEEE! I toooold you so. I wouldn't lie. ;D http://www.ocf.berkeley.edu/~wwu/images/riddles/seven_pencils_solution.gif I really hope someone proves it's optimal. I've had this problem stuck in my head for four months! Waah! :'( 

Title: Re: HARD: Cigarettes Max Clique Post by william wu on Jul 31^{st}, 2002, 10:49am I have located the Calvin University extra credit math assignment which references this problem. Check it out: http://www.ocf.berkeley.edu/~wwu/riddles/calvin_cigs.ps Note that the assignment references "stoutness" of cylindrical objects: R/L, where R is radius and L is height. A key consideration when proving the generalized solution. Also, I'll be updating http://www.ocf.berkeley.edu/~wwu/riddles/cigarettes.shtml periodically as more information comes in. 

Title: Somewhat off topic. Post by Nathan_Hellweg on Jul 31^{st}, 2002, 8:18pm If bending the cigs is allowed, the the size of the clique is at least the length/width of the cig because they can be bent into 'offset Ls' that will always form a clique. 

Title: Re: HARD: Cigarettes Max Clique Post by Misha Kruk on Jul 31^{st}, 2002, 10:12pm All right, the assignment said that it's ok to ask aunt Gladys for help, so I talked to my father about this :) He suggested the following approach for analytical proof: cylinder is defined by 5 numbers (3 coordinates and 2 for direction of axis). Two cylinders touch if the distance between their axis is less than 2r (that's one equation). Forget about l, let them be infinite. For n cylinders we have 5n random variables. Since each cylinder must touch each other we have n(n1)/2 equations. We will have a solution when n(n1)/2 <= 5n n <= 11 So we definitely can't go above 11 cigaretts here. I know it's not a real solution, but this might be step in the right direction. Hopefully someone who's smarter than me can pick up from here? 

Title: Re: HARD: Cigarettes Max Clique Post by william wu on Aug 1^{st}, 2002, 3:06am James Fingas has sent me a long analysis of the problem. Also, I found some possible leads through mathworld.wolfram.com. Too much info to paste here. Please check out the following page: http://www.ocf.berkeley.edu/~wwu/riddles/cigarettes.shtml#2002_08_01 

Title: Re: HARD: Cigarettes Max Clique Post by Misha Kruk on Aug 1^{st}, 2002, 5:59am ok, here are some tweaks to my previous post: cyliner (actually infinite cylinder, we are still simplifying) is actually defined by 4 numbers: plane through the beginning of coordinates and location on this plane. Also the position of the first cylinder is completely irrelevant (think of it a defining beginning of coordinates), so we have 4(n1) instead of 5n Also every solution can be rotated around the first cyliner in any way, so this takes away one more degree of freedom. This gives us: n(n1)/2 <= 4(n1)1 n^2  9n + 10 <= 0 Don't have time to solve this, late to work, but 8 doesn't satifsy it and 7 does. What do you think? 

Title: Re: HARD: Cigarettes Max Clique Post by Alex on Aug 1^{st}, 2002, 11:11am I sux @ math so I can't offer much in the way of the theory... but just thought I'd contribute my 2 cents in helping with the formula that Misha didn't have time to finish: if nČ  9n + 10 <= 0 then n <= 7.701562118716424 So yes, 7 is the max if the formula is sound. 

Title: Re: HARD: Cigarettes Max Clique Post by Alex F on Aug 1^{st}, 2002, 4:23pm In Martin Gardner's book "My Best Mathematical and Logic Puzzles", he gives an in depth explanation of when 7 cigarettes can be arranged correctly. He claims that the lengthtodiameter ratio must be greater than (7/2)*3^.5. http://www.amazon.com/exec/obidos/ASIN/0486281523/qid%3D1028244105/sr%3D111/ref%3Dsr_11_1/00231001589852021 

Title: Re: HARD: Cigarettes Max Clique Post by Rhaokarr on Aug 2^{nd}, 2002, 9:11pm I tried asking a few people down the pub about this, using matchsticks instead of cigarettes (as there weren't enough to go around). After saying that using the bulbous matchheads wasn't in the spirit of the problem, three of the four people got a solution for 6 (all variations of the fanofthree on another fanofthree). It was mildly embarrassing that each of the 6 solutions came up within three or four minutes of 'fiddling'... 

Title: Re: HARD: Cigarettes Max Clique Post by william wu on Aug 3^{rd}, 2002, 11:53pm OK there's some heavy analyses going on, so it's going to take me a while to process this information skeptically, particularly Fingas's email. I'll get back to you guys later, perhaps after my stupid GRE. Others are welcome to help me comb through the logic though. I appreciate all the effort that's going into this. In the meantime, I'll be memorizing obfuscated words :P 

Title: Re: HARD: Cigarettes Max Clique Post by James Fingas on Aug 29^{th}, 2002, 7:52am Here is the essence of the (way too) long email I sent to William: Method: Analyze the problem from a degreesof freedom standpoint. Madness: I come up with these limits for the problems: For infinite cigarettes (no ends), you can get at most 7 cigarettes touching, and we know of a solution for 5 cigarettes For longish cigarettes (but with ends), you can get at most 9 cigarettes touching, and we know of a solution for 7 For short canofcorn cigarettes, I'm pretty sure you can only get four touching. They're more like marbles than like cigarettes. The analysis looks at the number of actual degrees of freedom that you have as you place each cigarette. Some of these degrees of freedom are trivial: they don't change anything about the answer, except for rotating it, or moving it around. For infinite cigarettes, you have 4 in placing each cigarette. Some of these will be trivial, some will be used to satisfy constraints, and some will be real degrees of freedom. I won't go into a long explanation here, but you can verify the following yourself. 1) Cigarette 1 has no real degrees of freedom (all are trivial) 2) Cigarette 2 has 2 degrees of freedom (2 are trivial), and one constraint, for 1 degree of real freedom. 3) Cigarette 3 has 4 degrees of freedom, and two constraints, for 2 real degrees of freedom 4) Cigarette 4 has three constraints > 1 degree of freedom 5) Cigarette 5 has four constraints > no degrees of freedom 6) You may be able to place cigarette 6 if you use your degrees of freedom wisely in steps 24. This uses up one of those extra degrees of freedom. 7) You may also be able to place cigarette 7. This uses up two extra degrees of freedom. 8) You probably can't place cigarette 8, because you need 3 DOF and you only have 1. The same analysis can be extended to the finitelength cigarette. 5 variables specify each cigarette's position. 1) Cigarette 1: no DOF 2) Cigarette 2: 1 trivial, 1 constraint: +3 3) Cigarette 3: 0 trivial, 2 constraints: +3 4) Cigarette 4: 0 trivial, 3 constraints: +2 5) Cigarette 5: 0 trivial, 4 constraints: +1 6) Cigarette 6: 0 trivial, 5 constraints: +0 7) Cigarette 7: 0 trivial, 6 constraints: 1 8) Cigarette 8: 0 trivial, 7 constraints: 2 9) Cigarette 9: 0 trivial, 8 constraints: 3 10) Cigarette 10: no can do (probably) For really short cigarettes (only as long as their diameter) I don't see how you could arrange them any differently than marbles, so we'll say that the maximum is 4, and we know how to arrange those 4. 

Title: Re: HARD: Cigarettes Max Clique Post by Jon on Nov 11^{th}, 2002, 8:40pm What we're not taking into account is, do the cigs have to be the same length? If not, then more is possible. We can take them to be, at least, marbles, but the size variation helps. I think we should give a bound on the diametertolength ratio, like 1:5, for example. 

Title: Re: HARD: Cigarettes Max Clique Post by SWF on Nov 27^{th}, 2002, 5:53pm Here is a way for 8 cylinders (not all the same length). The axes of the red ones lie in the same plane, and the blue ones lie on top of them. 

Title: Re: HARD: Cigarettes Max Clique Post by paul on Apr 3^{rd}, 2003, 8:41pm i can get 12 put three together like so \  / \/ then put a identical set directly on top of it then put another set of six rotated 180 degrees end to end on the open part 

Title: Re: HARD: Cigarettes Max Clique Post by redPEPPER on Apr 4^{th}, 2003, 1:28pm Something like this, on two levels? /\ /  \ \  / \/ Even with only one level, a lot of them are not in contact with all the others. The red one has no contact with the blue ones for example. And with two levels it's even worse: the blue ones are not in contact with each other if one of them is on top and the other one at the bottom. 

Title: Re: HARD: Cigarettes Max Clique Post by dennis cope on Oct 21^{st}, 2003, 2:45am This problem was answered in one of Martin Gardners math books. The answer, if my memory serves correct, is seven. They are placed in a pyramid type fashion. I am currently stationed in Rota, Sp. I left my copy back in the US.The name of the bok is something to the effect of Mathmatical Magic, Puzzles, and games. 

Title: Re: HARD: Cigarettes Max Clique Post by Nigel_Parsons on Jun 17^{th}, 2004, 11:19am 'Mathematical Puzzles and Diversions' by Martin Gardner has it as 'The Touching Cigarettes'. with the answer given away by being illustrated on the cover (U.K. edition at least) UK edition is Penguin books ISBN 014 02 0713 9 

Title: Re: HARD: Cigarettes Max Clique Post by towr on Jun 18^{th}, 2004, 12:25am Is there any proof in it that that's the definite answer? Cause I thought 'the' answer was unknown (unproven).. 

Title: Re: HARD: Cigarettes Max Clique Post by Barukh on Jun 18^{th}, 2004, 3:53am on 06/18/04 at 00:25:20, towr wrote:
At least in the first edition of the book (some 30 years ago), it was not proven. Moreover, it was a kind of surprise for the author that 7 is possible. 

Title: Re: HARD: Cigarettes Max Clique Post by Jayaram on Aug 9^{th}, 2004, 4:27am Sorry for playing the fool  but isn't the question about infinite length cigarettes irrelevant? By definition, PARALLEL LINES ARE DEFINED AS LINES THAT MEET AT INFINITY. So, can't we just assume that infinite length cigarettes all meet at infinity (I know that the argument is ambiguous, but isn't that the very definition for parallel lines? 

Title: Re: HARD: Cigarettes Max Clique Post by Jack Huizenga on Aug 9^{th}, 2004, 9:43pm Parallel lines don't "by definition" meet at "infinity". It all depends on what type of geometry you are using. In standard Euclidean geometry, which is the geometry that nearly every "real life" question is worded in, parallel lines by definition never meet. Also, in Euclidean geometry there is no notion of infinity. I believe you are confusing projective geometry with Euclidean geometry. On another note, keep in mind that we are working in three dimensions. When working in three dimensions, one can't conclude that two arbitrary lines either intersect or are parallel like one can in two dimensions. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 