Weights on a Pan
A crazy combinatorics problem asked recently in Jane Street Interview
Toby is given a balance and n weights of weight 2, 2^2, . . . , 2^n. He has to place each of the n weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step he can choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which he can be do this task.
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
Solution
This problem has a very elegant answer !
Consider we already know the total number of ways to place n-1 weights i.e f(n-1).
For the set of n weights, if we divide the weight of each weight by 2, the answer does not change. So we divide set of n weights by 2 and get the same set of n-1 weights and weight of 1 unit.
We look at weight 1. If it is put on the scale in the first move, then it has to be placed on the left side, otherwise it can be placed either on the left or on the right side, because after the first move the difference between the weights on the left pan and the weights on the right pan is at least 2. Hence, there are exactly 2n − 1 different ways of inserting weight 1 in each of the f(n − 1) valid sequences for the n − 1 weights in order to get a valid sequence for the n weights.
Hence, we come up with the easy recursive formula which can be proved by induction as well ( Hint: f(1) = 1 )
f(n) = (2n-1) * f(n-1)
Solving it, gives f(n) = 1 * 3 * 5 * ... *(2n - 1)
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
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
Jane street 😮💨😮💨