## salesman problem

Posted by tendstoinfinity on February 10, 2011

pichak@scientist.com

Perhaps you have remembered Dr. A N Mishra, KV Jorhat one of the teachers blessed with splendid presence of mind. He has asked me a very beautiful question.

*One salesman used to carry 40 different weights 1kg,2kg,….40kg for weighing articles upto 40kgs, until somebody suggested why doesn’t he use less number of weights so that he can weigh all the kgs upto 40kg in one turn. Now can you help the salesman to choose minimum number of weights in the following cases*

* i. **weights can be placed on either of the pans of the balance.(this is Dr. Mishra’s question)*

* ii. **weights can be placed only on left pan and object on right pan.( this is my variation)*

before presenting the solutions directlyI want to see the Result: *All the naturals up to * *can be obtained by adding all or some of the element of the set {1=2 ^{0},2^{1},2^{2},2^{3},…2^{n}} only once. (Why?) *For example by adding some or all of the set only once you can get all naturals upto 7 using all or some {1,2,4}. You can see following table for illustaration

No of 4 | No of 2 | No of 1 | sum |

0 | 0 | 1 | 1 |

0 | 1 | 0 | 2 |

0 | 1 | 1 | 3 |

1 | 0 | 0 | 4 |

*1 | 0 | 1 | 5* |

#1 | 1 | 0 | 6 |

1 | 1 | 1 | 7 |

Are you able to see that in the above table (*no of 4,no of 2 and no of 1)* form the binary ( number system of base 2)representation of the respective sum. *Just as (101)_{2} =(5)_{10} . Now binary representation of 8 to 15 =2^{4}-1 contains 4digits. So the sum of any natural number from 1 to 15 can be represented as a sum of all or some of {2^{0}=1, 2, 4, 8=2^{3}} only once. I think my variation i.e (ii) can now be solved. Because you can only use one pan to place weights so addition only should be used so 6 weights of {1,2,4,8,16,32} will be necessary for 2^{5}-1<40<2^{6}-1. In fact the salesman can weigh any weights upto 61kg in one turn using these weights.

Another approach of thinking

There are two places for the weight units either in the balance pan or in bag of salesman. Let 0 represents the bag and 1 represents pan so weighing a weight of 6kg we have representation 110# means 4kg, 2kg on the pan and 1 kg in the bag.

Before we turn to Dr. Mishra’s problem we want to see the a wonderful property of ternary system(number system of base 3) : every natural can be represented as the sum or difference of two numbers whose ternary representation contain only 0’s and 1’s or otherwise every natural can be expressed as the sum or differences of numbers of the form 3^{n}(n is a natural no.). If the natural number is a power of 3(of the form 3^{n}) the prove is obvious. Now for the other case see the following example

(4)_{10}=(11)_{3}=(11)_{3}-0_{3} = 3^{1}+3^{0}

(5)_{10}= (12)_{3}

= 1.3^{1}+2.3^{0}

= 1.3+(3-1)3^{0}

= 1.3+3-1

=2.3-1

=(3-1)3-1

=3^{2}-3^{1}-3^{0}

= (100)_{3}-(10)_{3}-1_{0}

I hope you can generalize the facts.

So every natural number upto can be expressed by adding or subtracting all or some elements of the set {1=3^{0},3^{1},3^{2},…3^{n}}

So every number less than 40 can be expressed as sum or difference of all or some of {1,3,9,27}. These are weights required by the salesman.

For base 4, Similarly every natural number can be expressed by sum or difference of the powers of 4 taking any specific element not more than twice.

5 = 4^{1}+4^{0}

6 = 4+1+1 (1 =4^{0})

7 = 16 – 4 – 4 – 1

53 = 64 – 16 + 4 +1

Its proof is so simple. But giving a little time you can prove it.

Hopefully in some post I will discuss some more interesting fact of the bases of number system.

## a n mishra said

(1) maine to sajde me bus jal chadhaye the, aabe hayat aapne usko bana diya.

(2) pinaki se man kya mila roshan mijaaj ho gaya, aaj jana math ki jadugari kya cheej hai.

## tendstoinfinity said

kya shayari ki aapne! aapko main kya samjha paya? I want more mathematical comments.

## anmishra said

Prima facie the solution is appropriate.Mathematically I’ll dare later.

anm