wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Black and White Balls
        
(Message started by: alexeigor on Mar 28^th, 2008, 3:42am)

Title: Black and White Balls
Post by alexeigor on Mar 28^th, 2008, 3:42am

Consider an urn filled with a number of balls each of which is either black or white. There are also enough balls outside the urn to play the following game. We want to reduce the number of balls in the urn to one by repeating the following process as often as necessary.

Take any two balls out of the urn. If both have the same colour, throw them away, but put another black ball into the urn; if thy have different collours the return the white one to the urn and throw the black away.

Each execution of the above process reduces the number f balls in the urn by one; when only one ball isleft the game is over. What, if anything, can be said about the colour of the final ball in the urn in relation to the original number of black and white balls?

Title: Re: Black and Whit Balls
Post by towr on Mar 28^th, 2008, 4:50am

Nice puzzle.

I was trying to work out a recurrence formula when suddenly I noticed, [hide]the number of white balls modulo 2 is invariant[/hide].

Title: Re: Black and Whit Balls
Post by alexeigor on Mar 28^th, 2008, 6:25am

Good observasion, so
[hide]
Transitions:
w,b == w, b-1;
w,b == w-2, b+1;

Invariant:
w == w mod 2;

if White odd, last ball is White
if White even, last ball is Black
I'm right?
[/hide]

Title: Re: Black and White Balls
Post by gotit on Mar 28^th, 2008, 6:32am

I think this problem is quite similiar to this

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1194039906;start=12#12

Title: Re: Black and White Balls
Post by towr on Mar 28^th, 2008, 7:10am

on 03/28/08 at 06:25:25, alexeigor wrote:

[hide]if White odd, last ball is White
if White even, last ball is Black
I'm right?[/hide]

Yup, that's what I got.

on 03/28/08 at 06:32:02, gotit wrote:

I think this problem is quite similiar to this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1194039906)

Quite similar indeed; just give all the black balls an even number, and the white balls an odd number.
When replacing two balls, number the replacement with the difference.