Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation Acolyte
    Now With Added BA
    21 Jan '03 14:43 / 1 edit
    Suppose you have an (infinitely) long line of tiles, and you have to colour them each either red or blue. If there are enough tiles, will you always be able to find three tiles, equally spaced, that are all the same colour?

    Once you've done that, how about more colours? How about trying to find four or more equally spaced tiles all the same colour?

    Hint: for the second part, a general method will do. Don't try to spell it out tile by tile!
  2. Standard member royalchicken
    CHAOS GHOST!!!
    21 Jan '03 17:22


    Once you've done that, how about more colours? How about trying to find four or more equally spaced tiles all the same colour?

    Isn't this just equivalent to saying that given sets S1, S2, S3...Sk, such that:

    S1 U S2 U S3 U ... U Sk = N (the natural numbers),

    There exists some j <= k such that Sj contains an arithmetic sequence? Or did I miss something? Of course it still has to be proved...I have a couple free hours.
  3. Donation Acolyte
    Now With Added BA
    21 Jan '03 17:51
    Originally posted by royalchicken
    Isn't this just equivalent to saying that given sets S1, S2, S3...Sk, such that:

    S1 U S2 U S3 U ... U Sk = N (the natural numbers),

    There exists some j <= k such that Sj contains an arithmetic sequence? Or did I miss something? Of course it still has to be proved...I have a couple free hours.
    Well... the sets are disjoint (though I suppose that's not important, come to think of it) and you're not looking for an infinite arithmetic progression, just one of some length x. I phrased it in non-mathematical terms as I don't usually like setting puzzles that look like part of a Maths exam. If you find the question too easy, consider this: say you only consider {1,2,...,N}. How big does N have to be to guarantee that this set contains the relevant progression, for various values of x and k?
  4. Standard member royalchicken
    CHAOS GHOST!!!
    21 Jan '03 18:05
    That was a quite clever way of phrasing it. I am working on proving it as we speak.
  5. Standard member royalchicken
    CHAOS GHOST!!!
    24 Jan '03 20:57
    Hmm. How to rephrase the question?

    What about saying that given two positive integers, p,m, there must exist a constant q(p,m) such that for all n&gt;=q(p,m), if {1,2,3,...,n} ( S1 U S2 U Sm, then one S contains an arithmetic sequence of length p? This can fairly easily be proved by induction on p and m.