Question 14:

Start your Monday with this fun but complex puzzle!

Imagine a graph with two node colors: red and blue. Let K and d be natural numbers.¹

(¹For the purposes of this exercise, zero should not be considered a natural number.)

Start with a single red node.

Each step, any red nodes with no arrows going from them create d new blue nodes. At the same time, any blue nodes (excluding the ones just created) with no arrows pointing from them create one new red node. Every node created by another node has an arrow going from its parent to it. This is player A’s turn.

On player B’s turn, they can “take” (remove) up to K nodes. Removing a node also removes any arrows pointing to or from it, and nodes can be reactivated this way.

Player B wins if they drive the population to extinction (if they remove all of the nodes.)

Player A wins if Player B cannot win (if the population will avoid extinction forever.) A converging population (e.g. one that cannot diverge to infinity but will never go extinct) still counts as a win for Player A.

1. Try the classic variation of this problem with d = 8. Assuming optimal play by Player B, what is the maximum value we can set for K, where K ∈ ℕ, where Player A will always win, no matter what moves Player B makes?

2. More importantly, can we create a function K(d) in terms of d that will find the maximum winnable value of K for us for any d ∈ ℕ?

2023-10-09 01:48:40.113