2
$\begingroup$

I stumbled upon an interasting combinatorial question while playing a game of Magic: the Gathering.

Take N nodes, each one with an assigned value. Each node's value begins at 1, and may increase as the game progresses. Each move of the game consists of a node adding its value to the value of one other node. The source node does not reduce its value after this operation. Each pair of nodes may only make one move in each direction. The goal is to end up with the greatest possible total value among all nodes after all moves have been made. (The total number of moves will be (N choose 2) * 2.)

For example, consider N=2. The starting configuration is A=1,B=1. To begin the game, Node A adds its value to node B, resulting in A=1,B=2. Then node B adds its value to node A, resulting in A=3,B=2. The game is now over, and the final "score" is 5. The only other possibility is to have node B move first, which simply results in A=2,B=3 and the same final score.

However the problem becomes greatly more complex when more nodes are added. The complexity of the game increases extremely quickly, making brute-force approaches infeasible. So far, the maxima I have achieved for various N through random experimentation are:

N=1: 1
N=2: 5
N=3: 29
N=4: 249
N=5: 3866

But I am by no means convinced these are the best answers (at least for N>2). There are a number of simple instruction sets that can do well, but there always seems to be a better one, at least for some N. I'm curious if there is a simple algorithm to maximize the final value that works on all N.

$\endgroup$
  • $\begingroup$ You say , after all moves have been made. How many moves are possible? Is it until all possible exchanges between nodes have been done? $\endgroup$ – астон вілла олоф мэллбэрг Apr 15 '16 at 4:38
  • $\begingroup$ Yes. The total number of moves is going to be (N choose 2) * 2. So if N=2, the number of moves is 2. If N=3, the number of moves is 6. If N=4, the number of moves is 12. Etc. $\endgroup$ – KingSupernova Apr 15 '16 at 4:46
  • $\begingroup$ So for $N=3$, can you simulate the game in two different ways that brings two different answers? I have the hunch the answer is the same all the time, that's why. We've seen for $N=2$ that this happens, I want to see that it doesn't happen for $N=3$, so that this problem is meaningful. $\endgroup$ – астон вілла олоф мэллбэрг Apr 15 '16 at 4:51
  • 1
    $\begingroup$ Oh, it does. The number of moves is set, so we want to maximize the increase with each move. For example, Take N=3. If you simply add nodes B and C to node A first, we get A=3,B=1,C=1. Then we do the same for B and get A=3,B=5,C=1. Then finally we do it for C and get A=3,B=5,C=9, for a total of 17. If however we do it cyclically, with A→B,B→C,C→A,A→C,B→A,C→B, then we get a final answer of A=6,B=9,C=7 for a total of 22. Even better options exist, the best I've found for N=3 Gives a total of 29. $\endgroup$ – KingSupernova Apr 15 '16 at 4:58
  • 1
    $\begingroup$ Here's code that performs an exhaustive search up to $N=4$. Your value for $N=3$ is optimal, but for $N=4$ there's a better solution, resulting in a sum of $260$: 1 -> 2 [1, 2, 1, 1], 2 -> 3 [1, 2, 3, 1], 3 -> 2 [1, 5, 3, 1], 2 -> 1 [6, 5, 3, 1], 1 -> 3 [6, 5, 9, 1], 3 -> 1 [15, 5, 9, 1], 1 -> 4 [15, 5, 9, 16], 4 -> 3 [15, 5, 25, 16], 3 -> 4 [15, 5, 25, 41], 4 -> 2 [15, 46, 25, 41], 2 -> 4 [15, 46, 25, 87], 4 -> 1 [102, 46, 25, 87]. $\endgroup$ – joriki Apr 15 '16 at 8:23

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.