wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The Engineer Problem
        
(Message started by: Naumz on Sep 30^th, 2006, 3:48pm)

Title: The Engineer Problem
Post by Naumz on Sep 30^th, 2006, 3:48pm

I didnt really understand this problem. A friend of mine gave it to me. I'm including it in this section because I'm not sure how it is possible at all! It may be removed if it sounds illogical or something:

Hank Rearden wants to employ an engineer to work at his plant. As usual, he is willing to pay well if the candidate is competent enough. The engineer is to work for him for seven days. Rearden is willing to pay him 1/7th a bar of the highest quality Rearden Metal per day. The engineer is to get his payment of 1/7th of the bar everyday. (i.e. after 2 days, he must have 2/7th of the bar with him, after 3 days, he must have 3/7th and so on).
Now, Rearden wants the engineer to come up with a plan such that the bar of metal must have the lowest number of ‘cuts’ and the above conditions are satisfied. If the engineer is successful, he gets the job. What plan should the engineer propose?

Title: Re: The Engineer Problem
Post by SWF on Sep 30^th, 2006, 5:32pm

An equivalent problem is under the title Gold Chain (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027992672)

Title: Re: The Engineer Problem
Post by THUDandBLUNDER on Oct 1^st, 2006, 2:47am

I think he needs an optimal Golomb ruler (http://mathworld.wolfram.com/GolombRuler.html).

Title: Re: The Engineer Problem
Post by rmsgrey on Oct 1^st, 2006, 5:06pm

on 10/01/06 at 02:47:38, THUDandBLUNDER wrote:

I think he needs an optimal Golomb ruler (http://mathworld.wolfram.com/GolombRuler.html).

I don't think any kind of ruler gives a solution, though a perfect ruler would always help in locating the cut points.

Title: Re: The Engineer Problem
Post by towr on Oct 2^nd, 2006, 2:46am

on 10/01/06 at 02:47:38, THUDandBLUNDER wrote:

I think he needs an optimal Golomb ruler (http://mathworld.wolfram.com/GolombRuler.html).

He would need a perfect one, not an optimal one.

http://en.wikipedia.org/wiki/Golomb_ruler

Quote:

There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler.

Quote:

A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists

However, as you can't rearrange the parts of the ruler, whereas you can rearrange the pieces of gold bar, it's not really equivalent. [hide]Two cuts[/hide] is enough for the bar, but I don't see how you could make a Golomb ruler of order 4 that can measure 1-7. Unless you make it round.

Title: Re: The Engineer Problem
Post by Icarus on Oct 2^nd, 2006, 5:47pm

A more pendantic approach:

First of all, this is clearly a "Find an optimal solution from a finite - but non-zero - set of possibilities" problem, and as such, it always will have a solution. One of the approaches has to give a value less than or equal to all the rest.

To get rid of all fractions, measure in "sevenths of a bar" (s). Because the engineer gets paid 1s on the first day, that has to be the size of the first cut.

1 | (6 undivided)

For the second cut, we have two choices: either cut off another 1s to pay on day 2, or else cut off a 2s chunk, and have the engineer bring the 1s chunk back to trade:

1 | 1 | (5 undivided) or 1 | 2 | (4 undivided)

In the 1,1 case, we also have 2 choices the third day: either cut another 1s piece off, or else cut the 5s bar into pieces of side 2s and 3s:

1 | 1 | 1 | 4 or 1 | 1 | 2 | 3 or 1 | 2 | 4

At this stage - along all three tracks - it is no longer necessary to cut the bar any more, as all possible values can be reached.

1 | 1 | 1 | 4 : (1, 1+1, 1+1+1, 4, 4+1, 4+1+1, 4+1+1+1)
1 | 1 | 2 | 3 : (1, 2, 3, 3+1, 3+2, 3+2+1, 3+2+1+1)
1 | 2 | 4 : (1, 2, 1+2, 4, 4+1, 4+2, 4+2+1)

It should be obvious which is optimal!