pattern possible?

[DaveC426913]

I'm trying to diagramize some colour swatches at work, and I wanted a pattern that could be scaled up to n colours while still being symmetrical. The key is to ensure that every colour has every other colour as a neighbour.

Possible?

Here's what I mean:
2 colours: a pie cut into 2 pieces, one of each colour. Both pieces are the same shape, both are bordered by the other colour(s).

3 colours: a pie cut into 3 pieces, one of each colour. All 3 pieces are the same shape, all have every other colour as a neighbour.

4 colours: a pie cut into 4 pieces, one of each of 4 colours. But 2 pairs colours do not share a border, sinced they're kitty corner. (It is possible to do it by moving into the 3rd dimension - a tetrahedron will do nicely, but that's cheating.)

Is there a way of making a pattern (no matter how complex or convoluted) such that each colour has the same shape (tile), and each borders every other? And is in only 2-dimensions?

What is the maximum number of colours that one can accomodate?

I doubt there's anything practical that I could use at work, but now I have an academic curiosity.

[LarrrSDonald]

Hmm, interesting. On an intuitive level, it certainly feels like four would be impossible, any attempt to "cross connect" the remaining pairs of the "three each" solution would encircle one of the others, something which obviously cannot happen with identical tiles. I'd suspect a proof would involve this somehow, in order to border on four one of the four must be completely enclosed by the other three, not something one can accomplish with identical tiles. I'm certainly not by any means enough of a topologist to make a formal argument for this though.

Three is certainly possible (existance example above) and five is certainly impossible (special case of the four color problem - it's not even possible with *any* tiles, identical or otherwise) so really it boils down to proving four impossible (or possible, without solid proof I supposed can't be considered entirely off the table).

[NateTG]

I don't think you've got the problem described well enough to get a definitive answer.

[Jimmy Snyder]

I have a solution, but you aren't going to like it. I expect you will add a new rule to prevent it.

First, divide the pie into 8 regular pieces each forming a 45 degree central angle. The color them as follows:

1 2
3 3
4 4
1 2


Consider the two pieces colored 1 as a single region, and so on with the other colors. Then there are 4 regions, each the same shape, and each bordering on 3 other colors.

Edit: the 1 and 2 in the last row are supposed to line up with those in the first row. Can someone tell me what I am doing wrong with the [code] tag? Or is there a better way to line things up?

[ceptimus]

Three is certainly possible (existance example above) and five is certainly impossible (special case of the four color problem - it's not even possible with *any* tiles, identical or otherwise) so really it boils down to proving four impossible (or possible, without solid proof I supposed can't be considered entirely off the table).

http://www.mround.pwp.blueyonder.co.uk/physics/image/four_touching.gif

I think four is easy enough. The width of the arms of the Ls in the above diagram has to have this ratio to the length for this diagram to work.

width = \frac{length(2 - \sqrt{2})}{2}

[-Job-]

Nice try, but i believe in the ol'book o'rules, that is cheating. To quote "tiles touching at a single point shall not be considered as bounding eachother". Otherwise a circle divided into four slices would work just as nicely as they all "touch eachother" in the center of the circle.

Edit: Of course all you need to do is cut away the edges and you'll be fine. :smile:

[LarrrSDonald]

I was kind of thinking the same thing, i.e. if a single point is considered ok then the original 4 slice pie would have been fine. However, it might well be that non-single point contact can be made but reshaping the slices a bit and it cetainly ruins my previous argument.

[ceptimus]

Yes, I was going to post that you could chamfer off the corners at 45 degrees and adjust the width:length of the V shapes slightly to compensate - that way you get proper surface to surface contact rather than point/line.

But the diagram does show that 4 identical two-dimensional shapes can all touch each other, in two dimensions.

[Cybersteve]

I'm not sure if you can chamfer off the corners and keep all the tiles the same size. To make the inner two "L" s touch the sides you'd have to increase their "width" when you do this to the outer two "L"s they wouldn't touch in the middle.

