For a natural number n, let T(n) denote the number of ways we can place n objects of weights 1,2,...,n on a balance such that the sum of the weights in each pan is the same. Prove that T(100) > T(99).
T(99) is quite large, but each solution consists of two sums of 99*100/4=2475
The sum of T(100) are 2525. This is greater by 50.
Each sum for T(99) must have the number 50 on one side. If we replace this 50 with 100 and move the 50 to the other side, we create a sum for T(100). So T(100) is at least as large as T(99).
To show T(100) is greater we just need at least sum to 2525 with 50 and 100 on the same side.
Here's one:
{1+2+...+59+61+62...+70+100}
Thus T(100)>T(99)
---------------------------------------
Of course I could have just looked it up:
https://oeis.org/A063865
99 878552973096352358805720000
100 1731024005948725016633786324
These are the total number of partitions and so a balancing will be counted twice for interchanging the entire pans.
Not surprisingly T(100) is almost twice as large as T(99) since almost half the solutions for n=100 should have 50 and 100 on the same side.
---------------------------------
Incidentally the same argument can be used to show
T(4m)>T(4m-1) except for the first case:
T(4)=T(3) because the n=3 solution (1+2=3) can be turned into the n=4 solution by swapping in the 2 with a 4 and bringing the 2 to the other side (1+4=3+2), there are no extra n=4 solutions with the 2 and 4 on the same side.
|
|
Posted by Jer
on 2021-08-20 10:38:18 |
Solutions
