Results 1 to 4 of 4

Math Help - Number array

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Number array

    Consider I have the following rectangular array:

    0 0 0 0
    1 1 1 1
    2 2 2 2
    3 3 3 3
    4 4 4 4....


    Suppose I have to choose one number from each column. I then have to take the sum of the numbers and then divide it by 5 and take the remainder.

    Prove that:

    a.) the number of combinations that yield a remainder of 0, equals the number of of combinations that yield a remainder of 1, equals the number of combinations that yield a remainder of 2.... etc.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Use combinations?

    0000 0001 0002 0003 0004
    0014 0010 0011 0012 0013
    0023 0024 0020 0021 0022
    0032 0033 0034 0030 0031
    ....
    0104 0100 0101 0102 0103
    etc ...

    do you see what's going on? I set it up so that each column has the same remainder ... I guess you could use set congruences.
    \{a, a+1, a+2, a+3, a+4\} \equiv \{0,1,2,3,4\} \ (mod \ 5). I'm not too sure how to prove this formally, but it's pretty obvious .... like if a \equiv 3 \ (mod \ 5), then the set becomes {3,4,5,6,7} = {3,4,0,1,2} (mod 5).

    So, if you let a be the sum of the first 3 numbers (from the first 3 columns), then you're left with a, a+1, a+2, a+3, a+4. This is true for all a, and you'll see that the remainder of 5 happens only once in each case. Also, there's a possible 5^3 = 125 combinations for the summation of the first 3 columns ... so each remainder occurs 125 times ....

    This is really messy, but I hope it helps get you started
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    I'm still stuck, could you finish it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    I don't know how ... it seems pretty finished in my head, and I'm not too sure how to make a formal proof out of it .

    You could try this:

    Let b be a sum of the any numbers in the first three columns of the rectangular array.

    b+0, b+1, b+2, b+3, b+4 are the possible sums for all four columns.

    Since for any integer a, \{a, a+1, a+2, a+3, a+4\} \equiv \{0,1,2,3,4\} \ (mod \ 5), this means that from the set \{b+0, b+1, b+2, b+3, b+4\}, one of the sums will have a remainder of zero, another remainder 1, another remainder 2, etc.

    So, for any combination from the first 3 columns, when we add 0, 1, 2, 3, and 4 to it, then divide it by 5, each possible remainder (0,1,2,3, or 4) occurs only once.

    This implies that when we consider all the combinations, the number of combinations that yield a remainder of zero, is the same as that which yields a remainder of 1, 2, 3, and 4.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate and array
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 21st 2011, 03:34 AM
  2. Array Help
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: January 31st 2011, 06:42 AM
  3. array help
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: October 12th 2008, 04:42 PM
  4. array
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: October 8th 2008, 12:43 PM
  5. Array of Numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 24th 2006, 07:33 PM

Search Tags


/mathhelpforum @mathhelpforum