Erdős [Er75f] says Graham and Selfridge proved the answer is yes when $k=3$.

Hunter has observed that, for sufficiently large $n$, a generic projection of $[k]^n$ into $\mathbb{R}^2$ has this property, by the Hales-Jewett theorem.

View the LaTeX source

This page was last edited 19 October 2025. View history

• I believe I have formalized a proof of this problem. I gave Aristotle the problem statement and told it that it "may find Combinatorics.Line.exists_mono_in_high_dimension helpful" (the equivalent of Hales-Jewett in Mathlib), and it got 95% of the way there. It set up the problem to prove that there is some line with at least $k$ points of the same color, but its theorem statement did not require that all the points on the line had the same color. So I asked Gemini 3.0 Flash to write a theorem that matches the problem and prove it, and it did so without having to add any additional lemmas, just the theorem.
  
  I also removed the unused lemmas and fixed the warnings.
  
  Type-check it online!

  (The site has been updated to address this comment.)
  JoshuaB — 20:40 on 27 Feb 2026

  👍 1 📝 0 🤖 0

• the answer is yes: recall Hales Jewett and generically project $[k]^n$ into $\mathbb{R}^2$.

  (The site has been updated to address this comment.)
  zach hunter — 10:19 on 17 Oct 2025

  👍 1 📝 0 🤖 0