 # ZIO12001 - Editorial

Editorialist: Sudheera Y S

Problem Link: ZIO 2012 Problem 1

Problem statement :

There are ‘x’ white color balls and ‘y’ black color balls in a bag. You pick two ball at a time and follow the procedure :

1. If both are white , throw both of them
2. If both are black , throw one ball , and return another in the bag
3. If they are different colors , then throw the black ball and return the white ball in the bag

Compute the minimum and maximum values of N ( number of times you pick the balls ) and the color of the last ball

Idea :

Here we find a pattern ( with logic ) :

From points 2,3 ( problem statement ) , we find that in either of the cases the number of black ball reduces only by 1 , therefore we need :

Let’s denote the number of black balls by x :

1. If x is odd → one by one reduces , therefore we need x operations to completely throw the black balls
2. If x is even → we cant throw away the last ball , no matter what therefore we need exactly x-1 operations to throw away all x-1 black balls and only 1 ball will be left

Here we should also observe that Min N = Max N because we are performing the same operations and if we do the operations in any order , it doesn’t matter because to throw away all the black balls , we need exactly x or x-1 operations NO MATTER WHAT ( i.e even if we do operations 2 or 3 , the black ball reduces only by 1 ) therefore Min N = Max N ( because we can only lose white balls by operation 1 )

Minimum ( and maximum ) number of operations to throw away all black balls → x or x-1

Minimum ( and maximum ) number of operations to throw away all white balls → floor(y/2)

Therefore , Min N = Max N = ( x or x-1 ) + floor(y/2)

Here we are doing floor because , if y is odd then we will end up with last one ball therefore we need exactly (y-1)/2 for y being odd and floor does that If y is odd , we end up last ball being white because white ball only reduces by 2 and if y is even , then we will end up with last ball being black because black reduces only by 1

Summing it up , Min N = Max N = ( x or x-1 ) + floor(y/2) , color of the last ball is white if y is odd , or else if y is even then the last ball color will be black ( now let us start doing the subtasks )

Subtask A: 17 black, 23 white

Min N = Max N = 17 + (23/2) = 17 + 11 = 28

Number of white balls is odd, therefore color of the last ball is white

Subtask B: 42 black, 32 white

Min N = Max N = 41 + (32/2) = 41 + 16 = 57

Number of white balls is even, therefore color of the last ball is black 