My five friends and I used to loan each other money all the time. But over the past several years we have moved apart. We don't trust PayPal, banks, or the postal service so transferring money over such great distances is extremely difficult.
Fortunately, we have discovered a set of 6 magical fax machines! While ordinary fax machines are unable to fax money, these magical fax machines can*. And like any fax machine, it is possible to retrieve the documents you put into it (including money) even while the receiving fax machine produces a copy.
But these fax machines are not perfect. Each machine can only send one fax to each other machine (so 5 faxes per machine, for 30 faxes total). These faxes can be for any amount of money, but once a fax is started it cannot be interrupted.
For example, if I have \$30 and my friend has \$40, then I can fax my money to my friend and then I will have \$30 and my friend will have \$70. If my friend fax me back, then I will have \$100 and he will have \$70, and neither of us can fax any money to each other any more.
Our years of traveling have left my 5 friends and I broke. Each of us has exactly $1 and one this special fax machine.
Working together, what is the maximum amount of money that the six of us can create?
*and there won't be any problems with the fact that all your bills are copies of each other. It's magic
Puzzle was inspired by the Magic cards Master Biomancer and Rite of Replication, and how they would interact if Master Biomancer's ability was an "enters the battlefield" trigger (which it isn't) and with Rite of Replication producing 6 copies instead of 5.
Answer
By using a brute-force program with a little tweak
I have found:
$0 \to 1, 1 \to 2, 2 \to 1, 1 \to 3, 3 \to 1, 1 \to 4, 4 \to 1, 1 \to 5, 5 \to 1, 1 \to 0, 0 \to 5, 5 \to 0, 0 \to 4, 4 \to 0, 0 \to 3, 3 \to 0, 0 \to 2, 2 \to 3, 3 \to 4, 4 \to 3, 3 \to 2, 2 \to 4, 4 \to 2, 2 \to 5, 5 \to 4, 4 \to 5, 5 \to 3, 3 \to 5, 5 \to 2, 2 \to 0$
It makes
$\$122,762$
and interestingly the each fax machine makes
$0: 35037, 1: 47, 2: 34527, 3: 15462, 4: 8439, 5: 29250$
How did I find this result?
Simply I tried to solve it with less fax machines to get idea how it should be with more fax machines, such as 3 and 4 fax machines with a simple brute force and
The results are as below:
(0,1) - (1,0) - (0,2) - (2,1) - (1,2) - (2,0) - $29$ for $3$ fax machines
and
(0,1) - (1,2) - (2,1) - (1,0) - (0,2) - (2,0) - (0,3) - (3,2) - (2,3) - (3,1) - (1,3) - (3,0) Total: $260$ for $4$ fax machines.
But
For 5 fax machines, it tooks long enough to cancel the run and think over the results I got previously.
After thinking a little over the results I noticed that
Whatever route I took, to find the maximum, you need to continue faxing where yo faxed last.. Such as (x,y) - (y,k) - (k,z) etc... So I have implemented this part into my brute force and try to find the result for $5$ fax machines.
As a result, it took a few seconds to find the optimal result as below:
(0,1) - (1,2) - (2,1) - (1,3) - (3,1) - (1,0) - (0,3) - (3,0) - (0,2) - (2,3) - (3,2) - (2,0) - (0,4) - (4,2) - (2,4) - (4,3) - (3,4) - (4,1) - (1,4) - (4,0) Total: $4106$ for $5$ fax machines.
and then I have noticed something else too while comparing the last solution with the previous answers, which is:
For $3$ fax machines it starts with
(0,1) - (1,0) ...
For $4$ machines, we put two other routes before the last (1,0) happens:
(0,1) - (1,2) - (2,1) - (1,0)...
For $5$ machines, we put another two other routes before (1,0) happens:
(0,1) - (1,2) - (2,1) - (1,3) - (3,1) - (1,0)
So I presume that with 6 fax machines, it should be in that way to maximize the results and it should start with at least:
(0,1) - (1,2) - (2,1) - (1,3) - (3,1) - (1,4) - (4,1)
By using this, I have found the result by starting with the sequence above. This is very likely the optimal solution!
No comments:
Post a Comment