23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't know either. My initial solution matched AP's, but that's clearly not the optimal one since it was beaten. I'm probably going to wait a few more days, then accept the highest result. $\endgroup$ – Arcanist Lupus Mar 14 '18 at 13:21
9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Wow, really good! Can you explain a bit more what you mean with "a little tweak"? Because my brute-force is expected to take 1.9 billion years for only trying all closed paths. $\endgroup$ – A. P. Mar 12 '18 at 22:16
  • $\begingroup$ @A.P. put an explanation how I found the result. hope it helps. $\endgroup$ – Oray Mar 13 '18 at 7:11
  • $\begingroup$ I agree it's very likely, but maybe some weird mathematical properties makes the optimum from 5 on not a path or something. It wouldn't be the first time 5 is a special number, $S_5$ is non-solvable $\endgroup$ – Florian Bourse Mar 13 '18 at 8:49
11
$\begingroup$

The idea is that

always the biggest amount of money should be copied. So the money must be concentrated on one person.

A good scheme would be

$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 6$.


Now if $6$ sent the money back to $1$, he wouldn't be able to send it around any further, so
$\color{red}{6 \to 5}$, $\color{red}{5 \to 6}$, $\color{red}{6 \to 4}$, $\color{red}{4 \to 6}$, $\color{red}{6 \to 3}$, $\color{red}{3 \to 6}$, $\color{red}{6 \to 2}$.


Again, if the money was sent back to $6$, it could only give it back to $1$, hence continue with
$\color{#0F0}{2 \to 3}$, $\color{#0F0}{3 \to 2}$, $\color{#0F0}{2 \to 4}$, $\color{#0F0}{4 \to 2}$, $\color{#0F0}{2 \to 5}$.


The scheme continues in the same way:
$\color{#00F}{5 \to 4}$, $\color{#00F}{4 \to 5}$, $\color{#00F}{5 \to 3}$,


$\color{#F0F}{3 \to 4}$.


Now the cycle can be closed:
$\color{#3DD}{4 \to 3}$, $\color{#3DD}{3 \to 5}$, $\color{#3DD}{5 \to 2}$, $\color{#3DD}{2 \to 6}$, $\color{#3DD}{6 \to 1}$.

The amount of money created this way is

the sum of all final individual amounts of money minus the $\$6$ seed money, which is $\$98111$.

Addendum: As pointed out by Jaap Scherphius this solution is not optimal. In fact,

changing the order of the transfers, such that the last 2 steps of my solution ($\color{#3DD}{2 \to 6}$, $\color{#3DD}{6 \to 1}$) are executed before all others, results in a higher amount of created money: $\$ 118761 - \$ 6$. Trying out all other starting points for this circular path shows that this is the maximum for these permutations.

To actually find the global maximum

I have no better idea than to brute-force all possible permutations of the 30 transfers, which gives $30! = 265252859812191058636308480000000$ possibilities. This can be narrowed down by only considering closed paths, i.e. permutations in which the person who just recieved money is the next to send a fax. This ensures that always the biggest money pile is copied. Proof: If person $A$'s money $m_A$ is more than the money of any other person $m_i$ and he sends it to person $B$, then person $B$ has now $m_B + m_A > m_A$, hence he is now the one with the most money and should send it further.

$\endgroup$
  • $\begingroup$ It's strange, a simulation doesn't give the same total amount: termbin.com/t1yh (I find 71919-6$) (maybe the solution I have is false, I used a regex on your answer to generate it) $\endgroup$ – Labo Mar 10 '18 at 22:42
  • $\begingroup$ @Labo Sorry, I changed the ordering in the first edit. Your simulation still uses the old ordering. If you re-run the regex script with the updated answer, you should get the same value as me. $\endgroup$ – A. P. Mar 10 '18 at 22:53
  • $\begingroup$ @Labo Here is the new value for your variable sol = [(0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0), (0, 4), (4, 0), (0, 5), (5, 4), (4, 5), (5, 3), (3, 5), (5, 2), (2, 5), (5, 1), (1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 3), (3, 4), (4, 2), (2, 3), (3, 2), (2, 4), (4, 1), (1, 5), (5, 0)]. $\endgroup$ – A. P. Mar 10 '18 at 23:00
  • $\begingroup$ Indeed, it works :) Is your answer a proof of optimality or just a greedy idea? $\endgroup$ – Labo Mar 10 '18 at 23:27
  • 3
    $\begingroup$ You can improve your score substantially if you do the last two transfers ((1,5), (5,0) in the Labo's code) first, followed by the other moves in the same order. The score is then $118761-6=118755$ $\endgroup$ – Jaap Scherphuis Mar 11 '18 at 1:10
2
$\begingroup$

Answer:

The result I came up with is $16993 and here's how:

Step 1:

Let a b c d e f be the fax machines.

Step 2:

Pick the longest path, starting with a. Let's go for ab,ba,ac,ca,ad,da,ae,ea,af,fb,bc,cb,bd,db,be,eb,bf,fc,cd,dc,ce,ec,cf,fe,ef,fa. Notice how f sends money to a only at the end, since a has already exhausted it's attempts to every other fax machine.

Step 3:

Send the money around, then concatenate the final total of all the fax machines. a is 5539, b is 320, c is 1888, d is 470, e is 3268 and f is 5508.

Workings:

(Format is SenderReceiver-NewReceiverTotal)

a=1
ab-2    ba-3    ac-4    ca-7    ad-8    da-15   ae-16   ea-31   af-32
fb-34   bc-38   cb-72   bd-80   db-152  be-168  eb-320  bf-352
fc-390  cd-470  dc-860  ce-1028 ec-1888 cf-2240
fe-3268 ef-5508 fa-5539
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.