Happy Easter! This week, we search for the Easter bunny. There are five hideouts in one line, numbered 1 to 5. The Bunny hops to an adjacent hideout after every time you (unsuccessfully) check out one of them. Minimize the number of checks to find the Bunny.
Find a solution to optimize the four-hideouts worst-case performance first. Then move on to five hideouts and, for extra credit, consider creating a strategy that minimizes the average number of hideouts that must be checked (whereby we stop looking if we have not found the hopper after ten tries and then penalize that search with 20 tries - this would be called PAR-2 in communities like SAT).
To minimize a 4 hideout search, we would check 3 - 2 - 2 - 3 (or 2 - 3 - 3 - 2) to be guaranteed to find the bunny after 4 tries max. It should be clear that this strategy traps the bunny if it started in hideouts 1, or 3. If he started in 2, then either 2 - 1 - 2 catches him if he went to 1 first. Or, if he jumps to 3, then 2 - 3 - 4 - 3 and gotcha! And if he started in 4: 4 - 3 - 4 - 3 and the hider is ours.
To minimize the search with a guarantee of maximally 6 checks, we go 2 - 3 - 4 - 4 - 3 - 2.
As for the extra credit, Seeker suggests 4 - 4 - 2 - 2 - 3 - 4 - 4 - 3 - 2. This guarantees that the bunny is trapped after at most 9 tries but on average we would only need 2.938 tries. Which is curiously less than the guaranteed-found-after-six-tries strategy, which requires 3.551 tries on average. As it is often the case in life: Good average performance comes at the cost of taking on more risk.
In case you are wondering why we post a puzzle like this: We aim to show that optimization goes far beyond the textbook problems that have been taught for decades. And that modern solvers like InsideOpt Seeker can tackle them.
The problem here is a brain teaser. Finding the best batting order on a team of baseball players has profound economic implications, though. That is our motivation: to bring optimization to applications where optimization is not used or has been dismissed before because legacy solvers were not able to tackle them.
Try out InsideOpt Seeker and you will find that there are many applications for optimization that you did not dare to dream about tackling before. They are now within the realm of the possible and can drive large value for your organization.