wu :: forums - Print Page


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

        riddles >> medium >> 25 Attempts to Pass an Unknown Test
        
(Message started by: Barukh on Nov 15^th, 2011, 11:53am)

Title: 25 Attempts to Pass an Unknown Test
Post by Barukh on Nov 15^th, 2011, 11:53am

You are going to take a test consisting of 30 yes/no questions on a subject you have zero knowledge. To pass the test, you need to get all the answers right in a single attempt.

At every attempt, you supply your answers to every question, and the only information you get back is the number of questions answered correctly.

What are the chances you pass the test after 25 attempts?

I don't know the answer to this problem, but it looks quite interesting and belonging to at least Medium. I apologize if this is an old problem - haven't been around for a long time :(

Title: Re: 25 Attempts to Pass an Unknown Test
Post by towr on Nov 15^th, 2011, 12:18pm

It does sounds somewhat familiar, but if it's been posted before it would be a long while ago and I wouldn't know how to look for it.
Welcome back.

There's at least a 1 in 64 chance, since you can guarantee 24 correct answers. But you should be able to do much, much better.
I expect you should be able to get all combinations were 9 answers or less are "yes", or 21 or more; which gives you at least a 1 in 23 probability (not accounting your chances on the other cases).

Title: Re: 25 Attempts to Pass an Unknown Test
Post by Grimbal on Nov 16^th, 2011, 7:02am

It is kind of a variation of mastermind, isn't it?

Is it allowed not to answer a question?

If not, all possible submissions are equivalent for the first attempt and you can as well start with an all-yes attempt.

If you have a method that starts with some yes and some no, you can convert it to a method starting with all-yes by just reversing your guess in all attempts for all the questions you initially answered by no.

Title: Re: 25 Attempts to Pass an Unknown Test
Post by ThudnBlunder on Nov 16^th, 2011, 9:12am

on 11/15/11 at 12:18:39, towr wrote:

It does sounds somewhat familiar, but if it's been posted before it would be a long while ago and I wouldn't know how to look for it.
Welcome back.

Merely a fleeting visit, I suspect. :(

Not very (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1233708760) long ago.

Title: Re: 25 Attempts to Pass an Unknown Test
Post by Barukh on Nov 18^th, 2011, 1:11am

on 11/16/11 at 09:12:00, ThudnBlunder wrote:

Merely a fleeting visit, I suspect. :(

Not so fast - see my attempt to revive this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_general;action=display;num=1062691975;start=0) ;)

Quote:

Not very (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1233708760) long ago.

Ah, I suspected Leo is somehow involved, and now I know there is an elegant solution for 25 attempts version!