Author |
Topic: Mutually Touching Objects (Read 847 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Mutually Touching Objects
« on: Jan 23rd, 2004, 9:38am » |
 Quote  Modify
|
1. What is the maximum number of convex polygons in the plane, non-overlapping and such that any pair of them have a common boundary of positive length?
2. What is the maximum number of convex polyhedra in the 3D space, non-overlapping and such that any pair of them have a common boundary of positive area?
|
| « Last Edit: Jan 24th, 2004, 12:25am by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mutually Touching Objects
« Reply #1 on: Jan 23rd, 2004, 10:20am » |
Quote Modify
|
on Jan 23rd, 2004, 9:38am, Barukh wrote:| 1. What is the maximum number of convex polygons, non-overlapping and such that any pair of them have a common boundary of positive length? |
|
infinitely many, in infinite dimensional space..  (Or even in just 3D space actually..)
::for 2D I can get at least 4::
Quote:2. What is the maximum number of convex polyhedra, non-overlapping and such that any pair of them have a common boundary of positive area?
|
|
Probably also infinite for nD (n>3) space 
|
| « Last Edit: Jan 23rd, 2004, 10:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Mutually Touching Objects
« Reply #2 on: Jan 24th, 2004, 12:28am » |
Quote Modify
|
OK, I forgot to mention that the objects should be considered in corresponding dimensions  - I modified the problem statement.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Mutually Touching Objects
« Reply #3 on: Jan 24th, 2004, 3:44am » |
Quote Modify
|
1)::The four-colour theorem states that for any arrangement of connected regions in the plane, they can be coloured using four colours such that no adjacent regions share a colour, so no subset of five or more regions, be they convex or otherwise can touch each other. Finding a set of four convex polygons is easy.::
2) I've only managed a lower bound on this one ::5 - four arranged tetrahedrally with a little one in the middle:: though for non-convex, the answer is of course that you can get arbitrarily many.
[e]Someday I'll get the hang on hide tags...[/e]
|
| « Last Edit: Jan 24th, 2004, 3:46am by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Mutually Touching Objects
« Reply #4 on: Jan 24th, 2004, 4:21am » |
Quote Modify
|
2) Further thought reminds me that this is a general case of Cigarettes Max Clique - one of the long-term unsolved problems (currently stuck at 7 for long enough identical cylinders; 8 for varying lengths)
[e]fixed link[/e]
[e2]re-fixed link[/e2]
|
| « Last Edit: Apr 29th, 2004, 1:18pm by rmsgrey » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Mutually Touching Objects
« Reply #5 on: Jan 25th, 2004, 6:46am » |
Quote Modify
|
Good observations, rmsgrey  ! Despite some similiarity to the mentioned problem, the answer is completely different. In fact, it's much much bigger. Remember: there's no resitriction on the shapes of polyhedra.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Mutually Touching Objects
« Reply #6 on: Jan 25th, 2004, 10:32am » |
Quote Modify
|
There is a pretty big restriction on the shapes of polyhedra - they're required to be convex - without which, there is no upper bound.
I forgot to say that, while the cigarettes problem is a special case (and currently stalled without proof), the general case may well be easier to solve.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Mutually Touching Objects
« Reply #7 on: Jan 25th, 2004, 10:53am » |
Quote Modify
|
on Jan 25th, 2004, 10:32am, rmsgrey wrote:| There is a pretty big restriction on the shapes of polyhedra - they're required to be convex - without which, there is no upper bound. |
|
Well, what I meant: they don't need to have the same shape, and the shape mustn't be cylindrical.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mutually Touching Objects
« Reply #8 on: Jan 25th, 2004, 11:15am » |
Quote Modify
|
There is another difference with the cigarette case, the objects mustn't only touch, but must share a non-zero area boundary (as is stipulated in the puzzle) This pretty much rules out cylinders for consideration..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Mutually Touching Objects
« Reply #9 on: Jan 25th, 2004, 4:05pm » |
Quote Modify
|
But it's not hard to modify cylinders to provide a non-zero area in contact without sacrificing their convexity - just replace them with n-gon prisms for some large n
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Mutually Touching Objects
« Reply #10 on: Jan 27th, 2004, 6:49pm » |
Quote Modify
|
An infinite number of polyhedra can fit condition 2. I already drew one picture for the riddles forum today, and don't feel like making another one today. Perhaps there is an easier to describe method, but my idea is basically to start with polyhedron number 1 as a large flat block, and cut with a plane to remove a thin wedge. Call that wedge polyhedron 2 and put back in place. Keep cutting with new planes at strategic locations so it cuts all the previous shapes, remove the new thin wedge (containing pieces from each of the pre-existing polyhedra) and replace by a single polyhedron and repeat. The cut must be done correctly so it does not ruin the other polyhedra all touching one another.
There is a systematic way of doing this, and cutting a convex polyhedron with a plane always leaves convex polyhedra. Maybe I will try to draw it and more clearly explain tomorrow.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
 
 
Gender:
Posts: 767
|
|
Re: Mutually Touching Objects
« Reply #11 on: Jan 28th, 2004, 5:49am » |
Quote Modify
|
on Jan 24th, 2004, 3:44am, rmsgrey wrote:| 1)::The four-colour theorem states that for any arrangement of connected regions in the plane, they can be coloured using four colours such that no adjacent regions share a colour, so no subset of five or more regions, be they convex or otherwise can touch each other. Finding a set of four convex polygons is easy.:: |
|
I thought the problem was restricted to polygons touching along a boundary with positive length, so corners don't count. The four-color theorem implies corners, or boundaries of zero length.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Quetzycoatl
Newbie
Gender:
Posts: 46
|
on Jan 28th, 2004, 5:49am, John_Gaughan wrote:
I thought the problem was restricted to polygons touching along a boundary with positive length, so corners don't count. The four-color theorem implies corners, or boundaries of zero length. |
|
Actually I think it excludes 0 length boundaries. Anyway here is an example of 4 convex polygons sharing non-zero length positive boundaries.
|
|
IP Logged |
 |
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Mutually Touching Objects
« Reply #13 on: Jan 28th, 2004, 12:12pm » |
Quote Modify
|
Thank you for the image, I don't know why I didn't think of that. I'm a little slower than usual today
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Mutually Touching Objects
« Reply #14 on: Jan 28th, 2004, 3:13pm » |
Quote Modify
|
And Quetzycoatl is correct about the 4-color theorem. It only counts regions as adjacent if they share a border of positive length. If you counted touching only at a single point, maps requiring an arbitrary number N of colors are easy to draw: choose a point and draw N distinct rays out from it. This divides the plane into N regions all of which touch at the common point.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Mutually Touching Objects
« Reply #15 on: Jan 29th, 2004, 11:47pm » |
Quote Modify
|
on Jan 27th, 2004, 6:49pm, SWF wrote:| An infinite number of polyhedra can fit condition 2... |
|
Bravo, SWF, that's right! Just to make it more clear: how many faces the polyhedron #N has in your construction?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Mutually Touching Objects
« Reply #16 on: Apr 29th, 2004, 8:48am » |
Quote Modify
|
I seem to remember there is a solution with an infinite number of polhedras all identical. They look like a 3d parabola approximated with flat faces.
PS: I have given it another thought tonight, and what I was thinking of does not work. Sorry.
|
| « Last Edit: Apr 30th, 2004, 1:29am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print