3
$\begingroup$

I was inspired by this puzzle.

What is the longest binary string of "0" and "1" you can form such that no "0" is halfway between two other "0" and no "1" is halfway between two other "1"?

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer is

8, example: 01100110

Remark:

For every finite alphabet (eg. 0,1,...,n-1), there is always a finite maximal length W(n,3)-1 among strings without 3-term arithmetic progressions. This is Van der Waerden's theorem:

https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

$\endgroup$
6
  • $\begingroup$ Why community wiki? $\endgroup$
    – justhalf
    Jul 11, 2023 at 3:03
  • $\begingroup$ That's correct. Thanks for the reference. $\endgroup$ Jul 11, 2023 at 3:19
  • $\begingroup$ @justhalf Because I don't need reputation points for being able to link to Wikipedia $\endgroup$
    – user78949
    Jul 11, 2023 at 3:28
  • 1
    $\begingroup$ @justhalf The question itself is not too easy, but pointing to a source that contains a solution is too easy. $\endgroup$
    – user78949
    Jul 11, 2023 at 3:32
  • 1
    $\begingroup$ I made a harder version of this question. $\endgroup$ Jul 11, 2023 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.