Tends to infinity

Only maths… nothing else

  • Recent Posts

  • Categories

  • Top Posts

  • My previous writings

  • February 2011
    M T W T F S S
    « Jan   Mar »
     123456
    78910111213
    14151617181920
    21222324252627
    28  
  • Enter your email address to follow this blog and receive notifications of new posts by email.

    Join 8 other followers

  • you are

    • 1,234 th visitors on this page

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 2^{n+1}-1 can  be obtained by adding all or some of the element of the set  {1=20,21,22,23,…2n}    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 =24-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 {20=1, 2, 4, 8=23} 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  25-1<40<26-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 3n(n is a natural no.). If the natural number is a power of 3(of the form 3n) the prove is obvious. Now for the other case see the following example

(4)10=(11)3=(11)3-03 = 31+30

(5)10= (12)3

= 1.31+2.30

= 1.3+(3-1)30

= 1.3+3-1

=2.3-1

=(3-1)3-1

=32-31-30

= (100)3-(10)3-10

I hope you can generalize the facts.

So every natural number upto  \frac{3^{n+1}-1}{2}can be expressed by adding or subtracting all or some elements of the set {1=30,31,32,…3n}

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 = 41+40

6 = 4+1+1 (1 =40)

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.

Advertisements

3 Responses to “salesman problem”

  1. 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.

  2. anmishra said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: