wu :: forums « wu :: forums - HARD: Cigarettes Max Clique » Welcome, Guest. Please Login or Register. Feb 20th, 2024, 2:35pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, ThudnBlunder, SMQ, Icarus, william wu, Grimbal, towr)    HARD: Cigarettes Max Clique « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: HARD: Cigarettes Max Clique  (Read 42441 times)
william wu

Gender:
Posts: 1291
 HARD: Cigarettes Max Clique   « on: Jul 22nd, 2002, 3:30am » Quote Modify

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.

 « Last Edit: Jul 26th, 2002, 1:04pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Garth Johnson
Guest

 Re: cigarettes   « Reply #1 on: Jul 23rd, 2002, 11:25pm » Quote Modify Remove

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.
 IP Logged
Guest

 Re: cigarettes   « Reply #2 on: Jul 23rd, 2002, 11:53pm » Quote Modify Remove

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).   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 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.

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
 IP Logged
G. Toye
Guest

 Re: cigarettes   « Reply #3 on: Jul 24th, 2002, 1:56am » Quote Modify Remove

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).
 IP Logged
G. Toye
Guest

 Re: cigarettes   « Reply #4 on: Jul 24th, 2002, 3:02am » Quote Modify Remove

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.
 IP Logged
william wu

Gender:
Posts: 1291
 Re: cigarettes   « Reply #5 on: Jul 24th, 2002, 3:12am » Quote Modify

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!
 « Last Edit: Aug 1st, 2002, 4:11pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Hart Woolery
Guest

 Re: cigarettes   « Reply #6 on: Jul 25th, 2002, 12:46am » Quote Modify Remove

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.

Hart Woolery,
University of California, San Diego
 IP Logged
Gamer555
Newbie

Posts: 19
 Re: HARD: Cigarettes Max Clique   « Reply #7 on: Jul 29th, 2002, 8:31pm » Quote Modify

Wow! We got the big dudes out here

I agree, I don't think more than 6 is possible...
 IP Logged
ScottP
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #8 on: Jul 30th, 2002, 1:13am » Quote Modify Remove

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.
 IP Logged
william wu

Gender:
Posts: 1291
 Re: HARD: Cigarettes Max Clique   « Reply #9 on: Jul 30th, 2002, 4:00am » Quote Modify

SEEEE! I toooold you so. I wouldn't lie.

I really hope someone proves it's optimal. I've had this problem stuck in my head for four months! Waah!
 « Last Edit: Jul 30th, 2002, 4:06am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu

Gender:
Posts: 1291
 Re: HARD: Cigarettes Max Clique   « Reply #10 on: Jul 31st, 2002, 10:49am » Quote Modify

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.

 « Last Edit: Jul 31st, 2002, 5:08pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Nathan_Hellweg
Guest

 Somewhat off topic.   « Reply #11 on: Jul 31st, 2002, 8:18pm » Quote Modify Remove

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.
 IP Logged
Misha Kruk
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #12 on: Jul 31st, 2002, 10:12pm » Quote Modify Remove

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?

 IP Logged
william wu

Gender:
Posts: 1291
 Re: HARD: Cigarettes Max Clique   « Reply #13 on: Aug 1st, 2002, 3:06am » Quote Modify

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
 « Last Edit: Aug 1st, 2002, 3:07am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Misha Kruk
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #14 on: Aug 1st, 2002, 5:59am » Quote Modify Remove

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

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?
 IP Logged
Alex
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #15 on: Aug 1st, 2002, 11:11am » Quote Modify Remove

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.
 IP Logged
Alex F
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #16 on: Aug 1st, 2002, 4:23pm » Quote Modify Remove

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%3D 11-1/ref%3Dsr_11_1/002-3100158-9852021
 IP Logged
Rhaokarr
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #17 on: Aug 2nd, 2002, 9:11pm » Quote Modify Remove

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'...
 IP Logged
william wu

Gender:
Posts: 1291
 Re: HARD: Cigarettes Max Clique   « Reply #18 on: Aug 3rd, 2002, 11:53pm » Quote Modify

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
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: HARD: Cigarettes Max Clique   « Reply #19 on: Aug 29th, 2002, 7:52am » Quote Modify

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.
 « Last Edit: Aug 29th, 2002, 7:52am by James Fingas » IP Logged

Jon
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #20 on: Nov 11th, 2002, 8:40pm » Quote Modify Remove

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.
 IP Logged
SWF
Uberpuzzler

Posts: 879
 Re: HARD: Cigarettes Max Clique   « Reply #21 on: Nov 27th, 2002, 5:53pm » Quote Modify

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.

 IP Logged
paul
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #22 on: Apr 3rd, 2003, 8:41pm » Quote Modify Remove

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
 IP Logged
redPEPPER
Full Member

Posts: 160
 Re: HARD: Cigarettes Max Clique   « Reply #23 on: Apr 4th, 2003, 1:28pm » Quote Modify

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.
 IP Logged
dennis cope
Guest

 Re: HARD: Cigarettes Max Clique   « Reply #24 on: Oct 21st, 2003, 2:45am » Quote Modify Remove

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.
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »