All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 divisible by 11? (Posted on 2006-09-04)
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.

 No Solution Yet Submitted by Bon Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 almost solution | Comment 6 of 17 |

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             34             56             710            1112            1316            1718            1922            2328            2930            3136            3740            4142            4346            4752            5358            5960            6166            6770            7172            7378            7982            8388            8996            97100           101102           103106           107108           109112           113126           127130           131136           137138           139148           149150           151156           157162           163166           167172           173178           179180           181190           191192           193196           197198           199210           211`

 Posted by Charlie on 2006-09-04 12:53:59

 Search: Search body:
Forums (0)