Results 1 to 2 of 2

Math Help - Partitions and sets

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Partitions and sets

    a) what is the smallest number of integers that must be selected from {1,2....,30} in order to guarantee that the selection contains five numbers X1, X2,.....,X5 such that 3| < (Xi-Xj), 1<= i, j<= 5? (prove the answer)

    b) Generalize the statement in (a): given positive integers n,k and t, such that n>=tk, what is the smallest number of integers that must be selected from {1,2,...,n} in order to guarantee that the selection contains t numbers X1, X2, .....,Xt such that k|
    (Xi-Xj), 1<= i, j<= t? (no proof needed)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    For (a)

    \mathbb{Z}/3\mathbb{Z} contains 3 equivalence-classes. If we have 2 numbers x,y such that 3|x-y that is x-y\equiv 0 mod 3.

    Hence by the pigeon-hole principle we must choose 3\cdot 4 + 1 numbers from \left\{1,\cdots, 30\right\} such that at least 5 of these numbers are in the same residu-class modulo 3.

    For (b) that must be t(k-1)+1 since \mathbb{Z}/k\mathbb{Z} contains k residu-classes.

    Or did I misunderstand your question perhaps?
    Last edited by Dinkydoe; January 24th 2010 at 12:18 PM. Reason: "spelling error ;p "
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partitions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: October 4th 2010, 03:40 AM
  2. more partitions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 15th 2010, 05:28 PM
  3. partitions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 04:53 PM
  4. set partitions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 11:06 AM
  5. partitions of sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 8th 2008, 06:02 PM

Search Tags


/mathhelpforum @mathhelpforum