About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
November 2009
<<October November December>>
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.