Skip to content

UVA Problem: 12293 ( Box Game)

October 5, 2011

Problem Statement:

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.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: