Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering that if there exists a simple proof that the van der Warden's number W(3,3) (the smallest positive integer $n$ such that any 3-coloring of the set $\{1, 2, ..., n\}$ has a monochromatic 3-AP) equals 27. Also, it would be great if someone can present me a counterexample for $n=26$.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The complete list of length-26 examples is:

    AABBAABCBCCACAABABBCACCBCB
    AABBCAACACBBCCBBCACAACBBAA
    AABCBAACACBBCCBBCACAABCBAA
    AACBCAABABCCBBCCBABAACBCAA
    AACCAACBCBBABAACACCBABBCBC
    AACCBAABABCCBBCCBABAABCCAA
    ABAABABCCBBCCBABAABCCAACAC
    ABABBAACBBCBCAACCAACBCBBCA

not counting relabeling of the colors. (So there are 48 examples in all.)

I don't know of any proof that 27 is exact, other than a suitably-pruned exhaustive search.

I have source code that I wrote about 25 years ago that does the search, plus some discussion, on my blog. The code took a couple of days to run when I first wrote it, but to run it now is very quick.

share|improve this answer
    
That is very interesting! Thank you very much. –  a12345 Jan 14 '13 at 17:27
    
I don't think you should be so quick to accept the answer, particularly since it's incomplete. What if there is a simple proof that 27 is exact, and I don't know it, and the person who does know it skips over this question because you accepted an answer already? If I were you, I'd un-accept the answer, and wait a couple of days to see what else turns up. –  MJD Jan 14 '13 at 17:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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