6

I stumbled upon an interesting combinatorial question while playing Magic: the Gathering.

Take N nodes on a complete graph, each node 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 that it's connected to. (The source node does not reduce its value after this operation; values can never decrease.) After one move in each direction along a graph edge (two moves in total), that edge is deleted and no more moves can be made along that edge. 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 in the game will be (N choose 2) * 2. (The number of edges times 2, since each edge allows one move in each direction.)

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 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, such as "always move away from the node with the highest value to the node with the highest value among its legal choices". This isn't necessarily optimal though, and I'm curious if there is a simple algorithm to maximize the final value that works on all N.

Isaac King
  • 427
  • You say , after all moves have been made. How many moves are possible? Is it until all possible exchanges between nodes have been done? – Sarvesh Ravichandran Iyer Apr 15 '16 at 04:38
  • 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. – Isaac King Apr 15 '16 at 04:46
  • 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. – Sarvesh Ravichandran Iyer Apr 15 '16 at 04:51
  • 1
    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. – Isaac King Apr 15 '16 at 04:58
  • Oh, nice. Thanks, I'll get back to you on this, I need to make a program first, though. – Sarvesh Ravichandran Iyer Apr 15 '16 at 05:03
  • @user331636 is there some requirement about using all the nodes? Or can you spend all the moves adding A to B over and over again? Such is obviously suboptimal (in fact, it produces the lowest score possible) but I want to check the rules – Stella Biderman Apr 15 '16 at 05:06
  • No, each move must be different. Each node may only make one move to each other node. – Isaac King Apr 15 '16 at 05:19
  • 2
    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].
    – joriki Apr 15 '16 at 08:23
  • Note that a) all moves among the first $N-1$ nodes come first, then those including the $N$-th node, and b) most of the moves are greedy, adding the highest number to the highest number it can be added to, but the move 4 -> 3 that goes from [15, 5, 9, 16] to [15, 5, 25, 16] isn't of this form; it prefers to add the $16$ to a node from which it can be added back to the $16$ in the next move. – joriki Apr 15 '16 at 08:29
  • OEIS doesn't have a sequence with the first four values $1,5,29,260$. – joriki Apr 15 '16 at 08:30
  • Note also that the optimum value for $N=3$ can be achieved like this: 
    1 -> 2     [1, 2, 1],
2 -> 1     [3, 2, 1],
1 -> 3     [3, 2, 4],
3 -> 2     [3, 6, 4],
2 -> 3     [3, 6, 10],
3 -> 1     [13, 6, 10],

    with the two moves not involving node $3$ coming first, but this then yields a lower value when used as an initial sequence for $N=4$ than the above solution for $N=4$, which has 2 -> 1 after moves involving node $3$. But this might be just an initial small-value phenomenon; it might still be possible to prove that the inductive approach is optimal for higher $N$.

     – joriki Apr 15 '16 at 08:58
  • You might be intersted in this question about a similar game, where a pattern emerges at higher $n$ but there are irregularities at small $n$. – joriki Apr 15 '16 at 09:03

2 Answers2

2

The sequence of largest possible values appears to begin $$ 1, 5, 29, 260, 4106, 122762, \dots $$ Only the first four values are certain, but I have considerable numerical evidence for the last two.

Two patterns emerge when we look at high-scoring solutions to small cases:

Conjecture 1. The best solution follows an Eulerian tour of the directed complete graph $\overrightarrow{K_n}$. As we follow the tour, every time we take a step $v \to w$, we add the value at $v$ to the value at $w$.

If true, this reduces the number of cases we need to check: instead of $(N^2-N)!$ orders, we only need to try every possible Eulerian tour, and there's many fewer of those.

Conjecture 2. There is a best solution which does all operations involving $N-1$ of the nodes (in some order) before doing all operations involving the last node (in some order).

Regarding Conjecture 2, it can be shown that if the best solution has this form, then (after permuting the nodes) it ends with the steps $$1 \to N \to 2 \to N \to 3 \to N \to \dots \to (N-1) \to N \to 1.$$ This also leaves us fewer cases to check: essentially, all the ways we can deal with the first $N-1$ nodes.

Here are the best solutions I've found:

  • When $N=1$, doing nothing scores $1$ point at the end.
  • When $N=2$, the Eulerian tour $1 \to 2 \to 1$ scores $5$ points.
  • When $N=3$, the Eulerian tour $1 \to 2 \to 3 \to 2 \to 1 \to 3 \to 1$ scores $29$ points.
  • When $N=4$, the Eulerian tour $1 \to 3 \to 2 \to 3 \to 1 \to 2 \to 1 \to 4 \to 2 \to 4 \to 3 \to 4 \to 1$ scores $260$ points.

So far, these have all been verified with brute force.

  • When $N=5$, the Eulerian tour $1 \to 4 \to 2 \to 4 \to 3 \to 4 \to 1 \to 3 \to 2 \to 3 \to 1 \to 2 \to 1 \to 5 \to 2 \to 5 \to 3 \to 5 \to 4 \to 5 \to 1$ scores $4106$ points.

I have found a variant of this solution three ways: using simulated annealing to get a high-scoring solution without brute force; using brute force over all Eulerian tours, assuming only Conjecture 1; using brute force over all $12!$ orders of the operations on nodes $1,2,3,4$, assuming only Conjecture 2. That suggests that it is in fact optimal, and that both conjectures are true.

  • When $N=6$, the Eulerian tour $1 \to 5 \to 2 \to 4 \to 2 \to 3 \to 2 \to 5 \to 3 \to 5 \to 4 \to 3 \to 4 \to 5 \to 1 \to 4 \to 1 \to 3 \to 1 \to 2 \to 1 \to 6 \to 2 \to 6 \to 3 \to 6 \to 4 \to 6 \to 5 \to 6 \to 1$ scores $122762$ points.

