5
$\begingroup$

As part of a proof in finding the minimum coloured grid that is guaranteed to have some four points that form an aligned square of one colour, I formed a technique that requires finding the smallest line of $n$-coloured points, or equivalently the shortest string of $n$ different letters, that is guaranteed to have a regularly-spaced set of the same colour (letter).

For two colours and looking for a regularly spaced set of three points, we require $9$ points as shown in the following cases, forced from the initial patterns (shown red):

$\mathtt {\color{red}{OOXO}OXX?}$
$\mathtt {\color{red}{OOXX}OOX?X}$
$\mathtt {\color{red}{OXOO}XOXX?}$
$\mathtt {\color{red}{OXOX}XOXO?}$
$\mathtt {\color{red}{OXX}OOXXO?}$

Where in each case the $\mathtt{?}$ creates a regularly-spaced triplet whether filled with $\mathtt{O}$ or $\mathtt{X}$. For example in the final case we produce either a regular set of $\mathtt{X}$s on a 3-step or a regular set of $\mathtt{O}$s on a 4-step pattern.

Is there a method of finding a bound on the number of total points required to be sure of a regularly-spaced set of $k$ points all of the same colour in an $n$-colouring?

$\endgroup$
  • 4
    $\begingroup$ Van der Waerden's theorem $\endgroup$ – bof Jul 23 '18 at 6:57
  • $\begingroup$ @bof - ouch. a very tricky problem then. Limited answers very welcome. $\endgroup$ – Joffan Jul 23 '18 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.