wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> HARD: Cigarettes Max Clique
        
(Message started by: william wu on Jul 22^nd, 2002, 3:30am)

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 3-dimensionality 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 re-examine your assumption that an extra-credit 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 V-configuration, 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 non-zero (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 in-between 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 non-intersecting 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 inter-connections 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:

http://www.ocf.berkeley.edu/~wwu/images/riddles/six_cigarettes_solution.gif

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/six_pencils_solution.gif

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(n-1)/2 equations. We will have a solution when

n(n-1)/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(n-1) 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(n-1)/2 <= 4(n-1)-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 length-to-diameter ratio must be greater than (7/2)*3^.5.

http://www.amazon.com/exec/obidos/ASIN/0486281523/qid%3D1028244105/sr%3D11-1/ref%3Dsr_11_1/002-3100158-9852021

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 fan-of-three on another fan-of-three).

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 e-mail. 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 degrees-of 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 long-ish cigarettes (but with ends), you can get at most 9 cigarettes touching, and we know of a solution for 7

For short can-of-corn 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 2-4. 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 finite-length 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 diameter-to-length 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.

http://pages.prodigy.net/scottfr/Images/Cig.JPG

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:

Is there any proof in it that that's the definite answer?
Cause I thought 'the' answer was unknown (unproven)..

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.