I draw numbers 1 through k (k≤10) out of a hat ten times at random, replacing the numbers after drawing them. If I disregard the case where I draw "1" all ten times, explain why the number of possible sequences is divisible by 11. (Result by a calculator is insufficient because anyone can do that easily.)
Now if I change the number '10' to another integer n in the above paragraph, can I still have a similar result; i.e., the total possible number of configurations is divisible by n+1? Does this work for all integers n? If so, prove it; if not, find all integers n it works for.
Excluding the drawing of 1 each time reduces the number of possible sequences from k^10 to k^10  1. To say the latter is divisible by 11 is equivalent to saying that the former, i.e., k^10, is congruent to 1 mod 11.
Rewriting k^10 as 1*k*k*k*k*k*k*k*k*k*k, we see it starts as 1, which indeed is congruent to 1 mod 11. The congruence mod 11 will never be 0, leaving 10 possible congruences. Although I don't know a theorem to this effect, it seems as if the subset of congruences that the product cycles through, as you muliply by each succeeding k always has a number of elements equal to a factor of 10, i.e., either 2 or 5 or 10, so that after the 10th multiplication, you're back to 1, either the 2nd, 5th or 1st time.
It seems to work whenever n+1 is prime (n is 1 less than a prime). The following program tests for n = 2 to 200, reporting which values produce a situation where this works, together with n+1, to make the identification as primes easier:
FOR n = 2 TO 220
good = 1
FOR k = 1 TO n
t = 1
FOR i = 1 TO n
t = t * k MOD (n + 1)
NEXT
IF t <> 1 THEN good = 0: EXIT FOR
NEXT
IF good THEN PRINT n, n + 1
NEXT
The report is:
2 3
4 5
6 7
10 11
12 13
16 17
18 19
22 23
28 29
30 31
36 37
40 41
42 43
46 47
52 53
58 59
60 61
66 67
70 71
72 73
78 79
82 83
88 89
96 97
100 101
102 103
106 107
108 109
112 113
126 127
130 131
136 137
138 139
148 149
150 151
156 157
162 163
166 167
172 173
178 179
180 181
190 191
192 193
196 197
198 199
210 211

Posted by Charlie
on 20060904 12:53:59 