Let { a 1 , a 2 , ⋯ , a 2 0 1 3 } be a set of 2 0 1 3 positive integers. Three distinct integers 1 ≤ i , j , k ≤ 2 0 1 3 are called good if a k − a j = a j − a i = 1 . Find the last three digits of the maximum possible number of good triples { i , j , k } .
Details and assumptions
Two good triples { i , j , k } and { m , n , p } are considered distinct if they differ in at least one number.
Yes, it's 2 0 1 3 , not 2 0 1 4 .
This problem is not original.
A mistake in the wording has been fixed. Apologies.
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.
Let a 1 , a 2 , … , a 2 0 1 3 be a set of 2 0 1 3 distinct positive integers.
Doesn't that mean that all the a i are distinct?
Log in to reply
Oops; fixed. Thanks! Apologies to everyone who got misled.
Log in to reply
It is better to say in the first sentence that they form a multiset or, even better, a sequence, because the numbers are not necessarily distinct. In contrast, saying they are a set makes the readers assume that the numbers are originally distinct.
Problem Loading...
Note Loading...
Set Loading...
For all 1 ≤ i ≤ 3 , let f ( i ) be the number of a i 's congruent to i ( m o d 3 ) . Notice that all the numbers in a good triple are distinct modulo 3 , so the total number of good triples is at most f ( 1 ) f ( 2 ) f ( 3 ) . By AM-GM, f ( 1 ) f ( 2 ) f ( 3 ) ≤ 2 7 ( f ( 1 ) + f ( 2 ) + f ( 3 ) ) 3 = 2 7 2 0 1 3 3 . Equality holds by setting a 1 = a 2 = ⋯ = a 2 0 1 3 / 3 = 1 , a 2 0 1 3 / 3 + 1 = a 2 0 1 3 / 3 + 2 , ⋯ = a 2 / 3 ⋅ 2 0 1 3 = 2 , and a 2 / 3 ⋅ 2 0 1 3 + 1 = a 2 / 3 ⋅ 2 0 1 3 + 2 = ⋯ = a 2 0 1 3 = 3 .