Two maths lovers Parth and Pranjal competed each other for the number of problems solved correctly in 3 0 0 days streak at Brilliant.
Let a i be the number of problems solved by Parth on the i t h day.
Let b i be the number of problems solved by Pranjal on the i t h day.
Note: 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 3 0 0 and b 1 , b 2 , … b 3 0 0 are non-decreasing . The competition was tough , and Pranjal won by 1 problem.
If i = 1 ∑ 3 0 0 a i = 1 7 2 9 , i = 1 ∑ 3 0 0 b i = 1 7 3 0 ,
What is the minimum value of 3 0 i = 1 ∑ 3 0 0 a i b i ?
Note: 1 7 2 9 (taxicab number) , 1 7 3 0 are two consecutive sphenic numbers.
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.
For your bound 3 0 M ≥ 2 9 9 1 1 7 , equality occurs if and only if a i = 1 7 2 9 / 3 0 0 and b i = 1 7 3 0 / 3 0 0 for all i . But in the way you have set up the problem, a i and b i must be nonnegative integers, so equality cannot occur.
The name of the inequality is perhaps Chebyshev's Inequality?
I solved this question using Chebyshev's Inequality.
Congrats on 300 followers landmark!!
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. :)
I must brag!!! @Parth Lohomi I beat you! Better luck next time. That was a close fight. Huh! Anyways thanks @Nihar Mahajan ⌣ ¨
Log in to reply
Welcome! BTW can you add this question to the Chebyshev Inequality wiki?
Log in to reply
You just have to add the skill to problem for it. I have moved this to Chebyshev application skill.
It seems just like the Rearrangement Inequality . By the way, congrats on 300 followers! I'm stuck on merely 35...
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'?
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.
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!
Would it be possible to apply the Rearrangement Inequality here in this case? Thanks very much!
Thanks a lot!
Congrats on achieving 500 followers... Well this one can even be solved by classic A . M . − G . M .
Log in to reply
Notreally. Since this inequality is not known to many people, can't help. 😐
Log in to reply
Which lvl did you into initially set ?😓😓
Log in to reply
@Harsh Shrivastava – I dont remember exactly. But i am sure that i had not set level 5.
Since a i ∈ R and b i ∈ R , Least possible value for each person would be when the number of sums done is equally distributed amongst the 300 days. 3 0 i = 1 ∑ 3 0 0 a i b i = ( 3 0 0 1 7 2 9 × 3 0 0 1 7 3 0 ) × 3 0 0 × 3 0 = 2 9 9 1 1 7
Problem Loading...
Note Loading...
Set Loading...
This is a straight forward application of Chebyshev's inequality:
If a 1 ≤ a 2 ≤ ⋯ ≤ a n , b 1 ≤ b 2 ≤ ⋯ ≤ b n ,
n i = 1 ∑ n a i b i ≥ ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ n i = 1 ∑ n a i ⎠ ⎟ ⎟ ⎟ ⎟ ⎞ ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ n i = 1 ∑ n b i ⎠ ⎟ ⎟ ⎟ ⎟ ⎞
Thus substituting the given information ,
3 0 0 i = 1 ∑ n a i b i ≥ ( 3 0 0 1 7 2 9 ) ( 3 0 0 1 7 3 0 )
i = 1 ∑ n a i b i ≥ ( 3 0 0 1 7 2 9 × 1 7 3 0 )
i = 1 ∑ n a i b i ≥ ( 3 0 2 9 9 1 1 7 )
M = ( 3 0 2 9 9 1 1 7 )
⇒ 3 0 M = 2 9 9 1 1 7 :)