IBM Ponder This November Challenge
I am happy.. I am amongst the first few people to solve IBM Ponder This November Challenge.. This puzzle, unlike the last one, is really challenging and requires mathematical skills.
I am posting the puzzle. IBM Guys would post the solution in a month's time.
IBM Page
What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)?
We are asking for the exact answer in two cases:
In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?
On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.
* For example, the smallest divisor of 105 is 3, and of 103 is 103.
Update (26-05-2011)
Solution:
First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments!
Second part: Posted by Siddhant Agarwal, EE IITB 2011 Alumnus in comments!
I am posting the puzzle. IBM Guys would post the solution in a month's time.
IBM Page
What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)?
We are asking for the exact answer in two cases:
In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?
On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.
* For example, the smallest divisor of 105 is 3, and of 103 is 103.
Update (26-05-2011)
Solution:
First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments!
Second part: Posted by Siddhant Agarwal, EE IITB 2011 Alumnus in comments!
is first one is 3 and second one is 2.05
ReplyDeleteno dude.. thats not correct..
ReplyDeleteis the second one is wrong
ReplyDelete@Abhishek
ReplyDeleteBoth are wrong
one more shot is it six and 2.86
ReplyDeletei am very sorry for bothering you like this but hopefully you understand excitement of a first timer :)
good one man..
ReplyDeletefirst part is correct..
second part is close... but not right.. :)
I think you need one more try :P
Best of Luck!
i see how you got the first answer has 6. but what if the first question we ask is, is X smaller than 6? that would reduce the number of questions
ReplyDelete@suyash..
ReplyDeleteI dont think I understand your point.. In the first problem, you have to design a set of questions such that in the worst case, you have to ask minimum number of questions to find the number.
You cannot ask "any" question. Question will be of the form Is that number <= alpha and similar questions.
I think what you are saying is asking question like "If I conduct an experiment, then will the number of questions I will have to ask be <= beta?". Interesting approach. But I don't think the question is allowing such questions.
yes, sorry, thats what i meant, the first question i will ask is, q1: is the smallest divisor less than 6
ReplyDeletecase 1: yes
q2: is it greater than equal to 3
case 1.1: yes
q3: is it 3
case 1.1.1: yes. then it is 3.
case 1.1.2: no. then it is 5.
case 1.2: no. then it is 2.
case 2: no
q2: is it greater than equal to 13?
case 2.1: yes
q3: is it 13?
case 2.1.1: yes. then it is 13
case 2.1.2: no. then it is the number itself
case 2.2: no
q3: is it 11?
case 2.2.1: yes. then it is 11.
case 2.2.2: no, then it is 7.
how does this look? 3 questions is all i ask, in the worst case.
shit max... This is indeed an awesome max solution..
ReplyDeleteI still managed to get my name there means even the IBM guys did not think of it.... Will talk to more people and reply if there is some mistake..
But as far as I can think, its AWESOME!! its LEGEN wait for it DARY!! :)
@suyash
ReplyDeleteUpdate (11/05): You should find the exact divisor without knowing the number and answering "prime" is not a valid.
So, your algorithm is not correct.. Nice try though...
The answer still remains as 6 and ** :)
For the second question, u calculate the probabilty of a number being the smallest divisor.(For eg. prob that smallest divisor = 13 is 1/165) This prob distribution has the index set of 38 elements(the set of primes less than 166). Then construct the Huffman code over this and then find the expected length of this code. That is the optimal.
ReplyDeleteYes. Correct solution Siddhant.
ReplyDeleteTo summarize: (from the IBM Site)
The smallest divisor of a number between 2 and 166 has 38 different possibilities. Therefore, for the first case (worst case) one needs at least ceil(log2(38)) = 6 questions. [Binary search]
On the other hand, since the probabilities are biased, we can use Huffman coding to find it in less than three questions on average (494/165 = 2.9939...).
This comment has been removed by the author.
ReplyDelete