Your computer science friend is learning about dynamic programming, and has challenged

you to a sashimi-eating game of her design. At the start of the game, there are two plates of

sashimi, containing n and m pieces respectively. At every turn, a player may eat all the n (or

m) pieces of sashimi on one plate, and redistribute the m (or n) pieces from the other plate

so that the two plates now contain m/3 and m-m/3 pieces (or similarly if redistributing n

pieces). The player who starts the turn with two plates each containing one sashimi piece

pays the bill. Your friend is condent that she can win with her secret dynamic programming strategy.

Luckily, you have also studied dynamic programming, and so you can always

pick a winning move if there is one. Assume that you will both be playing according to the

same strategy.

a) Design a dynamic programming algorithm which avoids paying the bill for a game

instance with starting plates containing n and m pieces (if there is a winning move for n and

m). Pay special attention to the order in which the elements of your table should be lled.

b) Determine an asymptotic running time for your solution and justify your result.