Let a 1 = 1 and a 2 = 3 and for n > 2 a n = ( n + 1 ) a n − 1 − n a n − 2 For how many positive integers n ≤ 1 0 0 0 is a n divisible by 1 1 ?
Details and Assumptions
Computation devices are not necessary.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1!+2!+...+n!
Nice! But how you know that 1!+2!+...+10! Is divisible by 11? Did you calculate that?
Congrats. A nice insightful approach.
Great solution! ButI couldn't understand how you know that sum of k! from k=1 to 10 is divisible by 11,,, And how do you know a4 and a8 is divisible too, Did you simply calculated 10! + 9! +8!... ?
same to me
a 1 ≡ 1 ( m o d 1 1 ) a 2 ≡ 3 ( m o d 1 1 ) a 3 ≡ 4 × 3 − 3 × 1 ≡ 9 ( m o d 1 1 ) a 4 ≡ 5 × 9 − 4 × 3 ≡ 3 3 ≡ 0 ( m o d 1 1 ) a 5 ≡ − 5 × 9 ≡ − 4 5 ≡ 1 0 ( m o d 1 1 ) a 6 ≡ 7 × 1 0 ≡ 4 ( m o d 1 1 ) a 7 ≡ 8 × 4 − 7 × 1 0 ≡ − 3 8 ≡ 6 ( m o d 1 1 ) a 8 ≡ 9 × 6 − 8 × 4 ≡ 2 2 ≡ 0 ( m o d 1 1 ) a 9 ≡ − 9 × 6 ≡ 1 ( m o d 1 1 ) a 1 0 ≡ 1 1 × 1 ≡ 0 ( m o d 1 1 ) a 1 1 ≡ − 1 1 × 1 ≡ 0 ( m o d 1 1 )
The subsequent terms turn out to be divisible by 11 because both a n − 2 , a n − 1 ≡ 0 ( m o d 1 1 ) . Hence, the terms a 4 , a 8 and the terms from a 1 0 to a 1 0 0 0 are all divisible by 11 giving us a total of 9 9 3 terms.
Note: this problem is actually from the Balkan Math Olympiad (1990 I believe).
Log in to reply
No idea about that but I remember @Sreejato Bhattacharya posting a similar problem before.
Me neither..I encountered it on a book I was reading..
can't understand the solution
i = 1 ∑ n i !
good approach ... but it's very lengthy in competition exams there is no time to solve for this much .. :(
Log in to reply
Ok....
It's very easy to do modular arithmetic quickly.
Problem Loading...
Note Loading...
Set Loading...
a n = ( n + 1 ) ∗ a n − 1 − n ∗ a n − 2 -> a n − a n − 1 = n ∗ ( a n − 1 − a n − 2 )
Set V n = a n − a n − 1 , after that we have V n = n ∗ V n − 1 = n ∗ ( n − 1 ) ∗ ( n − 2 ) . . . ( n − ( n − 3 ) ) ∗ V 2 = n ! (as V 2 = 2 = 2 ∗ 1 )
So a n = n ! + a n − 1 = ∑ k = 1 n ( k ! ) for the first 10 terms, only a 4 , a 8 , a 1 0 are divisible by 11; and we also have ∑ k = 1 1 0 ( k ! ) is divisible by 11 that means for every n ≥ 1 1 we have a n = 1 1 ∗ t + ∑ k = 1 1 n ( k ! ) (where 1 1 ∗ t = ∑ k = 1 1 0 ( k ! ) ). And since all n ! ( n ≥ 1 1 ) are divisible by 11, all a n where n ≥ 1 1 are divisible 11
---> We have 993 terms which are divisible by 11