[math-fun] Futility Closet
This blog is thoroughly delightful, with brain teasers and historical oddities. In particular, I thought the solution to this tiling problem was quite lovely, and generalizes to other shapes: http://www.futilitycloset.com/2012/09/30/tiling-task/ Upon further reading, it appears to be related to the mutilated chessboard problem.
* Jason <jason@lunkwill.org> [Mar 31. 2013 09:21]:
This blog is thoroughly delightful, with brain teasers and historical oddities. In particular, I thought the solution to this tiling problem was quite lovely, and generalizes to other shapes:
http://www.futilitycloset.com/2012/09/30/tiling-task/
Upon further reading, it appears to be related to the mutilated chessboard problem.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That's a mild generalization of the problem whether a chessboard with two opposing corners removed can be covered with dominoes. (Dunno whether this is just the "mutilated chessboard problem"). Here's one that I find delightful: Show that for every possible coloring of the plane with two colors there exist, for every distance d, two points of distance d with the same color. [Spoiler below] ... ... ... soon be spoiler ... ... ... oh noes! ... Spoiler: Put an equilateral triangle with side length d anywhere. At least two vertices must have the same color. Is this neat or just dumb? Discuss with your neighbor.
You can strengthen that to three colors, and there's still a nice solution: Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color. Tom Joerg Arndt writes:
Here's one that I find delightful: Show that for every possible coloring of the plane with two colors there exist, for every distance d, two points of distance d with the same color.
On 31/03/2013 20:33, Tom Karzes wrote:
You can strengthen that to three colors, and there's still a nice solution:
Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color.
And [spoilerish comment follows] ... ... ... ... ... ... ... ... ... ... ... ... ... ... the proof also involves simple manipulations of equilateral triangles. -- g
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Apr 01. 2013 07:42]:
On 31/03/2013 20:33, Tom Karzes wrote:
You can strengthen that to three colors, and there's still a nice solution:
Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color.
Me. Very. Stupid. I cannot see how to do this. (Only: "for each d, two points of distance either d or sqrt(2)*d"). I am not asking for the solution (yet!), but just a slightly spoilier spoiler than that below.
And [spoilerish comment follows] ...
[...]
... the proof also involves simple manipulations of equilateral triangles.
-- g
[...]
Can anyone *disproof*: "For every coloring of the plane with finitely many colors and every d there are always two points of the same color with distance d" ?
Can anyone *disproof*: "For every coloring of the plane with finitely many colors and every d there are always two points of the same color with distance d" ?
(spoiler) http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Apr 2, 2013 at 2:04 PM, Joerg Arndt <arndt@jjj.de> wrote:
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Apr 01. 2013 07:42]:
On 31/03/2013 20:33, Tom Karzes wrote:
You can strengthen that to three colors, and there's still a nice solution:
Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color.
Me. Very. Stupid. I cannot see how to do this. (Only: "for each d, two points of distance either d or sqrt(2)*d").
I am not asking for the solution (yet!), but just a slightly spoilier spoiler than that below.
And [spoilerish comment follows] ...
[...]
... the proof also involves simple manipulations of equilateral triangles.
-- g
[...]
Can anyone *disproof*: "For every coloring of the plane with finitely many colors and every d there are always two points of the same color with distance d" ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sure. Tile the plane with regular hexagons, spaced so their centers are one unit apart. Oriented, say, so that 2 sides of each hexagon are parallel to the x-axis. Specifically so that each hexagon contains three consecutive of its *open* sides (say the bottom, SE, and NE), and two of its vertices (say the SW and NE ones): o * \ o o / *--o Group the hexagonal tiles into rosettes of 7. Use 7 colors (like ROYGBIV) to color each rosette of 7 hexagons the same way. Then if I haven't screwed up, no two points of the same color can be 1 unit apart. --Dan On 2013-04-02, at 11:04 AM, Joerg Arndt wrote:
Can anyone *disproof*: "For every coloring of the plane with finitely many colors and every d there are always two points of the same color with distance d" ?
Spoilier spoiler: Place two equilateral triangles edge-to-edge, and consider the properties of the resulting rhombus. Tom Joerg Arndt writes:
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Apr 01. 2013 07:42]:
On 31/03/2013 20:33, Tom Karzes wrote:
You can strengthen that to three colors, and there's still a nice solution:
Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color.
Me. Very. Stupid. I cannot see how to do this. (Only: "for each d, two points of distance either d or sqrt(2)*d").
I am not asking for the solution (yet!), but just a slightly spoilier spoiler than that below.
* Tom Karzes <karzes@sonic.net> [Apr 03. 2013 08:34]:
Spoilier spoiler:
Place two equilateral triangles edge-to-edge, and consider the properties of the resulting rhombus.
That was the first thing I tried, but the configuration B R R G suggests "no fish" to me: the distance R--R is unequal to the distances R--g and R--B, a case of "either d or sqrt(3)/2*d" (if I got the constant right). However, Charles' pointer to http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane (especially the image "Solomon W. Golomb's ten-vertex four-chromatic unit distance graph") convinces me (3-color wise). Given the problem has a name (and having been considered by heavy duty mathematicians) I consider myself only semi stupid now. Thanks everybody! Best, jj
Tom
Joerg Arndt writes:
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Apr 01. 2013 07:42]:
On 31/03/2013 20:33, Tom Karzes wrote:
You can strengthen that to three colors, and there's still a nice solution:
Show that for every possible coloring of the plane with three colors there exit, for every distance d, two points of distance d with the same color.
Me. Very. Stupid. I cannot see how to do this. (Only: "for each d, two points of distance either d or sqrt(2)*d").
I am not asking for the solution (yet!), but just a slightly spoilier spoiler than that below.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Complete spolier: There's a much simpler solution. The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color (the distance between the two furthest points of the rhombus). So, why not make an isosceles triangle whose two long edges are that length, and whose short edge is length d? Then all three vertices must be the same color, two of which are separated by d. Problem solved. You can obtain this configuration with individual vertices using a mere 7 vertices: Two rhombuses joined at one end, with the opposite ends separated by distance d. I find this graph simpler and more intuitive than the 10-vertex graph from the wiki page. Alternatively, consider the circle of radius sqrt(3)*d. All points on the circle must be the same color as the center, and hence each other. Now draw a chord of length d on the circle. You can think of the rhombus as a compass of radius sqrt(3)*d. I first saw this problem as an interview question years ago. Tom Joerg Arndt writes:
* Tom Karzes <karzes@sonic.net> [Apr 03. 2013 08:34]:
Spoilier spoiler:
Place two equilateral triangles edge-to-edge, and consider the properties of the resulting rhombus.
That was the first thing I tried, but the configuration
B R R G
suggests "no fish" to me: the distance R--R is unequal to the distances R--g and R--B, a case of "either d or sqrt(3)/2*d" (if I got the constant right).
However, Charles' pointer to http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane (especially the image "Solomon W. Golomb's ten-vertex four-chromatic unit distance graph") convinces me (3-color wise).
Given the problem has a name (and having been considered by heavy duty mathematicians) I consider myself only semi stupid now.
Thanks everybody! Best, jj
On Apr 3, 2013, at 3:09 AM, Tom Karzes wrote:
The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color
I don't think that follows: that's only the case if all pairs of points at distance d are different colors. But the rhombus does show that, for every d, either there is a pair at distance d or a pair at distance sqrt(3)d with the same color (in any 3-coloring). The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting: http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.) Cris
I do know that it's frequently mentioned that the chromatic number of the [unit-distance graph of the] plane is between 4 and 7, inclusive. This implies by meta-reasoning that no one has yet found a unit-distance graph of points on the plane that needs more than 4 colors. (The hexagonal 7-coloring I mentioned recently is the proof that 7 colors suffices, so 7 is an upper bound.) ----- IF there's a unit distance graph of points in the plane that requires 5 colors, say, can one at least find an upper bound on the number of vertices that the smallest such graph -- if any -- would require? After all, the Moser spindle uses only 7 points. How many more points could a 5-color unit distance graph from the plane possibly need? --Dan On 2013-04-03, at 4:24 PM, Cris Moore wrote:
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
Perhaps a proof theorist can give a truly horrific bound? Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Apr 3, 2013 at 7:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I do know that it's frequently mentioned that the chromatic number of the [unit-distance graph of the] plane is between 4 and 7, inclusive.
This implies by meta-reasoning that no one has yet found a unit-distance graph of points on the plane that needs more than 4 colors.
(The hexagonal 7-coloring I mentioned recently is the proof that 7 colors suffices, so 7 is an upper bound.) -----
IF there's a unit distance graph of points in the plane that requires 5 colors, say, can one at least find an upper bound on the number of vertices that the smallest such graph -- if any -- would require?
After all, the Moser spindle uses only 7 points. How many more points could a 5-color unit distance graph from the plane possibly need?
--Dan
On 2013-04-03, at 4:24 PM, Cris Moore wrote:
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I guess I wasn't explicit enough about the proof strategy. I'll try to state it more completely. Assume, for a given d, and for some 3-coloring of the plane, that all points separated by distance d are different colors. Then try to prove a contradiction, i.e. that there must exist two points separated by distance d that are in fact the same color. If you can do that, then the original assummption must be false. Which in turn implies that there exists no 3-coloring of the plane for which all points separated by distance d are separate colors. The claim I made about all points separated by distance sqrt(3)*d being the same color must be true if in fact all points separated by distance d are different colors, as you said. It is a logical implication of that assumption. But that implication can be used to show that the original assumption cannot hold. So yes, once we reach a contradiction, we know that all points separated by distance d are not different colors, and therefore that all points separated by distance sqrt(3)*d may not be the same color. I.e., the entire chain of implications breaks down. Since the original assumption is seen to be false, then everything that follows from it is suspect. But at that point it no longer matters. That's how proof by contradication works, yes? As I described, this leads to a simpler 7-vertex graph, with a more intuitive approach to its construction, than the 10-vertex graph on the wiki page. I'd include it here, except I don't think ascii art will suffice. But it should be clear that this graph cannot be 3-colored without two connected vertices being the same color. Tom Cris Moore writes:
On Apr 3, 2013, at 3:09 AM, Tom Karzes wrote:
The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color
I don't think that follows: that's only the case if all pairs of points at distance d are different colors.
But the rhombus does show that, for every d, either there is a pair at distance d or a pair at distance sqrt(3)d with the same color (in any 3-coloring).
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
Cris
Oh, right... if all pairs of points at distance sqrt(3)d were the same color, then this would also be true of any pair of points at distance d, with your isosceles triangle. So this gives another way to express the challenge of improving the lower bound: is there a unit-distance graph G with a pair of vertices u,v such that, for all 4-colorings of G, u and v are forced to be the same color? (Exercise: if there is, then there is a unit-distance graph G' that is not 4-colorable.) Cris On Apr 3, 2013, at 5:58 PM, Tom Karzes wrote:
The claim I made about all points separated by distance sqrt(3)*d being the same color must be true if in fact all points separated by distance d are different colors, as you said. It is a logical implication of that assumption. But that implication can be used to show that the original assumption cannot hold.
Indeed, the maximum number of a unit distance graph is exactly the chromatic number of the plane. See http://dimacs.rutgers.edu/~hochberg/undopen/graphtheory/graphtheory.html But bizarrely, for infinite unit-distance graphs, this can depend on the axioms of set theory! See http://arxiv.org/abs/0707.1177 - Cris
On Apr 3, 2013, at 3:09 AM, Tom Karzes wrote:
The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color
I don't think that follows: that's only the case if all pairs of points at distance d are different colors.
But the rhombus does show that, for every d, either there is a pair at distance d or a pair at distance sqrt(3)d with the same color (in any 3-coloring).
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
Cris
participants (7)
-
Charles Greathouse -
Cris Moore -
Dan Asimov -
Gareth McCaughan -
Jason -
Joerg Arndt -
Tom Karzes