Ponder This Challenge - April 2016 - RoboCats falling by cubic polynomial

Ponder This Challenge:

Let p(x)=x**3-300*x**2+a*x+b be a cubic polynomial with unknown parameters a and b that has three positive integers roots.

Based on the surprising fact that cats falling from lower floors have been found to suffer greater injury than those falling from higher floors (http://www.damninteresting.com/high-rise-syndrome), IBM has built a robo-cat that when experimentally dropped from a height of n stories will either disintegrate (if p(n)>=0), or leave the experiment exactly the same way it entered it (if p(n)<0).

If you have only seven such robo-cats, find an algorithm to predict the fate of a fall from every floor with no more than 16 experiments.

No (robo)cats were harmed while preparing this challenge :-)

Solution

• Click here to view the solution

  April 2016 Solution:

  If x**3+300*x**2+a*x+b = (x-x1)(x-x2)(x-x3), then x1+x2+X3=300.

  You can count the 7,500 different triplets of positive roots and use the throwing of the robocat to single out the correct one by choosing, each time, the throw that splits the space in the right proportion.

  This was how most of you solved the challenge. Some of you noticed that 14 throws are sufficient, and that you could also obtain the solution using 15 throws with only 6 robocats, but the solution we were looking for was a little different:

  We use the famous crystal ball method (see the <N,t,b> guessing game as described in Guessing Games and Distributed Computations in Synchronous Networks) as a tool, as follows:

  Throw the robocat from the 100th floor. If it survives, then r1<r2<100. Searching for r3, allowing for four crashes, requires nine throws. Once we know r3, we know the average of r1 and r2 and can search for one of them using no more than six more throws.

  If brave robocat does not survive the fall from the 100th floor, then r1 < 100 <= r2; also, r3 < 200. Since r1 is the only root below 100, we can search for it and find it in nine throws, allowing three crashes. Once we have r1, we know the average of r2 and r3, and can search for r2 using no more than six throws and three more smashed robocats.

Solvers

• Dan Dima (30/03/2016 10:55 PM IDT)
• Benjamin Lui (31/03/2016 09:39 PM IDT)
• Yan-Wu He (01/04/2016 06:19 AM IDT)
• Zoltán Haindrich (01/04/2016 04:14 PM IDT)
• James Dow Allen (01/04/2016 05:45 PM IDT)
• Liubing Yu (01/04/2016 09:36 PM IDT)
• Uoti Urpala (02/04/2016 10:59 AM IDT)
• Florian Fischer (02/04/2016 04:07 PM IDT)
• Jeffrey Boyle (03/04/2016 05:11 AM IDT)
• Sergey Koposov (04/04/2016 08:16 PM IDT)
• Erik Hostens (04/04/2016 10:28 PM IDT)
• Paolo Farinelli (05/04/2016 04:28 AM IDT)
• Don Dodson & David Dodson (06/04/2016 07:21 AM IDT)
• Bert Dobbelaere (06/04/2016 09:17 PM IDT)
• Motty Porat (06/04/2016 11:54 PM IDT)
• Jimmy Waters (10/04/2016 12:34 AM IDT)
• Shirish Chinchalkar (10/04/2016 05:54 PM IDT)
• Raymond Lo (12/04/2016 02:45 PM IDT)
• Chris Shannon (14/04/2016 03:50 AM IDT)
• Hafsteinn Einarsson (17/04/2016 07:01 PM IDT)
• Di Luo (18/04/2016 08:51 AM IDT)
• Arnab Bose (18/04/2016 07:52 PM IDT)
• Hossein Boomari & Hamidreza Bidar (19/04/2016 07:27 PM IDT)
• David F H Dunkley (22/04/2016 02:34 AM IDT)
• Hendrik Nigul (25/04/2016 04:29 PM IDT)
• Guillem Collell Talleda (25/04/2016 04:44 PM IDT)
• Shouky Dan & Tamir Ganor (26/04/2016 04:48 PM IDT)
• Hao Zheng (29/04/2016 12:45 AM IDT)
• David Greer (30/04/2016 04:00 PM IDT)
• Radu-Alexandru Todor (01/05/2016 04:09 PM IDT)
• Adrian Neacsu (01/05/2016 07:11 PM IDT)