← All solutions

The main observations that need to be made are the following:

1. If doing a takeover, we should always take over the largest company of the opponent (in particular, if we can not take over that company we should not do a takeover).
2. If doing a merge, we should always merge the two largest companies that we have.

While intuitively obvious, proving them is a bit tedious, so have fun with that.

With these observations, one can try a simple recursive tree search. This actually works (as long as you always try doing a takeover, when possible, before doing a merge), except that you will probably run out of stack size and crash.

Why should it work? Well, here are two more observations (easy to prove given the first two):

3. If a takeover is possible at any time after a merge move has been made, then that takeover will be winning.
4. After a takover, the opponent will be forced to merge.

Taken together, this implies that it is only the first move of the game in which there is actually a choice. Thus, one can just try the (at most) two possibilities for that move and then easily simulate the rest of the game.