Author |
Topic: HARD: Cigarettes Max Clique (Read 42505 times) |
|
Garth Johnson
Guest
|
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 |
|
|
|
Bob Baddeley
Guest
|
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
|
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
|
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
wu::riddles Administrator
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
|
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 |
|
|
|
william wu
wu::riddles Administrator
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
|
|
|
Nathan_Hellweg
Guest
|
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
|
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?
|
|
IP Logged |
|
|
|
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
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?
|
|
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 |
|
|
|
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
wu::riddles Administrator
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 |
Doc, I'm addicted to advice! What should I do?
|
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
