We have to see if trump can win the game given that Obama plays optimally.
This is same as checking if trump can win if he plays optimally.
We can assume that trump gets 2 moves while Obama gets one.
Let us try to find some pattern by observing the game when trump plays first and N is small.
When N=1 or N=2
Trump will win removing all the heaps in two chances that he gets.
When N=3
If any of the heaps has size greater than 1 then Trump can spend both moves in removing that heap.
Now, Obama gets two heaps. He can only destroy one or make one smaller.
In both cases, Trump wins in the next move.
However, if all of the heaps are of size 1 then Trump loses and Obama wins.
Now we can use induction to prove that Trump loses only when he gets N divisible by 3
and all heaps of size 1.
When N MOD 3 =1
Assuming that Trump would win if he got N-3 or N-2 heapsAlso, he would win with N-1 heaps given at least one heap has size > 1
He can simply remove 2 heaps and give N-2 heaps to Obama.
Now obama can only remove one heap or reduce the size of one heap.
So, Trump gets N-2 or N-3 heaps and we know that he wins with them.
When N MOD 3 =2
Lets X be the no of heaps with size greater than 1If X≤2
Trump can reduce the array of heaps into N-2 heaps of size 1.
As all the heaps are of size 1 Obama has no choice but to remove one heap.
Trump gets N-3 heaps of size 1 and we know he wins with them.
If X>2
Trump can remove one heap of size greater than 1 in two moves.
Now Obama gets N-1 heaps with X≥2.
He can either give back N-2 heaps with X≥1 or N-1 heaps.
In both cases Trump wins.
When N MOD 3 =0
It can be easily proved that Trump loses for X=0When X≥1
Trump can use two moves removing a heap with size >1
Now Obama gets N-1 heaps. He can either give back N-2 heaps or N-1 heaps.
In both cases Trump wins.
So, using induction we have proven that Trump loses only when he gets N heaps, all of size 1 and N divisible by 3.
Obama wins only if he can convert the heaps that he gets into this losing state for Trump.