Skip to main content

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

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?