4 edits
Originally posted by forkedknightWhat you say is correct (follows from pigeonhole principle). But I think Shallow Blue meant he thinks one could get it down to 2 crayons (thus 3 colors, including the white). Or at least I am trying to give him the benefit of the doubt. 🙂
It's fairly easy to prove that you can't do it with two colors:
Assume an equilateral triangle with side = 1 unit.
The color at each vertex must be different since each vertex is one unit away from both other vertices.
To deal with boundary points in smartarin's solution we can simply color all boundary points between regions the color of the region directly to the left. This leaves 5 boundary points on the left side of the page, which we color B if the color to the right is A and D if it is C (using smartarin's labels).
Originally posted by AnthemNice, I agree. I think this does resolve my earlier objections.
To deal with boundary points in smartarin's solution we can simply color all boundary points between regions the color of the region directly to the left. This leaves 5 boundary points on the left side of the page, which we color B if the color to the right is A and D if it is C (using smartarin's labels).
So it seems we have demonstrated that we can do it with 7 crayons (eight colors). But can it be done with fewer?
Originally posted by AnthemI like the idea of hexagonal packing, but I do not think this proposed solution works. In your ABC geometry, consider for example the cluster that consists of adjacent A & B circles in row x and the touching adjacent C & A circles in row x+1. The center points of these circles should outline a rhombus with two 60-degree angles and two 120-degree angles. The long diagonal of this rhombus (which connects the center points of the two A circles) should have length = 2*Cos(30deg) = SQRT(3). But then that means the two A circles are, at their closest, only SQRT(3) - 1 = ~0.732 units apart. This means that there will be sets of two points along this diagonal that are both one unit apart and both A color. Am I missing something here in this analysis?
I believe I have a way to do 6 colors (5 crayons). To make it easier I'm going to describe it on an infinite plane (out of which any 5x5 square will work).
Originally posted by PalynkaI think Anthem's latest suggestion with hexagons will still work. We just need a proviso analogous to the previous ones (such as, the terminal points on the 1 unit length diagonals you mention would take the same color as the point directly to their left).
Hexagons with side length equal to 1/2 don't work as the longest diagonals are of length equal to 1...
Not sure if hexagons will work...
So what I understood is that, in this model a regular hexagon is surrounded by 6 other hexagons (flower shape), hence there are 7 distinct colors. But, although the diagonal of the hexagon is 1 unit, the distance between two opposite sides is less than 1 unit.
So when you create another set of petals (total 12 hexagons) surrounding the small flower, you cannot use the center most color in any of these 12 hexagons. You cannot map these outer hexagons with remaining 6 colors as well.
Try that...
Originally posted by LemonJelloGoing outside the box...
Suppose I give you a white, blank card. Suppose it is square with side length of 5 (arbitrary) units. Suppose I have a bunch of crayons of all different colors. Suppose I tell you that you need to color one side of the card (either partially colored or fully colored, however you want to do it) such that when you finish there will be no set of two point ...[text shortened]... and (2) the two points have the same color.
What is the minimum number of crayons you need?
Euclidean geometry does not consider a line (eg, a diagonal) to be a collection of points. This has implications that I will skip over.
It was not stated that a unit was more than a point. The solution has to cover this possibility. A 5 x 5 square of points.
So the problem is reduced to this minimal case: A figure consists of a square, 5 points by five points. How can they be minimally colored (labelled) so that no neighboring points, diagonally, horizontally, or vertically, are of the same color (label)?
This is easy to solve.
So, expand the square to one consisting of 25 units, each one of them a 2 by 2 set of points. Is the solution any different?
Originally posted by smartarinYes, this solution takes that into account. So, the first layer of petals surrounding any 'A' petal is (counter clockwise starting from the right): BFEGCD. The next layer is CGDCBDFBEFGE.
Not sure if hexagons will work...
So what I understood is that, in this model a regular hexagon is surrounded by 6 other hexagons (flower shape), hence there are 7 distinct colors. But, although the diagonal of the hexagon is 1 unit, the distance between two opposite sides is less than 1 unit.
So when you create another set of petals (total 12 hexag ...[text shortened]... 2 hexagons. You cannot map these outer hexagons with remaining 6 colors as well.
Try that...
To get from any hexagon to another of the same color you need to go to 3 layers of petals out, which is more than 1 unit.
- Joined
- 18 Jan 07
- Moves
- 12477
Originally posted by LemonJelloNo, I was just not thinking right when I posted that answer. Nothing in it, I fear, is correct.
What you say is correct (follows from pigeonhole principle). But I think Shallow Blue meant he thinks one could get it down to 2 crayons (thus 3 colors, including the white). Or at least I am trying to give him the benefit of the doubt. 🙂
Richard
Originally posted by JS357It was not stated that a unit was more than a point
Going outside the box...
Euclidean geometry does not consider a line (eg, a diagonal) to be a collection of points. This has implications that I will skip over.
It was not stated that a unit was more than a point. The solution has to cover this possibility. A 5 x 5 square of points.
So the problem is reduced to this minimal case: A figure consists of ...[text shortened]... consisting of 25 units, each one of them a 2 by 2 set of points. Is the solution any different?
Yes, definitely outside the box. For this problem, I think one has to assume that by a square card of 5 (arbitrary) units on a side, we are at least talking about some set of points that has the cardinality of the continuum; whereas the set of points you describe is countable. We can take 1 unit of length as small as we like, but I think we should still concern ourselves with non-zero length; whereas you are talking about discrete points, which have no length. I am not sure what this thought experiment can tell us, since the operation you specify (expanding by adding in more discrete points) is countable and hence can never scale to the continuum.