Skip to main content

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)
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!


  1. is first one is 3 and second one is 2.05

  2. one more shot is it six and 2.86

    i am very sorry for bothering you like this but hopefully you understand excitement of a first timer :)

  3. good one man..
    first part is correct..
    second part is close... but not right.. :)
    I think you need one more try :P
    Best of Luck!

  4. 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

  5. @suyash..
    I 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.

  6. yes, sorry, thats what i meant, the first question i will ask is, q1: is the smallest divisor less than 6
    case 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.

  7. shit max... This is indeed an awesome max solution..

    I 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!! :)

  8. @suyash

    Update (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 ** :)

  9. 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.

  10. Yes. Correct solution Siddhant.

    To 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...).

  11. This comment has been removed by the author.


Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"

Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Sent to me by Gaurav Sinha

Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?