Results 1 to 5 of 5

Math Help - Pattern

  1. #1
    Junior Member
    Joined
    Apr 2005
    Posts
    26

    Pattern

    Show that if 14 distinct integers are chosen from the sequence 100,101,102,103,...,123,124, there must be two of them whose difference is four.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25

    Inelegant demonstration

    Quote Originally Posted by mathsmad
    Show that if 14 distinct integers are chosen from the sequence 100,101,102,103,...,123,124, there must be two of them whose difference is four.
    I'm kind of ignorant with formal proofs and the relevant language. Therefore, I'm arbitrarily going to call any selection of 13 numbers from the above set where none of the selections have a difference of four with any other selection a "Lamp Set". (Yes, I just glanced around for a random word to use.)

    Start by grouping the numbers in sets of 4:

    100,101,102,103
    104,105,106,107
    108,109,110,111
    112,113,114,115
    116,117,118,119
    120,121,122,123
    124

    A simple starting selection process is to select all numbers in the odd rows. This gives us a Lamp Set. Let's look at the pattern of our selections (1 means selected, 0 means not):

    1111
    0000
    1111
    0000
    1111
    0000
    1

    In a Lamp Set, we must not select two numbers vertically adjacent to each other. To modify the selections while maintaining a Lamp Set, we can flip all the selections in any of columns 2, 3 and 4:

    Columns 2 and 4 flipped:

    1010
    0101
    1010
    0101
    1010
    0101
    1

    Columns 2, 3 and 4 flipped:

    1000
    0111
    1000
    0111
    1000
    0111
    1

    Column one can't be flipped, because that would only leave us 12 numbers selected:

    0000
    1111
    0000
    1111
    0000
    1111
    0

    All possible Lamp Sets can be produced by choosing to flip or not three times. Therefore, there are only 2^3 = 8 possible Lamp Sets.

    Now, there are no Lamp Sets where a 14th selection can be made without it being vertically adjacent to one of the Lamp Set selections, and thus having a difference of four with that selection. Since a 14-member selection set with no two selections having a difference of four can be found, 14 selections made from the source set must always include at least two selections with a difference of 4.

    I'm not really used to proofs yet, so while there's probably a more elegant way to show this, the above is sufficient.
    Last edited by wil; May 27th 2005 at 04:20 AM. Reason: add a title
    Follow Math Help Forum on Facebook and Google+

  3. #3
    hpe
    hpe is offline
    Member hpe's Avatar
    Joined
    Apr 2005
    Posts
    158
    Quote Originally Posted by mathsmad
    Show that if 14 distinct integers are chosen from the sequence 100,101,102,103,...,123,124, there must be two of them whose difference is four.
    We can subtract 100 from each integer and thus assume that the 14 integers are chosen from the set {0,1,2,...,23,24}. Call the set of 14 integers S. Then S is the union of four sets:

    <br />
S_0 = S \cap\{0,4,8,12,16,20,24\}<br />
    <br />
S_1 =  S \cap \{1,5,9,13,17,21\}<br />
    <br />
S_2 = S\cap\{2,6,10,14,18,22\}<br />
    <br />
S_3 = S \cap \{3,7,11,15,19,23\}<br />

    That is, S0 is the subset of integers in S that are divisible by 4, S1 is the subset that has a remainder equal to 1 when divided by 4, and so on. The union of these sets is S, and any two of these sets have an empty intersection.

    Suppose now that the assertion is false. Then no two integers in S and no two elements of S0, S1, S2, S3 have a difference of 4. Thus S0 can have at most 4 elements (since otherwise there would be two numbers in S0 with a difference of 4), and S1, S2, S3 can each have at most 3 elements, for the same reason. Put together,
    <br />
S = S_0 \cup S_1 \cup S_2 \cup S_3<br />
    can have no more than 4+3+3+3 elements, contradicting the assumption that S has 14 elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25

    yeah!

    that was my next guess...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2005
    Posts
    26

    Cool Thanks for the help

    Thanks for the help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pattern
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: February 8th 2010, 07:23 AM
  2. what is the pattern?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: April 18th 2009, 03:39 PM
  3. pattern
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 15th 2009, 08:27 AM
  4. a pattern, plz help
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: April 10th 2008, 05:04 AM
  5. Pattern
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 18th 2005, 08:54 PM

Search Tags


/mathhelpforum @mathhelpforum