Question:
Vertu, the clever businessman, sells the ropes to his customers at the rate of 1 rupee per meter. He can only sell an integer length of a rope to a customer. Also, he has a magic locker which functions this way:
Suppose the locker has ‘x’ rupees. Now if ‘y’ rupees more are put into this locker, it multiplies them and total money in the locker now is ‘x*y’.
This morning, Vertu starts his business with ’n’ meters of rope. He puts 1 rupee in the locker as to have good luck.
Find the maximum money he can earn today considering that he sold all of his rope at the end of the day.
NOTE: Vertu has to put all rupees into the locker as soon as he gets it, and can get rupees from locker only at the end of the day.
Or in simple words,
Question: Given a number K, Find the combination of numbers having sum equal to K and their Product being the largest.
For now lets find an integer N, which when multiplied K/N times(Sum: N * K/N is equal to K) produces largest product.
Lets go with a simple example, K = 10
a. 5 times Two (Sum: 2 * 5(=10), Product: 2⁵[=32])
b. 10 / 3 times Three (Sum: 3*10/3 [=10], Product: 3^(10/3) [=38.94..])
c. 2.5 times Four (Sum: 4*2.5 [=10], Product: 4^(2.5) [=32])
d. 2 times Five (Sum: 5*2 [=10], Product: 5²(=25))
Now let K = 20
a. 10 times Two (Sum: 2 * 10(=20), Product: 2¹⁰ [=1024])
b. 20 / 3 times Three (Sum: 3*20/3(=20), Product: 3^(20/3) [=1516.38..])
c. 5 times Four (Sum: 4*5(=20), Product: 4⁵ [=1024])
d. 4 times Five (Sum: 5*4(=20), Product: 5⁴ [=625])
Hopefully you might have noticed what I want to show.
From above two examples it is clear that 3^(K / 3) is the greatest of them. This in turn is true for all integral K’s.
In general,
N^(K/N) is largest when N = 3 (N and K being integers)
Lets go and prove this:
Let y = x ^ (k/x)
Taking ln on both side,
ln y = (k/x)*ln x
Now differentiate both side with respect to x
(1/y)dy/dx = k(1/x² - ln x/x²)
dy/dx = ky(1 - ln x)/x²
As we know, the function will have its maximum value when dy/dx = 0 which implies (1 - ln x) = 0 as k is a non zero integer.
or ln x= 1
which implies x = e
So at x = e, y = x ^ (1/x) has its largest value.
And thus x = 3 (being nearest integer) proved to be a winner in above discussed combinations.
Now you guys might be wondering how about having a combinations of integer, Will it never win over 3?
Alright lets see that also,
Say K = 100,
Now instead of having N = 10,
Lets write it in combinations of 7 and 3, we still will have same sum, but our product will differ now
Product = 7¹⁰ * 3¹⁰ (instead of 10¹⁰)
Now wondering if the above obtained product is greater than 3^(100/3) which is nearly equal to 3³³
We know 7¹⁰ can be written as 7^(70/7)
and from what we have proved earlier, 3^(70/3) > 7^(70/7) but still will have same sum.
Thus 3^(70/3)* 3¹⁰ > 7¹⁰ * 3¹⁰
or rather 3²³ * 3¹⁰ = 3³³ > 7¹⁰ * 3¹⁰
Thus combination of 3 will still win over other combinations.
So with this fact in mind, Go and Just give this question another try.
You surely will be able to nail it down this time!
And if you are still stuck, Here’s the solution. But first do give the question decent amount of time.
Thanks for reading! :)
