COMBINATIONS 1Dec94 dp-j 3PM
The weighing scale problem posed by Graham Gallagher in Issue 38 prompted some
thoughts on the subject of combinations. So for those amongst us with an
interest in things mathematical, here goes, but first I must apologise for the
lack of scientific notation fonts. This makes presentation of even simple
algebra somewhat clumsy so if anyone has a ROM/ROM image which eases the
communication problem please tell us about it. However I do get back to the
weights problem after exploring the logic behind the magic 40 lb. But wait....
there is another fiendish aspect to this devilish escapade dear Watson.
Consider n unlike terms having +ve or -ve values. (I will use +-a,+-b,+-c,+-d
as an example. ie. having n=4, throughout this discourse.)
If we now take all these n terms and write them down n at a time with all
possible combinations of sign we will get a total of 2^n combinations. (In the
example there are 2^4=16 combinations such as a+b+c+d, -a+b-c+d, etc etc)
Suppose we now take any r terms of a set of n terms. The number of
combinations,nCr, of n terms taken r at a time is given by :-
nCr = n!/(r!*(n-r)!) where n! means factorial n
(If n=4 and r=3 then nCr is 4*3*2/(3*2)*(1)=4. viz. a,b,c a,b,d a,c,d & b,c,d.)
Now if each of the terms of these combinations can be +ve or -ve we can see
from the foregoing that there will be :-
(n!/(r!*(n-r)!)) * 2^r combinations in total.
ie. there are 4*2^3=24 combinations of any group of 3 selected from the 4 +ve
or-ve terms. We could similarly find the number of combinations taken 2 at a
time and 1 at a time and arrive at an overall total for all the possible
combinations, nCr=1_n, where nCr=1_n is shorthand for 'the no. of combinations
of n terms taken r at a time for all values of r from 1 to n.'
If we take this last equation and perform the summation from r=1 to r=n then
a little manipulation of the factorials yields:-
nCr=1_n = 2*n + n(n-1)*2^n/2! + n(n-1)(n-2)*2^3/3! +......
(Sorry for the mix of algebraic and BBC notation if one *ts to see *s.)
For the example, n=4, this gives:-
nCr=1_n = 2*4 + 4*3*4/2 + 4*3*2*8/(3*2) + 4*3*2*16/(4*3*2) + ...
= 8 + 24 + 32 + 16 = 80
I hesitate to refer to the above as an 'equation' because although it looks
like a straight forward series, which it is, when substituting a value for n,
only the first n terms of the series are valid and the rest ignored. So in the
case of n=4 above, only the first 4 terms are valid, the last term of course
having the value 2^n (=16 in this case). If I had the facility to write the
original summation of nCr in proper algebraic symbols it would be immediately
clear why we stop at the n th term.
Anyway the equation tells us that we can generate 80 combinations in all from
+-a,+-b,+-c,+-d taking 4 terms at a time down through 1 at a time. If we
assign actual numerical values to a,b,c & d and perform all the 80 sums this
does not necessarily result in 80 different results. Some of them may be
numerically the same, but whatever numbers are chosen it should be obvious that
there will be 40 +ve and 40 -ve answers. Also it is conceivable that there may
be particular values of a,b,c,d such that the 40 combinations which give +ve
results may happen to yield 1,2,3,4,.......38,39,40.
And here we are back to the weighing problem. 4 weights defined as -ve when
placed on the provisions pan and +ve when on the balance pan and having a
combined weight....yes, you've guessed it, 40lb, and provide every increment.
OK, OK... but what are they?. Well, I don't have a formula which tells me how
many possible combinations of 4 weights add up to 40, but the little Basic
program "Combi" shows me what they are, and tells me there are 297 to choose
from. Interesting perhaps but not much use, is it? And has it got 'em all?
Well you can apply various rationale a la Mr. Gallagher (Issue 39) but suppose
you were told there were seven weights totalling 1093 lb?. nCr=1_n says it may
be possible but I suspect Mr. Gallagher can get the answer in say under one
minute, to err on the generous side, as you will see later.
To write a progam to find the solution to this general problem by brute force
more or less, is an interesting, but not difficult challenge. Unfortunately
there's no need to bother. If you just happen to know about a particular
series,eh? Watson, you need neither rationale nor combinations. (My rationale
tells me to hang on to the latter just now. Brrr.)
You know how the binary number system works on the Beeb whereby combining bit
values in an 8_bit byte can produce every integer from 1 to 255 ? Well these
are really the terms of a geometric progression 1,g,g^2,g^3,g^4,......where g=2
and if we select the terms 1 at a time, 2 at a time,... etc we get all the
integers 1 to 255 or whatever by addition of the respective terms.
If we now make g=3, ie the trinary number sequence, and let a=1, b=g, c=g^2,
d=g^3,........etc and this time select the terms +-a,+-b,+-c,...... etc 1 at a
time, 2 at a time,... etc we again find that all the integers from 1 to
whatever are generated when added algebraically.
But whereas the combinations of the first four terms of the binary series yield
1 to 15, those of the trinary sequence yield 1 to 40. So the answer to our
weights problem is:-
1, 3, 3^2, 3^3 or 1,3,9,27 (=40)
Had the original weighing problem asked for say 6 weights to weigh from 1 to 63
lbs one would have immediately connected the answer with the binary series;
1+2+4+8+16+32 then 2 at a time; (1+2),(1+4),...(2+4),...etc. then 3 at a time;
(1+2+4).....etc etc. to give all the increments up to 63.
Mr. Gallaghers version relies on the combinations of the trinary sequence being
less well known. So all you have to do to solve the 7 weight problem I posed
earlier is add the next three terms in the series viz. 3^4,3^5 & 3^6 to give:-
1,3,9,27,81,243,729 (=1093)
Like the question "How many beans make 5?" you either know the answer or you
don't, and if you don't it could take rather a long time"...Yes, I heard. No, I
have not actually proved that the trinary sequence can be made to generate
every integer, but then nobody actually proved to me that the binary series
would.
In conclusion, armed with the binary and trinary sequences you can pose quite a
number of weighing problems. But take care, posing can seriously damage your
balance.