Game on the tree There's a problem from programming competition which already finished:
http://codeforces.com/contest/458/problem/F
Two weeks already passed but still nobody solved it yet - in fact you can see here http://codeforces.com/problemset?order=BY_SOLVED_ASC that this is the only problem in the set of about 2000 problems that was not solved yet.
The problem itself follows.
Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it.
On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left.
Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?
Can you help me how to mathematically solve this minimax problem? Do we need to use any advanced concepts from game theory to solve this problem?
Thank you for the help in advance.
 A: It is unclear from your question what you mean by a "mathematical" solution.
From my experience in programming competitions (and, having a look on the problems over at project Euler), there is usually no "nice" closed-form solution to problems of this type. Thus, don't expect a formula, 
a significant amount of clever dynamic programming will be required to solve hard test cases.
Since you have not provided even a brute-force algorithm, 
I take it that you wonder about how to even formulate a naive algorithm.
Below is a min-max approach, with bad complexity, but it is a 
"mathematical" solution. For me, a "mathematical" solution is something that can be solved by a specific algorithm given enough time. 
(* Base case optimal value in optimal move *)
maxPossible[{l_Integer,r_Integer}]:=Max[l,r];
minPossible[{l_Integer,r_Integer}]:=Min[l,r];

(* Construct all subtrees, by applying op (Min or Max) on pairs of leaves.*)
SubTrees[tree_List,op_]:=Module[{l,r,pos},
    pos=Position[tree,{l_Integer,r_Integer}];
    Table[ReplacePart[tree,p->op@Part[tree,Sequence@@p]],{p,pos}]
];

maxPossible[tree_List]:=maxPossible[tree]=Module[{strees},
    (* All possible moves Max can do. *)
    strees = SubTrees[tree,Max];

    (* Max wants to maximize over all possible subsequent moves. *)
    Max[minPossible/@strees]
];

minPossible[tree_List]:=minPossible[tree]=Module[{strees},
    (* All possible moves. *)
    strees = SubTrees[tree,Min];

    Min[maxPossible/@strees]
];

(* Test cases, as on website *)
testTree1={5,10};
testTree2={{5,20},10};
testTree3={{1,2},{3,4}};
testTree4={{{7,8},15},{7,{9,11}}};

maxPossible[testTree1]
maxPossible[testTree2]
maxPossible[testTree3]
maxPossible[testTree4]

The output is as expected. It is easy to modify the code, so that actual gameplay can be recorded. The last game for example, gives the following sequence of moves:
--- {{{7,8},15},{7,{9,11}}}
--- {{{7,8},15},{7,11}}
--- {{{7,8},15},7}
--- {{8,15},7}
--- {8,7}
--- {8}

I think you will have better luck over at programmers.SE, since this question is similar to Project Euler questions (if you heard about it).
