On Thu, Aug 13, 2015 at 4:56 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Choose k sufficiently large that any 2-colouring of {1, 2, ..., 2^(2k + 1)} contains a monochromatic arithmetic progression of length N.
How do you know that such a k exists?
Andy
Van der Waerden's theorem. Rich Schroeppel mentioned that Szemeredi's theorem, a hard generalisation of van der Waerden's theorem, kills the problem immediately without requiring the property that reversing the sequence flips the colours. In fact, Szemeredi actually kills the original 'game question': just keep choosing numbers arbitrarily from {1, 2, 3, ..., N}, and once you have N/2 of them (which your opponent can't prevent) then you can guarantee a length-k arithmetic progression (as long as you carefully chose N as a function of k). Sincerely, Adam P. Goucher