Consecutive Triples Of Numbers

Let { a 1 , a 2 , , a 2013 } \{a_1, a_2, \cdots , a_{2013}\} be a set of 2013 2013 positive integers. Three distinct integers 1 i , j , k 2013 1 \leq i, j, k \leq 2013 are called good if a k a j = a j a i = 1. 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 } \{i, j, k\} .

Details and assumptions

  • Two good triples { i , j , k } \{i, j, k\} and { m , n , p } \{m, n, p\} are considered distinct if they differ in at least one number.

  • Yes, it's 2013 , 2013, not 2014 2014 .

  • This problem is not original.

  • A mistake in the wording has been fixed. Apologies.


The answer is 711.

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 solution

For all 1 i 3 , 1 \leq i \leq 3, let f ( i ) f(i) be the number of a i a_i 's congruent to i ( m o d 3 ) i \pmod{3} . Notice that all the numbers in a good triple are distinct modulo 3 , 3, so the total number of good triples is at most f ( 1 ) f ( 2 ) f ( 3 ) f(1)f(2)f(3) . By AM-GM, f ( 1 ) f ( 2 ) f ( 3 ) ( f ( 1 ) + f ( 2 ) + f ( 3 ) ) 3 27 = 201 3 3 27 . f(1)f(2)f(3) \leq \dfrac{(f(1)+f(2)+f(3))^3}{27} = \boxed{\dfrac{ 2013^3}{27}}. Equality holds by setting a 1 = a 2 = = a 2013 / 3 = 1 , a 2013 / 3 + 1 = a 2013 / 3 + 2 , = a 2 / 3 2013 = 2 , a_1= a_2= \cdots = a_{2013/3} = 1, a_{2013/3+1}= a_{2013/3+2}, \cdots = a_{2/3 \cdot 2013}= 2, and a 2 / 3 2013 + 1 = a 2 / 3 2013 + 2 = = a 2013 = 3. a_{2/3 \cdot 2013+1} = a_{2/3 \cdot 2013+2} = \cdots = a_{2013}= 3.

Let a 1 , a 2 , , a 2013 {a_1,a_2,\dots,a_{2013}} be a set of 2013 2013 distinct positive integers.

Doesn't that mean that all the a i a_i are distinct?

Siddhartha Srivastava - 6 years, 8 months ago

Log in to reply

Oops; fixed. Thanks! Apologies to everyone who got misled.

Sreejato Bhattacharya - 6 years, 8 months ago

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.

A Former Brilliant Member - 6 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...