A Meeting of Dragons
Dragons are meeting in a convention center for a brainstorm. The delegates have to be selected to provide the maximum efficiency of the brainstorm session. A dragon has any (integer) amount of heads, and for any N , any amount of N -headed dragons is available if needed. The problem is that the size of the convention center is limited so no more than 1 0 0 0 heads can fit into the assembly hall. The intellectual power of a dragon pack is the product of head numbers of dragons in the pack. How many dragons are there in an optimal pack of dragons at the convention center?
The answer is 334.
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.
4 solutions
Lagrange Multiplier? We can easily say that if we have a 5 headed dragon we can substitute it with a 2 -headed and a 3 -headed and get a better situation. Then from 5 on substituting a n -headed dragon with ⌊ n / 2 ⌋ 2 -headed dragons we get to a better situation. We can simply use induction! So again.. why don't we put a 4 headed dragon instead of 2 2 -headed?
Log in to reply
Your solution is intuitive, But you wont be able to make a concrete solution out of it. you need calculus for that. Tough your 2nd question is valid. even if we use a 4 headed dragon, the total intellect will be same. I guess the problem has two solutions.
Log in to reply
Won't be able to make a concrete solution you say? Ok... I thought the main Idea was enough! I will be more precise... Suppose for instance that we found an optimal pack where there is a 5 -headed dragon. If we substitute the 5 headed dragon with a 3 -headed and a 2 headed we obtain a better pack. This is a contradiction. Therefore an optimal pack won't have any 5 -headed dragon. You can manually check that up to 1 1 you can substitute dragons with less than 5 heads leaving the total unchanged but making a better pack. Now we have that 2 n is bigger than 2 n and than 2 n + 1 from n = 5 on. PLEAS DON'T MAKE ME WRITE ALL THE INDUCTION! this is the proof! Having only 3 -headed and 2 -headed we see that if an optimal pack has 3 2 -headed they can be substituted with 2 3 -headed giving a better solution. Therefore we have a contradiction again, so we can not have an optimal pack with more than 3 2 -headed. Please notice that a 4 headed can be converted into 2 2 -headed without loss of generality (up to now). No need of calculus at all! And the problem is solved.
Log in to reply
@Ariel Lanza – Good one. This solution didnn't come in my mind.
@Ariel Lanza – I didnt understand completely. You checked manually till 1 1 -why until only 1 1 ? Why not further? And secondly I also did not understand the use of proving 2 n is bigger than 2 n . Can you explain please?
Could you please show the proof by Lagrange Multiplier? I was stuck. Thanks in advance!
Log in to reply
Here is a better solution:
By Arithmetic Mean Geometric Mean inequality (or AM-GM for short) we have x 1 x 2 ⋯ x n ≤ ( n x 1 + x 2 + ⋯ + x n ) n where x 1 , x 2 ⋯ x n are the intellects of the n dragons. We know that x 1 + x 2 + ⋯ + x n = 1 0 0 0 ; therefore x 1 x 2 ⋯ x n ≤ ( n 1 0 0 0 ) n . We have an upper bound! AM-GM also states that equality occurs when x 1 = x 2 = ⋯ = x n , as desired. □ .
Should be 1001 seats to allow a unique solution.
There's no need for calculus.
A single-headed dragon is clearly a waste. Any dragon with N > 4 heads can be split into two dragons with 2 heads and N − 2 heads, respectively, for a factor of 2 ( N − 2 ) = 2 N − 4 > N to improve the solution. Thus the solution can only contain dragons with 2 , 3 or 4 heads. Dragons with 4 heads can be equivalently replaced by two dragons with 2 heads each, so the solution can be replaced by an equivalent one which contains only dragons with 2 or 3 heads. Three dragons with 2 heads each can be replaced by two dragons with 3 heads each to improve the solution. Thus the solution contains at most two dragons with 2 heads. The remainder of 1 0 0 0 modulo 3 then dictates that the solution contains exactly two dragons with 2 heads, and thus 3 3 2 dragons with 3 heads.
The solution is not unique since the two dragons with 2 heads can be equivalently merged into one dragon with 4 heads; thus, the two optimal solutions contain 3 3 3 and 3 3 4 dragons, respectively.
Absolutely beautiful. I rarely come across such a wonderful, sound proof. Bravo, Fermat!
maximize N^(1000/N).. we get N=e
use 3^332*2^2 -> 334 dragons
Why not 3^332*4^1??????
This really doesn't count as a formal proof.
Lets first write the problem mathematically. we need to maximize product(x i) where sum(x i)<=1000. i varies from 1 to n, but unfortunately n is unknown, rather that is what we need to calculate. But observe that whatever the value of n is, product(x i) will be maximum when all the x i values are equal. (This can be shown with simple application of Lagrange Multiplier and partial Derivative. I am assuming everyone can prove that. If you are stuck with this part, comment here, and I will give you the proof. )
So, the problem reduces to maximize x^n where x/n=1000. i.e. maximize x^(1000/x). Using a little calculus you can see that the answer to this problem is e (the magnificent irrational number) . So, we have two choices, either x=2, or x=3. since 2^500<3^333 [as 500 log(2)<333 log(3)], our desired solution is 3 and hence n=333
Now comes the tricky part: observe that if there are 333 3-headed dragons, the total head count is 999, and the intellect coeff is 3^333. Now instead of the last 3 headed dragon if we put 2 2-headed dragons (as there was space for 1 more head still), the total intellect coeff becomes 4 3^332. now 4 3^332>3*3^332=3^333.
Hence, the result is 334 dragons - 332 3-headed and 2 2-headed