Consider you have x stones each a power of 2. There is an interesting property - the largest out of these will always be greater than the sum of all the rest of the weights. This implies the pan which has the largest power of 2 weight will always be heavy even if you put all the other weights on the opposite pan.
This means if I pick a subset of these weights, I am solving nothing but the smaller version of this problem. With these insights, we can continue to the solution.
Solution:
Let the number of ways for this problem be f(n).
Consider the weight with the largest power of 2. For the left pan to be always heavier than the right pan, you need to put this weight on the left pan at some point of time. There arise two cases:
1. I put the largest weight on the left pan at the first turn. Number of ways in which this can happen is = (n-1)! * 2^(n-1)
2. I put the largest weight at some other point of time. But this puts a constraint on the sequence of weights that I put before the largest weight - they have to satisfy the constraint of the problem. But from the insight above, I am basically solving a smaller version of the problem. So say I pick any x weights from the remaining (n-1) weights. I calculate f(x). This gives me the number of ways to put these x weights on the pans such that the left pan is always heavier at each point of time. Then I put the largest weight on the left pan. Now I don't care what I put where because the largest weight makes the left pan heavier always from this point of time and onwards. So number of ways I satisfy the constraints of the problem given I pick 'x' weights before the largest weight = ((n-1) choose x) * f(x) * (n-1-x)! * 2^(n-1-x)
Sum these up from x=1 to x=n-1
So
f(n) = (n-1)! * 2^(n-1) + Summation ( ((n-1) choose x) * f(x) * (n-1-x)! * 2^(n-1-x) ) where x ranges from x = 1 to x = n-1
f(n-1) = (n-2)! * 2^(n-2) + Summation ( ((n-2) choose x) * f(x) * (n-2-x)! * 2^(n-2-x) ) where x ranges from x = 1 to x = n - 2
Thanks PuzzledQuant. I have a suggestion though. Could we enable latex like commands to write math expressions and equations in the comment section as well as in the author's solution? It improves readability. Commentors can easily express as well as the author's solution also becomes more readable.
A different elegant approach:
Important insight:
Consider you have x stones each a power of 2. There is an interesting property - the largest out of these will always be greater than the sum of all the rest of the weights. This implies the pan which has the largest power of 2 weight will always be heavy even if you put all the other weights on the opposite pan.
This means if I pick a subset of these weights, I am solving nothing but the smaller version of this problem. With these insights, we can continue to the solution.
Solution:
Let the number of ways for this problem be f(n).
Consider the weight with the largest power of 2. For the left pan to be always heavier than the right pan, you need to put this weight on the left pan at some point of time. There arise two cases:
1. I put the largest weight on the left pan at the first turn. Number of ways in which this can happen is = (n-1)! * 2^(n-1)
2. I put the largest weight at some other point of time. But this puts a constraint on the sequence of weights that I put before the largest weight - they have to satisfy the constraint of the problem. But from the insight above, I am basically solving a smaller version of the problem. So say I pick any x weights from the remaining (n-1) weights. I calculate f(x). This gives me the number of ways to put these x weights on the pans such that the left pan is always heavier at each point of time. Then I put the largest weight on the left pan. Now I don't care what I put where because the largest weight makes the left pan heavier always from this point of time and onwards. So number of ways I satisfy the constraints of the problem given I pick 'x' weights before the largest weight = ((n-1) choose x) * f(x) * (n-1-x)! * 2^(n-1-x)
Sum these up from x=1 to x=n-1
So
f(n) = (n-1)! * 2^(n-1) + Summation ( ((n-1) choose x) * f(x) * (n-1-x)! * 2^(n-1-x) ) where x ranges from x = 1 to x = n-1
f(n-1) = (n-2)! * 2^(n-2) + Summation ( ((n-2) choose x) * f(x) * (n-2-x)! * 2^(n-2-x) ) where x ranges from x = 1 to x = n - 2
Using the two equations above:
f(n) = (n-1)! * 2^(n-1) + f(n-1) + 2*(n-1) * ( f(n-1) - (n-2)! * 2^(n-2) )
f(n) = (2n - 1) * f(n-1)
For the base case, f(1) = 1, as there is only 1 way to make the left pan heavier always.
This gives us f(n) = (2n-1) * (2n-3) * (2n-5) * ... 3 * 1
Very insightful
Thanks PuzzledQuant. I have a suggestion though. Could we enable latex like commands to write math expressions and equations in the comment section as well as in the author's solution? It improves readability. Commentors can easily express as well as the author's solution also becomes more readable.
Jane street 😮💨😮💨