wu :: forums - Print Page


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

        riddles >> hard >> 100 paintings
        
(Message started by: spanchap on Mar 22^nd, 2007, 10:30pm)

Title: 100 paintings
Post by spanchap on Mar 22^nd, 2007, 10:30pm

There are 100 sculptures stored in 100 rooms. The scupltures are stored randomly - the best sculpture could be in any one of the 100 rooms.

You get to evaluate the sculptures beginning from room # 1 and walking thru successive rooms till you reach room #100. You are an expert in evaluating sculptures and are able to determine the relative rank of all sculptures in rooms 1 thru n when you have visited the first n rooms. Also, you know that no two sculptures have the same rank.

When you visit any given room , say room # p, you can declare that the sculpture in room p is the best sculpture among the 100 sculptures.

Once you have moved past a room, you do not get credit for declaring the sculpture in that room to be the best even though you might reach that conclusion after visiting the subsequent rooms.

What is your strategy to find the best sculpture if you get only one chance to go thru the 100 rooms?

What is your strategy to find the best sculpture if you get to do this exercise many times (say at different museums with different set of sculptures)?

Title: Re: 100 paintings
Post by towr on Mar 23^rd, 2007, 2:13am

This problem is also on the site as "bachelor dilemma", I think. And possible under a few other guises.
The result is well-known enough; proving it (at least for general N, rather than just 100) is quite a task though, if memory serves me right.

We've also considered the case were you know the distribution of value in one thread.

Title: Re: 100 paintings
Post by spanchap on Mar 23^rd, 2007, 7:23am

Thanks for letting me know that this puzzle has already been discussed. I will check that out. BTW, the solution is deceptively simple.

-Suresh

Title: Re: 100 paintings
Post by Whiskey Tango Foxtrot on Mar 23^rd, 2007, 7:56am

Here's a link (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028246833;start=23#23) in case the search function proves too fickle.

Title: Re: 100 paintings
Post by spanchap on Mar 23^rd, 2007, 2:19pm

Please see the below link to the bachelor problem for a solution not discussed till now

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

Title: Re: 100 paintings
Post by SWF on Mar 23^rd, 2007, 6:21pm

Why is the subject of this "100 paintings" when there are 100 sculptures?

Title: Re: 100 paintings
Post by spanchap on Mar 23^rd, 2007, 6:52pm

My bad. Should have been 100 sculptures.

I guess I was unconsciously giving somebody an opportunity to correct me. Now I wonder what that says about me...