Monday puzzle: paying an employee in gold

In honor of Labor day, I thought I would offer the following interview brain teaser as today’s puzzle.

You have a solid gold bar, marked into 7 equal divisions as follows:

| – | – | – | – | – | – | – |

You need to pay an employee each day for one week. He charges exactly 1 piece of the gold bar per day.

You are only allowed to make 2 cuts into the bar (and this is gold so don’t even think about “folding” the bar).

How can you make the cuts to pay your worker one gold piece every day?

An answer is in the comments below, written by Scott.



Share this post:

| More

Previous post:

Next post:



  • Leipaella

    Well, you didn’t say they had to be straight cuts. So it is possible to make one cut go zic-zac and the other deals the final blow. I’m still figuring the exact way to make it have seven bits of same size.

  • AbbaGav

    Cut off a one-sized piece and pay it to him day 1.
    Cut off a two-sized piece and give it to him day 2, asking for the one piece back as change.
    Give him the one-sized piece back so his total is 3 on day 3.
    Give him the four sized piece (the leftover) on day 4, asking for the other 2 pieces as change).
    Give him the one sized piece to bring it to 5 on day 5.
    etc.

  • Anthony F.

    Easy one :)
    Divide the gold bar after the first piece and the third piece to get 3 pieces like this :
    A: | – |
    B: | – | – |
    C: | – | – | – | – |

    Now…
    Day 1 : give him A = 1
    Day 2 : give him B and ask him to give you A back = 2
    Day 3 : give him A (so he has A+B = 3)
    Day 4 : give him C and ask for A and B = 4
    Day 5 : give him A (A+C = 5)
    Day 6 : give him B and ask for A (B+C = 6)
    Day 7 : give him A so A+B+C = 7

  • Chris

    The answer is a lot simpler than that. You don’t need 7 individual pieces to do this. We need to assume that the employee keeps his gold each day rather than spending it.

  • http://dannyturner.net Daniel Turner

    Assuming the employee doesn’t use the spend the gold whilst it’s in his possession, use transactions (i.e. ask for change).

    Cut the bar into pieces of size 1/7, 2/7 and 4/7

    First day, give him the 1/7 piece. (1/7 total)
    Second day, exchange the 1/7 piece for a 2/7 piece. (2/7 total)
    Third day, give him the 1/7 piece. (3/7 total)
    Fourth day, exchange all his pieces for the 4/7 pieces. (4/7 total)
    Fifth day, give him the 1/7 piece. (5/7 total)
    Sixth day, take the 1/7 piece, give him the 2/7 piece. (6/7 total)
    Final day, give him the 1/7 piece.

  • Scott

    For simplicity, we’ll assume the bar is 7″ long. You cut the bar into 1″, 2″ and 4″ segments.

    Pay is as follows:
    Day 1: Pay employee 1″
    Day 2: Pay employee 2″, get 1″ in change
    Day 3: Pay employee 1″
    Day 4: Pay employee 4″, get 2″ and 1″ in change
    Day 5: Pay employee 1″
    Day 6: Pay employee 2″, get 1″ in change
    Day 7: Pay employee 1″

    What is interesting is that the segments the employee has appears to follow a binary progression. Let’s represent the inches an employee has by a three digit binary number. The first digit indicates his possession of the 1″ segment, the second digit, his possession of the 2″ segment, the third digit his possession of the 4″ segment. His possessions at the end of each day are:

    001
    010
    011
    100
    101
    110
    111

    Since the decimal value of each digit corresponds to the length of that segment, we can easily calculate his possession my simply taking the decimal value of the binary number. More importantly, we can generalize for any number of days, n, where n is one less than a power of two.

    If n is one less than a power of two, then the number of segments we need is log_2(n+1) and we pay according to the binary progression above.

    For example, 15 days:
    log_2(15+1) = log_2(16) = 4

    So we need 4 segments, 1″, 2″, 4″, and 8″.

    This is a pay schedule that scales well, too. Each additional segment allows us to pay more than twice as many days.

  • Scott

    Ugh. Sorry for posting the answer, SPOILERS in my post, everyone.

  • Random Nitpick

    The problem is relatively easy to solve. However, I’ll just provide a random nitpick:

    On day two you realize every scheme fails when the worker says, “Oh, I spent my gold yesterday so I can’t give change!”

  • Michael

    The obvious answer is that if we needed to pay the employee for up to 2^n days, we would only need to make at most n cuts as we can count in binary: 1,2,4, etc.

    As others have pointed out, this only works if the employee doesn’t spend his gold with somebody besides you. If the employee needs to be paid daily it is likely it is because he would spend it, although it could also be because he doesn’t trust you.

    If trust isn’t involved then you probably will not want to create a scheme of issuing 1 piece gold certificates against the 1,2 and 4 piece chunks in your vault, although it certainly could work.

    Being the technical nitpick that I am, I would also like to point out that the puzzles states that the gold bar is already “equally divided into 7 pieces”. At first I thought “divided” meant “cut” and was puzzled as to why we would need to cut the gold bar when it has already been cut. Depending on how it is divided, why might not need to “cut” the bar at all to get individual pieces. Gold is very malleable, so I’m not sure why the problem says don’t think about “folding” the bar, we could very possibly bend it along the division points depending how thick the bar is. But I’ll assume perhaps it is too thick and the divisions are merely markings showing where we could cut into equal pieces. I’ll also assume that the solution doesn’t involve melding the pieces back together at intervals so we might have more than two cuts but not at any given time.

  • http://www.franchise-info.ca michael webster

    Well, I didn’t get the answer! It always fascinates me why the solutions to some puzzles is obvious once you see it, and having seen the obvious, you cannot figure out what the difficulty was in the first place!

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Scott wrote up the solution nicely so there is not much for me to add. The division is also known as a “binary cut” because of the connection with the binary system.

    As an extension, you could similarly pay a worker for 31 days if you had a bar with 31 pieces and cut it to give pieces of length 1, 2, 4, 8, and 16 (this is 4 cuts).

  • Pingback: How to visit a museum in one hour and still see the masterpieces - Mind Your Decisions

  • Scott

    Generalized Solution for n-days.

    Any n number of days can be paid for using no more than floor(log_2(n)) + 1 cuts. Furthermore, the values of n that are one less than a power of two form “bases” on which the rest of the values for n can be determined.

    Our example, with n=7 has the following divisions:

    1,2,4

    And a pay schedule of:

    Day 1: 1
    Day 2: 2
    Day 3: 1,2
    Day 4: 4
    Day 5: 1,4
    Day 6: 2,4
    Day 7: 1,2,4

    This forms a “base”. All values of n from 8 – 14 will also use divisions of 1,2, and 4 (with corresponding remainders) and will have the exact same pay schedule as n=7 for the first seven days.

    Now we just need to figure out the pay schedule for the remaining days, and this can be done backwards.

    The last day will simply have all of the divisions. Let us use 14 as an example. According to our formula, 14 requires 4 cuts and has 7 as its base, this gives us:

    1,2,4,7

    The first 7 days of payment follow the pay schedule for 7. What about the remaining 7?

    First we recognize that, on the last day, the employee will have all the gold pieces. So we start with the last day and subtract according to our binary progression.

    Day 14: 1,2,4,7
    Day 13: 2,4,7 (Take away 1)
    Day 12: 1,4,7 (Take away 2)
    Day 11: 4,7 (Take away 1,2)
    Day 10: 1,2,7 (Take away 4)
    Day 9: 2,7 (Take away 1,4)
    Day 8: 1,7 (Take away 2, 4)

    Note: If we continued to Day 7, we’d have:

    Day 7: 7 (Take away 1,2,4).

    But we already have day 7 with our forward progression as 1,2,4. This just illustrates the fact that solutions aren’t necessarily unique.

    Generally:

    Let n = the number of days
    Let b = the largest integer <= n that is one less than a power of 2
    The number of divisions is floor(log_2(n)) + 1.
    The first cuts will be identical to those necessary to solve when n=b, with the last cut being the remaining gold.

    Days 1 – b:
    Starting with nothing, you add in accordance with the binary progression as if n=b

    Days b+1 – n
    Working backwards, and starting with all gold divisions, you subtract in accordance with the binary progression as if n=b

    Example:

    n = 26
    b = 15
    Divisions = floor(log_2(26)) + 1 = floor(4.7) + 1 = 4 + 1 = 5

    Divisions for 15:
    1,2,4,8

    Divisions for 26:
    1,2,4,8,11

    Days 1 – 15
    1: 1
    2: 2
    3: 1,2
    4: 4
    5: 1,4
    6: 2,4
    7: 1,2,4
    8: 8
    9: 1,8
    10: 2,8
    11: 1,2,8
    12: 4,8
    13: 1,4,8
    14: 2,4,8
    15: 1,2,4,8

    Days 16 – 26 (Working backwards)
    Day 26: 1,2,4,8,11
    Day 25: 2,4,8,11
    Day 24: 1,4,8,11
    Day 23: 4,8,11
    Day 22: 1,2,8,11
    Day 21: 2,8,11
    Day 20: 1,8,11
    Day 19: 8,11
    Day 18: 1,2,4,11
    Day 17: 2,4,11
    Day 16: 1,4,11

    (Note: We don't have to complete the entire reverse sequence; we can stop once we get to the Days we've already solved. This just further illustrates the existence of multiple solutions).

    I suppose the question is, is there any integer n whose payout schedule can be solved using less than floor(log_2(n)) + 1 divisions?

Previous post:

Next post:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress