# UVA Problem: 12293 ( Box Game)

This problem seems complicated at fast glance. But there is a hidden pattern inside solution. Problem statement says –

One of them contains n balls, while the other box contains one ball.

Forget the other box , just consider the box with n balls.

Remember , Alice moves first , Both try to win and play perfectly.

Let’s Define ,

Game(t)=Win , if a player get (t ) ball and his move leads to win the game.

Game(t)=Lose , if a player get (t ) ball and his move leads to lose the game.

Now try to generate pattern-

n=2 , which can be split into (1+1) , Bob can’t take the ball next turn So winner is Alice, so Game(2)=Win.

n=3 , which can be split into (2+1) , So Bob get 2 ball and its his turn, and we previously computed that Game(2)=Win, so Bobs win and Alice Lose that means Game(3)=Lose.

n=4, which can be split into (2+2) or (3+1), Alice want to to give bob that number of ball so that Bob Lose. If she give Bob 3 ball then Bob will certainly lose since Game(3)=Lose. So in this case Alice will win , so Game(4)=Win.

If you go on that way you will be able to generate a pattern when Alice/Bob will win.