My 300 followers problem! (Parth and Pranjal special!)

Algebra Level 5

Two maths lovers Parth and Pranjal competed each other for the number of problems solved correctly in 300 300 days streak at Brilliant.

Let a i a_i be the number of problems solved by Parth on the i t h i^{th} day.

Let b i b_i be the number of problems solved by Pranjal on the i t h i^{th} day.

Note: a i , b i a_i , b_i can be rational numbers , since there may be some questions which both may have solved partially.

The two sequences a 1 , a 2 , . a 300 a_1 , a_2 , …. a_{300} and b 1 , b 2 , b 300 b_1 , b_2 , … b_{300} are non-decreasing . The competition was tough , and Pranjal won by 1 1 problem.

If i = 1 300 a i = 1729 , i = 1 300 b i = 1730 \displaystyle \sum_{i=1}^{300} a_i = 1729 ,\displaystyle \sum_{i=1}^{300} b_i = 1730 ,

What is the minimum value of 30 i = 1 300 a i b i \displaystyle 30 \sum_{i=1}^{300} a_i b_i ?

Note: 1729 1729 (taxicab number) , 1730 1730 are two consecutive sphenic numbers.


The answer is 299117.

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.

3 solutions

Nihar Mahajan
Mar 1, 2015

This is a straight forward application of Chebyshev's inequality:

If a 1 a 2 a n a_1 \leq a_2 \leq \dots \leq a_n , b 1 b 2 b n b_1 \leq b_2 \leq \dots \leq b_n ,

i = 1 n a i b i n ( i = 1 n a i n ) ( i = 1 n b i n ) \dfrac{\displaystyle \sum_{i=1}^n a_ib_i}{n} \geq \left(\dfrac{\displaystyle \sum_{i=1}^n a_i}{n}\right)\left(\dfrac{\displaystyle \sum_{i=1}^n b_i}{n}\right)

Thus substituting the given information ,

i = 1 n a i b i 300 ( 1729 300 ) ( 1730 300 ) \dfrac{\displaystyle \sum_{i=1}^n a_ib_i}{300} \geq \left(\dfrac{1729}{300}\right) \left(\dfrac{1730}{300}\right)

i = 1 n a i b i ( 1729 × 1730 300 ) \displaystyle \sum_{i=1}^n a_ib_i\geq \left(\dfrac{1729 \times1730}{300}\right)

i = 1 n a i b i ( 299117 30 ) \displaystyle \sum_{i=1}^n a_ib_i\geq \left(\dfrac{299117}{30}\right)

M = ( 299117 30 ) M = \left(\dfrac{299117}{30}\right)

30 M = 299117 \Rightarrow 30M = 299117 :)

For your bound 30 M 299117 30M \ge 299117 , equality occurs if and only if a i = 1729 / 300 a_i = 1729/300 and b i = 1730 / 300 b_i = 1730/300 for all i i . But in the way you have set up the problem, a i a_i and b i b_i must be nonnegative integers, so equality cannot occur.

Jon Haussmann - 6 years, 3 months ago

The name of the inequality is perhaps Chebyshev's Inequality?

I solved this question using Chebyshev's Inequality.

Congrats on 300 followers landmark!!

Harsh Shrivastava - 6 years, 3 months ago

Log in to reply

Yeah! its Chebyshev. Actually in some books its written 'Tchebychev'. Thus in order to prevent any ambiguity , I did not mention the name. :)

Nihar Mahajan - 6 years, 3 months ago

I must brag!!! @Parth Lohomi I beat you! Better luck next time. That was a close fight. Huh! Anyways thanks @Nihar Mahajan ¨ \ddot\smile

Pranjal Jain - 6 years, 3 months ago

Log in to reply

Welcome! BTW can you add this question to the Chebyshev Inequality wiki?

Nihar Mahajan - 6 years, 3 months ago

Log in to reply

You just have to add the skill to problem for it. I have moved this to Chebyshev application skill.

Pranjal Jain - 6 years, 3 months ago

Log in to reply

@Pranjal Jain Thank you very much!!

Nihar Mahajan - 6 years, 3 months ago

It seems just like the Rearrangement Inequality . By the way, congrats on 300 followers! I'm stuck on merely 35...

User 123 - 6 years, 3 months ago

Log in to reply

Just want to confirm. With reference to the aforementioned wiki, would it not mean that the minimum value would be the value of the 'Random Sum'?

User 123 - 6 years, 3 months ago

Log in to reply

You can't use rearrangement inequality in this question. At least not directly. The inequality used here is Chebyshev's inequality

Technically, what you said is correct, but since we don't know the value of the "random sum", we gain nothing.

Siddhartha Srivastava - 6 years, 3 months ago

Log in to reply

@Siddhartha Srivastava I had meant using it indirectly. I confess I do not see any possible way. Thanks very much indeed!

User 123 - 6 years, 3 months ago

Log in to reply

@User 123 In fact Chebyshev's is a repeated usage of Rearrangement (expand and check!) So you can use rearrangement, but you need to do it 300 times.

Joel Tan - 6 years, 1 month ago

Would it be possible to apply the Rearrangement Inequality here in this case? Thanks very much!

User 123 - 6 years, 3 months ago

Thanks a lot!

Nihar Mahajan - 6 years, 3 months ago

Congrats on achieving 500 followers... Well this one can even be solved by classic A . M . G . M . A.M.-G.M.

Mayank Singh - 6 years, 2 months ago

@Nihar Mahajan

Why is this a Lvl 5 question ?

Log in to reply

Notreally. Since this inequality is not known to many people, can't help. 😐

Nihar Mahajan - 6 years ago

Log in to reply

Which lvl did you into initially set ?😓😓

Harsh Shrivastava - 6 years ago

Log in to reply

@Harsh Shrivastava I dont remember exactly. But i am sure that i had not set level 5.

Nihar Mahajan - 6 years ago

Since a i R a_i \in \mathbb{R} and b i R b_i \in \mathbb{R} , Least possible value for each person would be when the number of sums done is equally distributed amongst the 300 days. 30 i = 1 300 a i b i = ( 1729 300 × 1730 300 ) × 300 × 30 30\sum_{i=1}^{300}a_ib_i =( \frac{1729}{300}\times\frac{1730}{300} )\times 300 \times 30 = 299117 = 299117

Pranav Kirsur
Mar 29, 2015

Chebyshev!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...