Monday, December 18, 2006

Solution to the Shopkeeper Problem

I don't think I need to post the solution as Christophe has already solved all of them in no time.

Problem 1: One Side Only (Simple)

This is simply the numbers 2^0,2^1,2^2 ….. that is 1,2,4,8,16 ……….
So for making 1000 kg we need up to
1, 2, 4, 8, 16, 32, 64, 128, 512.


Problem 2: Both Sides (Medium)

For this answer is 3^0,3^1,3^2 …. That is 1,3,9,27,81,243,729


Problem 3: Incremental (Hard)

This is exactly a problem solved by Gray code.

Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953
A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.

Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011,
100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010,
110, 111, 101, 100}.

For this answer we need as many blocks as per Solution to Problem 1.
For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.
Now if we want to make packets of all weights from 1 to & we will do the following

001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight …
………….

Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111

2 comments:

厦门 said...

power balance
silly bandz
Raymond Weil Watches
concord papillon
rolex datejust 36mm
wedding dresses develop quality for discerning customers and Experience the comfort, free shipping.
Buy evening dresses with a price guarantee and top rated customer service.

Mohammad Shamsi said...

In the first answer, 256 is missing in the list:

1, 2, 4, 8, 16, 32, 64, 128, [256], 512.