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

Home > Numbers
divisible by 11? (Posted on 2006-09-04) Difficulty: 3 of 5
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.)
Hints/Tips 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             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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information