Magic Money Machine

Source: CMU Puzzle Toad

Problem: The wizards at Wall Street are up to it again. The Silverbags investment bank has invented the following machine. The machine consists of 6 boxes numbered 1 to 6. When you first get the machine, it contains 6 tokens, one in each box. You have two buttons A, B on the machine and you can press them as many times as you like and in any order.


Button A Choose a number i from 1 to 5 and then take one token from box i and magically two tokens will be added to box i + 1.
Button B Choose a number i from 1 to 4 and then take one token from box i and then the contents of boxes i + 1 and i + 2 will be interchanged.

The machine sells for one trillion dollars. The contract says that you can take the machine back to the bank at any time and then the bank will give you one dollar for each token in the machine. Is the machine worth buying?

Update (Nov 10, 2010):
This problem is an IMO 2010 Problem. Solution available at artofproblemsolving link
Solution posted by Siddhant Agarwal (EE Senior Undergraduate, IIT Bombay) who gave credits to Naval Chopra (CSE Senior Undergraduate, IIT Bombay) in comments!

Comments

  1. if we assume that if we press button A and i comes up, and there are no tokens in i then it does nothing. Similarly for B.

    So the argument is as follows:
    Press A button so many times that the prob of any token being at place less than 6 tends to zero. (calculate the no of times u hav to press A for getting prob<p). Now press B. Repeat the process.
    We know as trillion is a finite number we can find a p at each instance and so we can find the no of times to press A. Between every B pressing the total amount grows exponentially. So we are bound to get one trillion quickly :)

    ReplyDelete
  2. Pressing B decreases your total count by 1

    Since there is no way to go backward(you could not fill a container i unless you empty a container j such that j < i), I do not think we can form a loop and hence would end up on a much smaller number than 1 trillion.

    The best we can reach is 63.

    ReplyDelete
  3. hi sid.

    I don't really get you. If we press A so many times that the prob of any token being at place less than 6 is near zero, then nothing would happen when we press B, since B takes a token from box 1-4 (which would now have no tokens.)

    ReplyDelete
  4. @jim: ur correct, my bad. This clears a lot.

    A modified argument: We note that the 1st box can only lose tokens. So it will become zero in finite time(with prob 1). After this happens, box 2 can only lose tokens. So with the same argument it will become zero in finite time with prob 1. Going iterativly, we will lose out all the money in finite time with prob 1.

    Hence it is clear that we cannot make infinite money (with prob 1). However it might still be possible to have the expected value of a good strategy to exceed 1 trillion.

    ReplyDelete
  5. One technique for getting large numbers is the following :
    Suppose the number of tokens are a1,a2,..,a6 respectively. Initially all are 1. Suppose A_i means pressing button A and choosing number i and similarly for B_j.
    A_1 -> a1=0 , a2 = 1+2 = 3.
    A_3 -> a3=0, a4 = 3.
    // config is <0,3,0,3,1,1>
    while (a2>0) {
    B_2
    while(a3>0){
    A_3
    }
    }
    // config is <0,0,0,24,1,1>
    A_5 -> <0,0,0,24,0,3>
    while (a4>0) {
    B_4
    while(a5>0){
    A_5
    }
    }
    //config is <0,0,0,0,0,3*2^24>

    This is still less than a trillion dollars. But probably we make can do better.Probably by putting the second while construct inside the first one.

    ReplyDelete
  6. Soln by Naval Chopda (Senior Undergrad CSE IITB)

    Using Varun's arg we can get:
    <0,3,0,3,1,1>
    then <0,1,0,12,1,1>
    then <0,0,12,0,1,1>
    then <0,0,11,0,2,1>
    ..
    then<0,0,1,0,2^11,1>
    then<0,0,0,2^11,0,1>
    then<0,0,0,(2^11)-1,0,2>
    ...
    and finally
    <0,0,0,0,0,2^(2^11)>

    I am definitely buying that machine!

    ReplyDelete
  7. I just realized that this is problem 5 in IMO 2010. The original problem asks whether u can get 2010^(2010^2010) money from the machine and the great thing is u can!

    http://www.artofproblemsolving.com/Wiki/index.php/2010_IMO_Problems/Problem_5

    It seems that the maximum amount that u can get from the machine is amazingly large. we'll have to employ knuth's notation to write it down

    ReplyDelete
  8. @Siddhant.. Thanks a ton for the solution :)

    As pointed out by Siddhant, this is an IMO 2010 Problem, solution can be found here: http://www.artofproblemsolving.com/Wiki/index.php/2010_IMO_Problems/Problem_5

    ReplyDelete

Post a Comment