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!
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!
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.
ReplyDeleteSo 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 :)
Pressing B decreases your total count by 1
ReplyDeleteSince 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.
hi sid.
ReplyDeleteI 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.)
@jim: ur correct, my bad. This clears a lot.
ReplyDeleteA 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.
One technique for getting large numbers is the following :
ReplyDeleteSuppose 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.
Soln by Naval Chopda (Senior Undergrad CSE IITB)
ReplyDeleteUsing 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!
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!
ReplyDeletehttp://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
@Siddhant.. Thanks a ton for the solution :)
ReplyDeleteAs 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