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.

(In reply to re: Replace '10' by n by Richard)

Then it seems that we are asking if n+1 divides n^n-1. If this is true, then let m = n+1 and we are asking if m divides (m-1)^(m-1)-1. If m-1 is even, then (m-1)^(m-1)-1 = m*M for some M and m divides it. If m-1 is odd, then (m-1)^(m-1)-1 = m*N-2 for some N and m divides it only if m = 2.

Thus, n+1 divides n^n-1 if n =1 or n is even.

Posted by Bractals on 2006-09-04 19:43:31