This last one was only feasible to find by assuming both conjectures, and doing a brute force over all Eulerian tours of nodes $1,2,3,4,5$ followed by the sequence $1 \to 6 \to 2 \to 6 \to 3 \to 6 \to 4 \to 6 \to 5 \to 6 \to 1$.

Misha Lavrov
  • 142,276
  • Note that your conjecture 2 makes computation very easy: in the chain $1 \to N \to 2 \to \ldots \to N \to 1$, you want the nodes $1,\ldots,N-1$ to be ordered in order of their values, with 1 being the node with the highest current value and $N-1$ the node with the lowest current value. By applying this "chaining technique" recursively, you can compute the value in something like $\mathcal O(n^2\log(n))$ time, or maybe even a bit better if you can void explicitly sorting. In fact, I think it's probably not hard to prove that the nodes' values stay sorted in every recursive step, just reversed. – Mees de Vries Jan 13 '23 at 12:20
1

The solution to N nodes, is their maximum path. These paths all obey a couple logical rules.

A. The only edges followed, are those whose origin was the previous edge's destination.

B. The path utilizes bouncing as often as possible, which is to travel to a node and return from it immediately.

These bounce edges, all connected by a return edge, make an outstretched-hand shape.

C. All the return edges are connected to a some unifying node.

This works until 6 nodes, where an important distinction arises. Two solutions exist for N nodes, depending on whether the nodes begin with equal populations or with unequal populations.

D. The first moves of the solution, is to reduce itself from an N graph of equals, to an N-1 graph of unequals.

For graphs composed of 4 nodes or less, unequals and equals solutions were reflections of each other. The same path, but taken exactly backwards. 5+ nodes break this, and this appears the first time after 6 nodes's initial reduction to 5 nodes.

C+. When beginning with unequals, the solution bounces as much as possible before it creates a unifying node, not after.

With every bouncing, it reduces itself into a simpler graph. The simplest graph is a 4 or 5 graph.

D+. The initial bouncing halts when the graph is reduced to 4 or 5 nodes, then returns to the very start.

E. Whether you have either an odd or even amount of nodes will change when the solution stops bouncing, at reduction to 4 or at reduction to 5.

F. The path cannot go too long without bouncing.

With solutions 7 and up, the final return is too long, and inefficient. Instead, a clever trick creates an incepted solution to 3 during the final return.

G. All paths utilize a certain arrangement to allow this incepted solution to 3 during the final return.

With solutions 9 and up, it can be seen that one incepted solution to 3 is not enough: a bouncing is necessary to add more incepted3-s to continue the final return.

G+. Certain nodes are barred from use, until during the final return, where they are used to continue a chain of incepted3-s.

Also

H. The nodes alternate by jumps of 2, not jumps of 1. It prevents getting stuck in a corner while bouncing.

And, obviously

I. The solution always travels towards the biggest population available, when choosing where to bounce. Duh.

So far, that completes the logic of the paths.

Let's see it in action.

The solution to 2 is a bounce.

The Solution to 3 is a reduction to 2, which then is just a bounce.

The solution to 4 is a reduction to 3, but not the one above. It is the reflection of it.

I will denote the ordering of the paths as a digit string and function.

$(2)=2

$(3)=32

$(4)=423

The solution to 5 is a reduction to 4, and then the reflection of 4.

$(5)=5324

The solution to 6 is a reduction to 5, then bouncing as much as possible until the path hits 4, then it uses the reflection of 4, and is finally followed by the final return.

$(6)=6(5)324R

The solution to 7 is a reduction to 6, then bouncing as much as possible until the path hits 4, then it uses the reflection of 4, and is finally followed by the final return; but it took care to not bounce too much, to allow an incepted3 later, which swapped (6)(5)324 into (6)(4)325

$(7)=7(6)(4)325RR

The solution to 8 is a reduction to 7, then bouncing as much as possible until the path hits 5, then it uses the reflection of 5, and is finally followed by the final return; but it took care to not bounce too much, to allow an incepted3 later, which swapped stuff around a bit.

$(8)=8(7)(5)4326RR

Notice that instead of the reflection 4235, what followed was 4325 (which later has its 5 swapped with 6). I do not know why 32 refuses to go away from every solution.

The solution to 9 is a reduction to 8, then bouncing as much as possible until the path hits 4, then it uses the reflection of 4, and is finally followed by the final return; but it took care to not bounce too much, to allow an incepted3 later. But the final return is still too long, so took care to reserve a node and its bounces, to create a chain of incepted3s.

$(9)=9(8)(6)(4)325R7RR

And so on

$(10)=10(9)(7)(5)4326R8RR

$(11)=11(10)(8)(6)(4)325R7R9RR

$(12)=12(11)(9)(7)(5)4326R8R10RR

$(13)=13(12)(10)(8)(6)(4)325R7R9R11RR

etc, creating a recursion of sorts.

The proper numbers, are

0 0

1 1

2 5

3 29

4 260

5 4106

6 122762

7 7224008

8 826 600 000 blah blah

9 187 000 000 000 blah blah

10 84 000 000 000 000 blah blah

11 7 ...000... big number, untested

12 unknown, untested

13 unknown, untested

And also, due to the exponential nature of growth, $(N) is approximately exp(some polynomial).

Yet $(N) always overtakes any exp(polynomial) eventually, so a solution to N can only be approximated, if you first know with certainty, the solution to N-1. Kinda useless.

Oh, and one more thing. I suspect this is related to the least-distance-to-connect-N-nodes-of-a-regular-polygon problem, or the Motorway Problem. Presented here by James Grime: https://www.youtube.com/watch?v=dAyDi1aa40E

Noxara Salva
  • 19
  • 4