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.