1
$\begingroup$

Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow algorithm. I am writing my unsuccesful attempt at solving it using dynamic programming at the end of this thread. What is the right algorithm to solve this ?

The 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


My attempt:

Each round consists of money being sent from one fax machine to another . Therefore, there will be a total of 30 rounds. Let 1->2 means sending a fax from 1 to 2, etc.

I first thought that after, say, 3 rounds,

The sequence (1->2) (2->4) (4->2) will be the same as the sequence (2->4)(4->2)(1->2) and therefore we can consider them as one . This way, we won't have to consider all possible permutations. But then I realised that these 2 permutations are not the same . The first one results in \$1 , \$5 , \$2 with 1, 2 and 4 after the 3 rounds but the second one results in \$1, \$3 and \$2 with 1, 2 and 3 respectively.

Using this approach will still require of me to consider all the possible permuations, taking me back to square one.

$\endgroup$
3
  • $\begingroup$ You want the sequence with maximum output. 1,5,2 is more than 1, 3, 2 so the second permutation can indeed be ignored. And you can put permutations in a canonical order. So the first fax is 1 -> 2. The next is 2->1, 1->3, 2->3, 3->2, 3->4. $\endgroup$
    – gnasher729
    Nov 26 '21 at 11:11
  • $\begingroup$ A sequence a->b, c->a is always worse than c->a, a->b so it can be excluded. $\endgroup$
    – gnasher729
    Nov 26 '21 at 11:21
  • $\begingroup$ @gnasher729 .. the time taken to consider all possible permutations is 30! . Even if we reduce the time to 29! , it is still a lot of time. I am looking for a solution that takes reasonable amount of time . $\endgroup$ Nov 27 '21 at 11:41

Your Answer

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

Browse other questions tagged or ask your own question.