Number array

Printable View

October 20th 2009, 12:58 AM
usagi_killer

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.
October 20th 2009, 07:13 AM
Bingk

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 :)
October 22nd 2009, 07:52 PM
usagi_killer

I'm still stuck, could you finish it?
October 24th 2009, 01:50 AM
Bingk

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.