How much money can we make?

Question

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 1

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.

Answer 2

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!

Answer 3

Well I am a bit late to the party, but I did manage to find another solution that gives the same amount as the accepted answer:

$3\rightarrow1, 1\rightarrow5, 5\rightarrow2, 2\rightarrow5, 5\rightarrow4, 4\rightarrow5, 5\rightarrow1, 1\rightarrow4, 4\rightarrow1, 1\rightarrow2, 2\rightarrow4, 4\rightarrow2, 2\rightarrow1, 1\rightarrow3, 3\rightarrow2, 2\rightarrow3, 3\rightarrow4, 4\rightarrow3, 3\rightarrow5, 5\rightarrow3, 3\rightarrow0, 0\rightarrow5, 5\rightarrow0, 0\rightarrow4, 4\rightarrow0, 0\rightarrow2, 2\rightarrow0, 0\rightarrow1, 1\rightarrow0, 0\rightarrow3$

giving the final amounts:

0: 40921, 1: 20540, 2: 10329, 3: 42826, 4: 5280, 5: 2866

For the 7 person version of the problem my best solution produces

$7, 230, 779

Answer 4

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