5
$\begingroup$

This is follow up question to How much money can we make?


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 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


This time you are trying to maximize your money instead of maximizing sum of the money and your friends are of course trying to help you.

How much can you make at most?

Note: You may need to use computer programming or you may not.

$\endgroup$
8
$\begingroup$

I have nothing resembling a proof that this is optimal, but a bit of computer-searching found a sequence that appears to get

\$55287 via the following sequence of transfers: (1, 0), (5, 1), (2, 5), (5, 2), (3, 5), (5, 3), (4, 5), (5, 4), (1, 5), (4, 1), (1, 4), (3, 1), (4, 3), (3, 4), (2, 3), (4, 2), (2, 4), (3, 2), (1, 3), (2, 1), (1, 2), (0, 1), (2, 0), (0, 2), (3, 0), (0, 3), (4, 0), (0, 4), (5, 0), (0, 5).

Here's the crappy Python code I wrote to do it. It's doing simulated annealing. I made a guess at some parts of the solution by extrapolation from the (more-likely-optimal) solutions the same code found for smaller n, and forced it to look at only solutions fitting that pattern; I hope it's clear what to delete and change to undo that.

import math, random
n_people = 6
edges = []
for i in range(n_people): edges.extend((i,j) for j in range(n_people) if j != i)
# Ugly hack: enforce conjectured shape of solution
# (to not do this, remove next 3 non-comment lines and see
# single change below; note also that this needs changing if n_people
# changes)
edges0 = [(1,0), None, (2,1), (1,2), (0,1), (2,0), (0,2), (3,0), (0,3), (4,0), (0,4), (5,0), (0,5)] # adjust if n_people changes
edges1 = [e for e in edges if e not in edges0]
edges = edges0[:1] + edges1 + edges0[2:]
n_edges = len(edges)
def score(edges):
    money = n_people*[1]
    for (i,j) in edges:
        money[i] += money[j]
    #return sum(money) # use this to optimize total money (older problem)
    return money[0] # use this to optimize your own money (newer problem)
def mutate(edges):
    edges = edges[:]
    # The -11 version is for the "restricted" optimization
    #i,j = random.sample(range(n_edges),2)
    i,j = random.sample(range(1, n_edges-11),2)
    edges[i],edges[j] = edges[j],edges[i]
    return edges
curr = score(edges)
best = (curr, edges)
print(best)
temp = 8000
while True:
    candidate = mutate(edges)
    cscore = score(candidate)
    if cscore > curr or random.random() < math.exp((cscore-curr)/temp):
        edges = candidate
        curr = cscore
        if curr > best[0]:
            best = (curr, edges)
            print("new best", curr, edges)
    temp = 0.999993 * temp
    if temp < 1:
        print("resetting", curr, edges)
        temp = 8000
$\endgroup$
  • $\begingroup$ If using a code solution, it would be really great if you could post the code in the answer so future readers can compare their version against yours. $\endgroup$ – Bilkokuya Mar 21 '18 at 16:33
  • 2
    $\begingroup$ Yeah, will do at some point. $\endgroup$ – Gareth McCaughan Mar 21 '18 at 16:50
  • $\begingroup$ this is what I have found as well after your last edit. I am pretty sure (like 99% sure) there is no better answer. Thanks @GarethMcCaughan. I will wait a little then accept your answer. Was it just pure brute force or did you apply something else? $\endgroup$ – Oray Mar 21 '18 at 16:57
  • $\begingroup$ Fairly brutish -- simulated annealing -- except that after a while I looked at the shape of the best solutions it had found for n=2,3,4,5, made a guess at some features the best solution for n=6 was likely to have, and sped things up by restricting the search accordingly. $\endgroup$ – Gareth McCaughan Mar 21 '18 at 18:09
4
$\begingroup$

Not sure if this is optimal but I think you can get

$\$39,812$

Strategy

First, have you (numbered $0$) and four other friends to build up the maximum amount of money between yourselves using the strategy from the answer to the previous question.

Specifically, if your friends are numbered $1$ to $4$ then the sequence of moves is

$(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)$

If I've gotten my numbers right, this gives the following monetary distribution among you and your friends:

$0: \$1485, 1: \$690, 2: \$199, 3: \$365, 4: \$1369 $

Then, with the other friend numbered $5$, proceed with the following sequence of moves:

$ (0,5) - (5,4) - (4,5) - (5,1) - (1,5) - (5,3) - (3,5) - (5,2) - (2,5) - (5,0) $

This exploits the idea of copying the largest amount of money each step. You should end up with $ \$ 39,812$

Feel free to correct me here, I rushed this so may have made mistakes.

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