[NateTG]

I'm not sure if you can chamfer off the corners and keep all the tiles the same size. To make the inner two "L" s touch the sides you'd have to increase their "width" when you do this to the outer two "L"s they wouldn't touch in the middle.

You can do this by only chamfering half the edges away. Then there woudld be a notch in the bottom, but the two bottom pieces woudl still touch.

Three is certainly possible (existance example above) and five is certainly impossible (special case of the four color problem - it's not even possible with *any* tiles, identical or otherwise) so really it boils down to proving four impossible (or possible, without solid proof I supposed can't be considered entirely off the table).

The problem, as stated, does not require that there only be one tile per color. If we use multiple tiles of the same color, it's always possible to meet the design specification. In fact, it's always going to be possible to make a single row arrangement that shows all possible color pairings with that many tiles.

A more interesting question to ask might be what the minimal area or diameter is for a particular tile shape and color count.

[ceptimus]

I altered the diagram to show the chamfered corners.

http://www.mround.pwp.blueyonder.co.uk/physics/image/four_touching.gif

[DaveC426913]

I have a solution, but you aren't going to like it. I expect you will add a new rule to prevent it.
First, divide the pie into 8 regular pieces each forming a 45 degree central angle. The color them as follows:

1 2
3 3
4 4
1 2

Consider the two pieces colored 1 as a single region, and so on with the other colors. Then there are 4 regions, each the same shape, and each bordering on 3 other colors.
Edit: the 1 and 2 in the last row are supposed to line up with those in the first row. Can someone tell me what I am doing wrong with the [code] tag? Or is there a better way to line things up?
Yeah, I don't know why it doesn't work. I use periods as spacers and colour them white:

..1.2
3.....3
4.....4
..1.2

But I get your idea, I was trying the same thing. It then raises the questions: is there a consistent, symmetrical and aesthetically-pleasing pattern? And can it be scaled up to n colours?

[-Job-]

Bravo ceptimus, i tried for a while to figure out how to have the 4 ones touching and i admit i didn't find suitable tiling for this. Whoever gets 5 ought to get a prize. :smile:

[LarrrSDonald]

<joins in the applause> Very nice. I still feel that given continous pieces of one color each, five still ought to be impossible as per the four color problem. Yes, I agree, the original problem is stated a bit haphazardly and doesn't prevent that and possibly other things. I figured that this was one of those times where there's an implied "... and any other formalizations required to kill off the obvious solutions". I certainly don't mind people pointing them out and/or playing with them, but it's not something I'm personally into so I opted to think about it more in the way I assume it was ment.

On the four deal, the solution does indeed involve one being enclosed in the other three (the center L). I couldn't see how this could be with identical pieces, which in hindsight was obviously a terrible assumption as ceptimus has kindly showed. However, with five continous pieces of one color each, I don't see how it could be done without breaking the four color problem (or, rather, disproving it's core, which at this point seems unlikely).

[shmoe]

I can't see anyway this can be connected to the four-colours problem.

5 (or more) shapes is impossible if you assume 1 "piece" per shape (say homeomorphic to a closed disc), even if you allow different shapes for each colour. This would get you a planar embedding of the complete graph on 5 vertices, which is impossible.

[Moo Of Doom]

I can't see anyway this can be connected to the four-colours problem.
If you have 5 regions that are all neighbors, you could not color them with 4 colors without two neighboring regions sharing a color. Thus the four-color map theorem very directly implies the inexistance of 5 mutually neighboring regions.

[Ubern0va]

I'm not sure how much this differs from the pattern posted here a while ago by another user, but I was doodling the other day and I thought of this one (http://i7.photobucket.com/albums/y300/medrawuc/4_shapes.jpg).

When I look at it now, I realize that the shape could be simplified (to just a letter M), but the idea remains the same :)