Ponder This Challenge - August 2014 - Biased binary search

Ponder This Challenge:

We are trying to solve an optimization problem,

Let's assume that correct answer is defined as an integer number between 51 to 150 cm (inclusive).

You can use a black box solver to answer the question: "is the correct answer at least X?"

If the answer is positive - it costs you one cent, but if not - it costs you 10 cents.

Assuming that the answer is uniformly distributed (i.e., every number has the same probability) and using the most efficient strategy, how much will it cost, on average, to solve the problem?

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

Solution

• Click here to view the solution

  If the costs were equal, the best way to solve this problem would be a binary search. However, since erring on one side costs more, we should skew the search.

  Using the following dynamic programming:

  f(1) = 0

  f(n) = min_{0<i<n} [i/n*(f(i)+10) + (n-i)/n*(f(n-i)+1)]

  f(100) = ?

  we can find the best strategy, which costs, on average, 26.5 cents.

Solvers

• David Brink (07/31/2014 01:02 PM EDT)
• Yossi Fendel (07/31/2014 02:37 PM EDT)
• Liubing Yu (07/31/2014 02:58 PM EDT)
• Adrian Orzepowski (07/31/2014 03:06 PM EDT)
• Antoine Comeau (07/31/2014 03:16 PM EDT)
• Oleg Vlasii (07/31/2014 03:37 PM EDT)
• Harold Gutch (07/31/2014 03:50 PM EDT)
• Ariel Ish-Shalom (07/31/2014 05:37 PM EDT)
• José Eduardo Gaboardi de Carvalho (07/31/2014 05:45 PM EDT)
• Motty Porat (07/31/2014 08:49 PM EDT)
• Alan Murray (07/31/2014 09:25 PM EDT)
• Olivier Mercier (07/31/2014 09:29 PM EDT)
• Melvin Tsang (07/31/2014 09:33 PM EDT)
• János Kramár (07/31/2014 11:47 PM EDT)
• Anatoli Plotnikov (08/01/2014 01:59 AM EDT)
• Jochen Voß (08/01/2014 04:25 AM EDT)
• Philip Kinlen (08/01/2014 05:20 AM EDT)
• Graham Hemsley (08/01/2014 05:31 AM EDT)
• Armin Krauss (08/01/2014 06:47 AM EDT)
• Mathias Schenker (08/01/2014 08:34 AM EDT)
• Lv Jianhao (08/01/2014 09:33 AM EDT)
• Peter Gerritson (08/01/2014 10:01 AM EDT)
• Eric Farmer (08/01/2014 10:25 AM EDT)
• Rob Pratt (08/01/2014 10:25 AM EDT)
• David Greer (08/01/2014 11:11 AM EDT)
• Daniel Johnson (08/01/2014 11:24 AM EDT)
• John Tromp (08/01/2014 01:04 PM EDT)
• Tim Nordenfur (08/01/2014 01:39 PM EDT)
• Kevin Bauer (08/01/2014 01:58 PM EDT)
• Gilles-Philippe Paillé (08/01/2014 02:26 PM EDT)
• Kan Shen (08/01/2014 02:37 PM EDT)
• Christian Blatter (08/01/2014 02:53 PM EDT)
• Jan Rubak (08/01/2014 03:03 PM EDT)
• Lorenz Reichel (08/01/2014 03:48 PM EDT)
• Ben Phillabaum (08/01/2014 07:37 PM EDT)
• Ross Lippert (08/01/2014 08:12 PM EDT)
• Cynthia Beauchemin (08/02/2014 12:13 AM EDT)
• Rick Kaye (08/02/2014 02:31 AM EDT)
• Don Dodson & David Dodson (08/02/2014 02:31 AM EDT)
• Chris Shannon (08/02/2014 04:21 PM EDT)
• Clive Tong (08/02/2014 05:48 PM EDT)
• Franciraldo Cavalcante (08/02/2014 08:42 PM EDT)
• Michael Brundage (08/02/2014 09:20 PM EDT)
• Guangda Huzhang (08/02/2014 10:19 PM EDT)
• Andreas Kabel (08/03/2014 01:42 AM EDT)
• Dan Dima (08/03/2014 01:56 AM EDT)
• Joseph DeVincentis (08/03/2014 08:21 AM EDT)
• Harald Bögeholz (08/03/2014 09:08 AM EDT)
• Daniel Bitin (08/03/2014 10:20 AM EDT)
• Shanmukh Katragadda (08/03/2014 11:25 AM EDT)
• Florian Fischer (08/03/2014 11:56 AM EDT)
• Yue Ru Sun (08/03/2014 07:39 PM EDT)
• Allen Sirolly (08/03/2014 09:10 PM EDT)
• Arthur Breitman (08/04/2014 09:07 AM EDT)
• Yusuke Nojima (08/04/2014 09:07 AM EDT)
• Nagendra Gd (08/05/2014 04:02 AM EDT)
• James Dow Allen (08/05/2014 05:17 AM EDT)
• Guangzhong Sun (08/05/2014 07:11 AM EDT)
• Huafeng Jiang (08/05/2014 09:27 AM EDT)
• Reiner Martin (08/05/2014 03:12 PM EDT)
• Robert Lang (08/05/2014 04:02 PM EDT)
• Sergey Koposov (08/05/2014 06:25 PM EDT)
• Cameron Byer (08/05/2014 10:13 PM EDT)
• Hamidreza Bidar (08/06/2014 07:10 AM EDT)
• Amit Bhatia (08/06/2014 11:13 AM EDT)
• Aleksei Voidelevich (08/06/2014 12:14 PM EDT)
• André Vitor (08/06/2014 11:12 AM EDT)
• J. Eric Ivancich (08/07/2014 12:05 AM EDT)
• Sean Egan (08/07/2014 01:17 AM EDT)
• Gurvan Lullien (08/07/2014 02:13 AM EDT)
• Emilio Del Tessandoro (08/07/2014 03:05 AM EDT)
• Viktor Chayko & Aliaksei Vaidzelevich (08/07/2014 03:44 AM EDT)
• Victor Chaves (08/07/2014 01:11 PM EDT)
• Zhusong Li (08/07/2014 01:15 PM EDT)
• Noble Pendergrass (08/07/2014 04:57 PM EDT)
• Deyan Simeonov (08/07/2014 06:39 PM EDT)
• David Friedman (08/07/2014 10:39 PM EDT)
• Álvaro Begué (08/08/2014 01:41 PM EDT)
• William Heller (08/08/2014 06:24 PM EDT)
• Dávid Szalóki (08/11/2014 08:40 AM EDT)
• Klaus Hoffmann (08/11/2014 01:02 PM EDT)
• Andreas Stiller (08/11/2014 08:15 PM EDT)
• Keith Schneider (08/12/2014 12:28 AM EDT)
• Igor Karp (08/12/2014 01:29 AM EDT)
• Patrick Langechuan Liu (08/12/2014 11:31 AM EDT)
• Matt Crawford (08/12/2014 09:37 PM EDT)
• Lunce Fu (08/13/2014 03:55 PM EDT)
• Dezhi Zhao (08/13/2014 04:56 PM EDT)
• Kai Guttmann (08/13/2014 05:11 PM EDT)
• Roger Duthie (08/14/2014 03:48 AM EDT)
• Dinkar Vasudevan (08/14/2014 09:09 AM EDT)
• Misha Berlinkov (08/14/2014 10:03 PM EDT)
• Koszó Norbert (08/15/2014 01:46 AM EDT)
• Michael Schuresko (08/15/2014 12:08 PM EDT)
• Eden Hochbaum (08/15/2014 02:45 PM EDT)
• Michel Hannoyer (08/16/2014 02:53 AM EDT)
• Martin Thiim (08/16/2014 01:45 PM EDT)
• Joe Riel (08/18/2014 12:37 AM EDT)
• Attila Dankovics (08/18/2014 04:10 AM EDT)
• Ehud Schreiber (08/18/2014 08:00 AM EDT)
• Todd Will (08/18/2014 02:18 PM EDT)
• Addison Fischer (08/18/2014 05:48 PM EDT)
• Martin Cochet & Vladimir Milovanovic (08/19/2014 11:33 AM EDT)
• Guillaume Bioche (08/19/2014 04:57 PM EDT)
• Ken Meehan (08/19/2014 11:03 PM EDT)
• Wolf Wackeroth (08/20/2014 12:16 PM EDT)
• Michael Slifker (08/20/2014 02:55 PM EDT)
• Joe Clark (08/20/2014 04:18 PM EDT)
• Joe Klobusicky (08/20/2014 04:37 PM EDT)
• Joaquim Neves Carrapa (Joaquim Neves Carrapa EDT)
• William Mantzel (08/21/2014 04:04 PM EDT)
• Frank Mullin (08/21/2014 10:39 PM EDT)
• Janos Csorba (08/23/2014 02:25 AM EDT)
• Jan Fricke (08/23/2014 02:24 PM EDT)
• Antonio García Astudillo (08/24/2014 02:54 PM EDT)
• Sumeet Katariya (08/24/2014 09:29 PM EDT)
• Zhao Yu Dong (08/25/2014 12:49 AM EDT)
• Vladimir Dorofeev (08/25/2014 11:42 AM EDT)
• Erik Hostens (08/27/2014 07:45 AM EDT)
• Alex Fleischer (08/27/2014 12:06 AM EDT)
• Adam Daire (08/28/2014 04:34 PM EDT)
• Arsene Lui (08/28/2014 04:59 AM EDT)
• Daniel Lincke (08/28/2014 07:17 AM EDT)
• Zhangqiu Yu (08/29/2014 03:03 AM EDT)
• Vicent Pla (08/29/2014 04:40 AM EDT)
• Konstantin Dzhigardzhyan (08/31/2014 08:25 AM EDT)
• Radu-Alexandru Todor (08/31/2014 02:18 PM EDT)