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.

Where has everybody (except Richard) gone?  The problem is not solved yet.  It's my own fault of course: Mention a theorem and people will accept it obediently and move on.

Never mind Fermat found out before us: How do you solve the problem?  This amounts to proving the theorem, but as I said, it's not nasty.  With the following two hints, I give it at most the D3 that the problem is rated:

1) We know primes are rare things to have around. We have one as the modulus / divisor of the calculation. In the expression we are trying to divide, we have almost the same number, but not quite. Can you arrange it so the prime occurs there too?

2) Transform the resulting expression in a way which I am sure you have done umpteen times at school.  Think something in parentheses to a certain power.  Then think about what might or might not divide the resulting additive terms.

When you have got so far, you are not done yet, but you will see the way forward (I hope).

Posted by vswitchs on 2006-09-06 13:36:00