# Coloring the integers

Here is a problem I composed, which recently appeared on the Colorado Mathematical Olympiad.

If one wishes to color the integers so that every two integers that differ by a factorial get different colors, what is the fewest number of colors necessary?

I might describe a solution, as well as some related history, in a future post. But for now I’ll just say that Adam Hesterberg solved this problem at Canada/USA Mathcamp a few summers ago, claiming the \$20 prize I offered almost as soon as I offered it. At the time, I suspected but still did not know the exact answer.

Although the wording of the problem strongly suggests that the answer is finite, I don’t think that this is entirely obvious.

Along those lines, here is another infinite graph with finite chromatic number.

If one wishes to color the points of the Euclidean plane so that every two points at distance one get different colors, what is the fewest number of colors necessary?

This is one of my favorite unsolved math problems, just for being geometrically appealing and apparently intractably hard. After fifty years of many people thinking about it, all that is known is that the answer is 4, 5, 6, or 7. Recent work of Shelah and Soifer suggests that the exact answer may depend on the choice of set theoretic axioms.

This inspired the following related question.

If one wishes to color the points of the Euclidean plane so that every two points at factorial distance get different colors, do finitely many colors suffice?

More generally, if $S$ is a sequence of positive real numbers that grows quickly enough (say exponentially), and one forbids pairs points at distance $s$ from receiving the same color, one would suspect that finitely many colors suffice. On the other hand, if $S$ grows slowly enough (say linearly), one might expect that infinitely many colors are required.

Posted in expository
Tagged combinatorics

# Mathematical art

Blog at WordPress.com. | Theme: Dusk To Dawn by Automattic.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 3, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9580878615379333, "perplexity_flag": "middle"}