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


厦门 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.