@vijju123, I made decision trees for tables of size 1x1, 1x2, 2x3, and 3x3. I can see that Yoda wins every time M and N are odd if we are playing with rule set 1 and Chef wins every time either M or N is even. But I fail to understand why this can be generalized to higher dimensions/values of M and N. My question is, how can we be sure that just because it worked till M, N <= 3, it will work for M, N>3. And also, what I didnt understand was if there is some optimal strategy that is there. For example, if Chef makes such and such a move, Yoda must make a move that fulfills certain conditions??
@gonecase- (To others, the question he asked is in comment of bansal1232ās answer, just telling so no one gets confused 
)
Ah! I see. Its a good question that why we are generalizing our observations. While I am still beginner in game theory type of questions, I will try my best to explain.
We are given that they play optimally. When both the players play optimally, then win and loss are solely decided by starting conditions, which in this case are dimensions of board.
This type of question usually require you to spot the recurring condition whichs are causing loss or win.
Yes, there are MANY possible moves for high matrix, and yes, for some questions you might have to go through all possible moves to find the optimal moves chosen by them. (Hence why we prefer performing it on smaller cases and extend it to larger ones).
While it is possible to symmetrically/mathematically or conceptually prove the wins in this Q, it can get really tough.
Eg- Lets take a case of N and M being odd, and diagonal rule set is to be followed (meaning they can only move diagonally)
Lets say we have a 5x5 grid, and chef starts at 1,1.
The ONLY possible move for Chef is to move from 1,1 to 2,2. Now, YODA wants to win, and after some trials you will find his optimal move is to push it from 2,2 to 3,3. Now poor chef can either go to 2,4 or 4,2 or 4,4. And its easily seen that no matter WHERE he moves, he is going to lose (as after his move, YODA could force the coin to another corner, getting the win.)
What determined who won or not? There were two factors here-
- Chef HAD to move from 1,1 to 2,2. No other possible move.
- The Size of board favoured YODA when he played optimally.
Now you may want to argue for a 7x7 board.
7X7 BOARD
Chef moves to 2,2. Now YODA would force him BACK to 1,3. Chef would have ONLY 1 POSSIBLE MOVE, i.e. from 1,3 to 2,4. YODA will again make him go to 1,5 , then chef could only go to 6,2 , and then YODA wins by making final move at 1,7.
NOTE- The same strategy could also be followed in 5x5 board. Actually, MULTIPLE winning strategy exist for a particular N and M, and what we found in case of 5x5 was something specific to it, (or perhaps extensible to higher cases, didnāt checkā¦too many possible moves).
NOTE 2 - We can interchange rows and columns here. Meaning If chef moves to 2,2, yoda can follow exact same strategy and move to 3,1 (& etc.) and win, provided that side is also odd.
(Also, I am sorry if I interchanged rows or columns in my explanation, please refer to image for clarity )
Here we found the true symmetry, and a concrete proof that at least one winning strategy for YODA EXISTS if both N and M are odd. YODA can play it every time N and M are odd. We can extend it to cases for 9x9,11x11 and so on. (Thus, for this case, extending of our base cases should work.)
And after concluding this, we might be interested in extending our base observations of other conditions to higher N and M. (Eg- When both even, when one even one odd etc.)
You CAN find other symmetries for other cases, but its tough. And problem setters expected us to conclude from observations.
Now, what if it fails? Had it failed, and we would had been unable to extend our base observations to higher ones, then we would be forced to either derive that when does winning strategy exist for CHEF/YODA (like we did above), OR there would be some hidden trick in Q for us to decipher.
I am sorry, I cant afford to go on deriving all possible cases at this moment ( Second Series of Exams from 31stā¦T_T pray for me 
), but I hope I quenched your query. BTW, it was a good question you asked, I am sure it would help many other people with similar doubt.
(PS- If you look at the image for 7X7 carefully, you would realize that the same strategy YODA can play if either one of N and M are even (because effectively everything is happening in the 2X7 matrix.) Meaning he can play this and win if N odd and M even. This when DIAGONAL rules are to be followed. When diagonal rules are not followed, we can prove that chef would win. (The strategy heād use is to go from 1,1 to 1,2 [1 cell down], forcing YODA to go from (2,2) and similarly win. (I thin you must have derived it in 2x2 and 2x3 type of matrices) )
2 Likes
I am glad it helped. :).
The basic proof that we can extend our base solutions is existence of at least one winning strategy for CHEF/YODA (which they can repeat everytime the board dimensions are favourable) for some pattern in dimensions.
For the diagonal move rule (Rule 2), I got the proof of āwhy does Yoda win when either side of the matrix is oddā. But for the other rule, I didnāt find any solid proof of the winning conclusions. Are they just derived from observations or there is any proof?