Suppose there are two piles of plates in the table. One has ‘m’ RED plates and other has ‘n’ BLACK plates. In his/her chance, a player can either pick any number of red plates or any number black plates or equal number of red and black plates. A player loses if he cannot make a move in his/her chance. You are playing this game with your friend. Given that you begin the game and both the players play optimally, output ‘L’ if you will lose or ‘W’ if you will win.
Example:
input: m = 1, n = 2
output: L
input: m = 2, n = 2
output: W
Read about wythoff nim
How do you come up with the formula in the general case? I mean, even when you know the grundy theory, imagine being asked for who wins at (red,black) = (248149213213213, 237213213921839218321). Coming up with a pattern for 0 positions seems hard, no? The golden ratio thing for this case seems to come out of nowhere.
Yeah. Thats the whole point . There are many cases where there are no generalizations of N and P positions. The cases that are famous are where some magic is present. So we care about those and their variants.
Eg: See this variant. there are three nim piles with a,b,c stones . Moves for players are choose some pile and remove some stones from it or remove x(>0) stones from all three piles . This reduces to normal game . Though it looks to be harder than wythoff nim.
PS: I think in above example number of piles can be any odd number . Then it reduces to standard nim.
Is there any other method besides this as it is interview problem, can there be any pattern or approach which solves this easily?
What are the constraints? If m and n are reasonably small you can just recursively check all possible states.