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).
Well, if we find the actual number of ways all the way through n=100, that'll prove the proposition. It's a challenge more to my liking than that of abstractly finding the limited answer sought. So,
clc, clearvars
global n goal weights ways
for n=1:25
ways=0;
sum=(1+n)*n/2;
goal=sum/2;
if goal==floor(goal)
weights=[];
addon(1)
disp([n ways])
% fprintf('\n')
end
end
function addon(wh)
global n goal weights ways
if wh==1
st=goal;
if st>n
st=n;
end
else
st=weights(wh-1)-1;
end
for i=st:-1:1
if sum(weights)+i==goal
weights(wh)=i;
ways=ways+1;
if n==4
% disp(weights)
end
weights=weights(1:end-1);
elseif sum(weights)+i<goal
weights(wh)=i;
addon(wh+1)
weights=weights(1:end-1);
end
remain=i*(i-1)/2;
if remain<goal-sum(weights)
break
end
end
end
3 2
4 2
7 8
8 14
11 70
12 124
15 722
16 1314
19 8220
20 15272
23 99820
24 187692
The above actually formed the sets of weights and counted them as it went along. This gets time-consuming as the numbers get higher, though it does give the indication that the numbers are monotonically increasing once past n=4.
So the following program determines new numbers by adding one new (larger) weight at a time. It keeps a count in a matrix ways(m,n) where n is the total of the weights to be formed and m is the highest weight in each set counted by that number.
In fact, if expressed in mathematical notation, the design of the program could probably serve as the basis for an analytic proof, based as it is on some of the preceding values, although not directly from the one just before, but rather half the new total weight, which differs greatly from the previous half total weight.
clc, clearvars
maxn=100;
ways=zeros(maxn,(maxn+1)*maxn/2);
ways(1,1)=1; ways(2,2)=1; ways(2,3)=1;
for n=3:maxn
for i=1:n*(n-1)/2
t=i+n;
if t<=size(ways,2)
ways(n,t)=ways(n,t)+sum(ways(1:n-1,i));
end
ways(n,n)=1;
end
end
for n=3:maxn
tot=(n+1)*n/2;
goal=tot/2;
if goal==floor(goal)
disp([n sum(ways(1:n,goal))])
end
end
3 2
4 2
7 8
8 14
11 70
12 124
15 722
16 1314
19 8220
20 15272
23 99820
24 187692
27 1265204
28 2399784
31 16547220
32 31592878
35 221653776
36 425363952
39 3025553180
40 5830034720
43 41931984034
44 81072032060
47 588491482334
48 1140994231458
51 8346638665718
52 16221323177468
55 119447839104366
56 232615054822964
59 1.72266372778013e+15
60 3.36068266965503e+15
63 2.50117144608775e+16
64 4.88700132513347e+16
67 3.65301750223042e+17
68 7.14733339229024e+17
71 5.36328829958528e+18
72 1.05063310218141e+19
75 7.91107094378918e+19
76 1.55141342711179e+20
79 1.17180632686288e+21
80 2.30024121638978e+21
83 1.74226848396272e+22
84 3.42308389104891e+22
87 2.59932234752909e+23
88 5.11107966282059e+23
91 3.89008053990555e+24
92 7.65474647046678e+24
95 5.83841502019944e+25
96 1.1496359389816e+26
99 8.78552973096352e+26
100 1.73102400594873e+27
Note that all the numbers of ways are even (specifically in the ones where we can see the last digit, rather than being in scientific notation.) This is because the program counts the weights that make up half the total, and also the other half; these always are different as there is only one weight of each size; for example, two of the eight ways of totaling 14 (half of 28) when the highest weight is 7 are (5,4,3,2) and (7,6,1) and both are counted. What the question asks for, though, is 1/2 each of the values shown; of course the order of the answers was the only thing asked for, and that is not affected by showing twice the value asked for.
We have shown that T(100) > T(99), but curiosity impels us to find some exact numbers rather than the limited precision of the data given in scientific notation, so we go to vpa (variable precision arithmetic), which defaults to 32 digits of precision, but takes longer to execute (turns out over an hour, vs 2 or 3 seconds):
clc, clearvars
maxn=100;
ways=vpa(zeros(maxn,(maxn+1)*maxn/2));
ways(1,1)=1; ways(2,2)=1; ways(2,3)=1;
for n=3:maxn
for i=1:n*(n-1)/2
t=i+n;
if t<=size(ways,2)
ways(n,t)=ways(n,t)+sum(ways(1:n-1,i));
end
ways(n,n)=1;
end
end
for n=3:maxn
tot=(n+1)*n/2;
goal=tot/2;
if goal==floor(goal)
disp([n sum(ways(1:n,goal))])
end
end
[ 3, 2]
[ 4, 2]
[ 7, 8]
[ 8, 14]
[ 11, 70]
[ 12, 124]
[ 15, 722]
[ 16, 1314]
[ 19, 8220]
[ 20, 15272]
[ 23, 99820]
[ 24, 187692]
[ 27, 1265204]
[ 28, 2399784]
[ 31, 16547220]
[ 32, 31592878]
[ 35, 221653776]
[ 36, 425363952]
[ 39, 3025553180]
[ 40, 5830034720]
[ 43, 41931984034]
[ 44, 81072032060]
[ 47, 588491482334]
[ 48, 1140994231458]
[ 51, 8346638665718]
[ 52, 16221323177468]
[ 55, 119447839104366]
[ 56, 232615054822964]
[ 59, 1722663727780132]
[ 60, 3360682669655028]
[ 63, 25011714460877474]
[ 64, 48870013251334676]
[ 67, 365301750223042066]
[ 68, 714733339229024336]
[ 71, 5363288299585278800]
[ 72, 10506331021814142340]
[ 75, 79110709437891746598]
[ 76, 155141342711178904962]
[ 79, 1171806326862876802144]
[ 80, 2300241216389780443900]
[ 83, 17422684839627191647442]
[ 84, 34230838910489146400266]
[ 87, 259932234752908992679732]
[ 88, 511107966282059114105424]
[ 91, 3890080539905554395312172]
[ 92, 7654746470466776636508150]
[ 95, 58384150201994432824279356]
[ 96, 114963593898159699687805154]
[ 99, 878552973096352358805720000]
[ 100, 1731024005948725016633786324]
That's more than 1.7 octillion for n=100 vs less than 0.9 octillion for n=99.
Since the program holds the ways matrix, we can look at some of the entries to see how the numbers are allocated by the largest weight:
For n=99, total weight 4950, with 2475 on each pan:
>> ways(1:99,2475)
ans =
count of ways largest weight in each set
10 70
84713 71
22942026 72
1898669114 73
78208874667 74
1986698025435 75
35070397408102 76
464014960961466 77
4846994840269156 78
41510961732372639 79
299933051455740949 80
1869679772811162054 81
10237017604791448496 82
49958167774869388512 83
219966758441787301131 84
882846784097770629155 85
3258337768971473065530 86
11142123783115148816688 87
35534579307259890814236 88
106302285696259660026312 89
299808913141747271422180 90
800776232264737101334794 91
2033695435244343230956819 92
4928692058788631545788102 93
11435516138252008612499202 94
25475949003075967694959462 95
54639881225177226783074726 96
113095324115589788850959447 97
226409440874886269893864877 98
439276486548176179402860000 99
It's easy to verify that there are 10 sets of weights, the largest of which is 70, that add up to 2475. Since all the whole numbers through 70 add up to 2485, you just need to leave out a set of numbers that add up to 10: 10; 9, 1; 8, 2; 7, 3; 6, 4; 7, 2, 1; 6, 3, 1; 5, 4, 1; 5, 3, 2; or 4, 3, 2, 1; that's 10 sets.
The same for n=100, where the total weight is 5050 and half that is 2525:
>> ways(1:100,2525)
For n=100:
count of ways largest weight in each set
340 71
567703 72
102576901 73
6866119401 74
246826168577 75
5694779812521 76
93548411917898 77
1170562321027133 78
11696813097611912 79
96641418395212186 80
678014539020623131 81
4124770556739260403 82
22130370292630913187 83
106179651263838648021 84
460890127931298369476 85
1827769140925314390736 86
6678243379749287096090 87
22645052192743849290202 88
71713747954226118454946 89
213285791015661144139869 90
598664759736818497669028 91
1592805370296712723788408 92
4032665817711435848774154 93
9749726232547355277074600 94
22580515975428992741756313 95
50240863485371489366129253 96
107668568147817788261870815 97
222769760695786512986670780 98
445961687773439222570959178 99
865512002974362508316893162 100
And, I just realized that the number using the max weight must equal the total of all the others, as the max weight (in this case 100), must be on one side, while the other side lacks that weight and each is counted as one of the ways. Thus 865512002974362508316893162 is indeed half the total 1731024005948725016633786324, and is therefore the number for comparison in the case of T(100), while 439276486548176179402860000 is the number for comparison in the case of T(99). That' about 865.5 septillion vs 439.3 septillion.
|
|
Posted by Charlie
on 2021-08-20 11:51:12 |
Let me count the ways -- computer solution
