I am posting the puzzle. IBM Guys would post the solution in a month's time.
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.
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!