IBM Research | Ponder This | November 2009 challenges
Skip to main content

Ponder This

November 2009

<<October November December>>


Ponder This Challenge:

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 (11/05): You should find the exact divisor without knowing the number and answering "prime" is not a valid.


We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 11/02/2009 @ 15:00 PM EST
Solution: 11/30/2009 @ 15:00 PM EST
List Updated: 12/16/2009 @ 15:00 PM EST

People who answered correctly:

Christian Kissig (11/02/2009 07:57 PM EDT)
Lukasz Bolikowski (11/02/2009 08:45 PM EDT)
Ante Kovacic (11/02/2009 11:05 PM EDT)
John T. Robinson (11/03/2009 02:47 AM EDT)
Corey Cerovsek (11/03/2009 04:06 AM EDT)
Andreas Eisele (11/03/2009 04:37 AM EDT)
P. Subrahmanya (11/03/2009 04:50 AM EDT)
Michael Brand (11/03/2009 05:01 AM EDT)
Pratik Poddar (11/03/2009 05:11 AM EDT)
Christian Blatter (11/03/2009 12:14 PM EDT)
Luke Pebody (11/03/2009 12:18 PM EDT)
Phil Muhm (11/03/2009 12:28 PM EDT)
Arthur Breitman (11/03/2009 01:24 PM EDT)
Martin Thiim (11/03/2009 03:56 PM EDT)
Klaus Hoffmann (11/03/2009 05:12 PM EDT)
Joe Fendel (11/03/2009 05:37 PM EDT)
Austin Shapiro (11/03/2009 06:27 PM EDT)
Donald T. Dodson (11/03/2009 06:46 PM EDT)
Pataki Gergely (11/03/2009 08:34 PM EDT)
Ante Turudic (11/04/2009 07:47 AM EDT)
Are Hjørungnes (11/04/2009 08:07 AM EDT)
William Heller (11/04/2009 08:45 AM EDT)
Mark Mixer
(11/04/2009 03:23 PM EDT)
Irem Koprulu Eryilmaz (11/04/2009 04:23 PM EDT)
Benedikt Engels (11/04/2009 05:25 PM EDT)
Krunoslav Kovac (11/04/2009 05:41 PM EDT)
Harald Bögeholz (11/04/2009 06:11 PM EDT)
Daniel Bitin (11/04/2009 07:22 PM EDT)
Chuck Carroll (11/04/2009 08:40 PM EDT)
Gale Greenlee (11/04/2009 08:57 PM EDT)
Kai Guttmann (11/04/2009 09:55 PM EDT)
Harold Gutch (11/04/2009 11:22 PM EDT)
Daniel Hsu (11/05/2009 01:36 AM EDT)
Yuval Filmus (11/05/2009 02:31 AM EDT)
Kin Keung Ma
(11/05/2009 03:49 AM EDT)
Dmitry Litvinenko (11/05/2009 08:59 AM EDT)
Will Hasenplaugh
(11/05/2009 01:28 PM EDT)
Sevag Papazian (11/05/2009 02:19 PM EDT)
David Friedman (11/05/2009 03:04 PM EDT)
Gueorgui Nedev (11/05/2009 03:12 PM EDT)
Alan Murray (11/05/2009 04:54 PM EDT)
Greg Janée (11/05/2009 10:36 PM EDT)
Andreas Stiller (11/05/2009 10:49 PM EDT)
Yuanmi Chen (11/06/2009 11:04 AM EDT)
Lei Zhao (11/06/2009 02:20 PM EDT)
Radu Borza (11/06/2009 02:25 PM EDT)
Hamidreza Bidar (11/07/2009 06:18 AM EDT)
Bernardino Romera Paredes (11/07/2009 10:05 AM EDT)
Dan Dima (11/07/2009 02:53 PM EDT)
Stefan `Sec` Zehl
(11/08/2009 12:57 AM EDT)
Yuvraj Dhillon (11/08/2009 05:56 AM EDT)
Subramanian CA (11/08/2009 06:12 AM EDT)
Rustam Miftakhutdinov (11/08/2009 09:06 AM EDT)
Joseph DeVincentis (11/09/2009 02:32 PM EDT)
Sylvain Becker (11/09/2009 07:33 PM EDT)
John G Fletcher (11/10/2009 01:59 AM EDT)
Troels Nørgaard
(11/10/2009 02:02 PM EDT)
Wolfgang Kais (11/10/2009 02:48 PM EDT)
Thomas Rohr (11/10/2009 02:48 PM EDT)
Liran Katzir (11/10/2009 04:11 PM EDT)
Guy Tannenbaum (11/10/2009 10:40 PM EDT)
Lachezar Hristov (11/11/2009 09:29 AM EDT)
Parashar Dave
(11/11/2009 01:29 PM EDT)
Stephen Herbert
(11/11/2009 01:36 PM EDT)
Rickard Björklund (11/11/2009 07:38 PM EDT)
Jörg Binder
(11/12/2009 07:31 PM EDT)
Karl D’Souza (11/12/2009 11:45 PM EDT)
Harinarayanan E V (11/13/2009 02:07 AM EDT)
Alan Curry (11/13/2009 04:18 AM EDT)
Albert Stadler (11/13/2009 04:04 PM EDT)
Stephan Keil (11/13/2009 08:23 PM EDT)
Michael Schaaf (11/15/2009 04:46 PM EDT)
Nagy Zoltan (11/16/2009 12:26 PM EDT)
Jeremy Cahill
(11/17/2009 09:32 PM EDT)
Susan Mielke (11/17/2009 10:59 PM EDT)
Chris Chen Xu (11/18/2009 03:59 PM EDT)
Ramkumar Balaraman (11/19/2009 09:09 AM EDT)
Wang Weiyan (11/20/2009 04:53 AM EDT)
Andy Kidd (11/20/2009 05:45 PM EDT)
Jimmy He (11/22/2009 09:06 PM EDT)
Se Kwon Kim
(11/23/2009 03:39 AM EDT)
Adam Daire (11/23/2009 03:35 PM EDT)
Amos Guler (11/24/2009 12:07 PM EDT)
Aviv Nisgav
(11/24/2009 06:32 PM EDT)
Fabio Filatrella (11/25/2009 10:14 AM EDT)
Jason W Christopher
(11/26/2009 06:52 AM EDT)
Clive Tong (11/26/2009 08:01 AM EDT)
James Carter (11/27/2009 06:34 AM EDT)
Rani Hod
(11/28/2009 09:04 PM EDT)
Hengfeng Tian (11/30/2009 02:31 AM EDT)
Shmuel Menachem Spiegel (11/30/2009 04:01 AM EDT)
Andrew Marut (11/30/2009 07:05 AM EDT)
Mutaamba Maasha
(11/30/2009 06:08 PM EDT)
Nyles Heise (12/01/2009 12:47 AM EDT)


Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.