Problem1.(10 points) You are given a game with the following rules: there are twoplayers, Blue and Red, playing one after the other each for a total ofnrounds andcontrolling a character, Charlie, to explore a board made of two types of tiles, blueand red.(So the game goes on for a total of 2nturns, alternating between the twoplayers, and Blue plays first.)When Blue plays, she decides whether the charactergoes left or right; when Red plays, she chooses to go forward or backward. At theend of the 2nsteps, Blue wins if Charlie is on a blue tile, and Red wins if Charlie ison a red tile.You want to find the optimal strategy to win the game, and, in particular, if thereis a way for Blue to win the game: we model the game as a binary treeTof height2n,where the leaves correspond to the tiles Charlie reaches at the end, and a pathfrom root to a leaf corresponds to a sequence of decisions by Blue and Red players.So the leaves of the tree are either red or blue; when we are at an internal node ofodd depth, it is Red’s turn to play; when we are at an internal node of even depth,this is Blue’s turn to play.Youaskedtwoofyourfriends,andtheycameupwiththefollowingtwoalgorithms,CANREDWIN1andCANREDWIN2,whicharesupposedtoindicateifthereisastrategyforRedtowinthegamenomatterhowwellBlueplays:ateverystep,Redcansel