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 2006-09-04 12:53:59