Tricky Logic Puzzle (VII) – How To Really Solve It?

Welcome to the latest entry in the tricky logic puzzle series. This puzzle entry requires you to flex your algorithmic reasoning skills.

The story begins one fine day, when Cheat discovers a mysterious box. Inside this box are two feeble looking opaque glass boxes and one mysterious note.

The opaque glass boxes look like they could break any second. The mysterious note besides them reads as follows:

The finder of this box shall take the two special boxes to the specified location. The finder shall then climb the 100 storey building at this location.

There exists a specific floor in this building from which the two special boxes may be dropped without them breaking. If any of these boxes is dropped from a floor above this floor, they would break.

However, the boxes may be dropped from any floor below this floor and they will sustain no damage. Consequently, they may be dropped again.

The finder’s task is as follows:

1. Figure out the highest floor from which the boxes may be dropped without breaking.

2. Achieve this task by dropping the boxes as few times as possible.

If the finder is able to do these tasks successfully, he gets access to a treasure map.

On reading this, cheat gets excited and plans for his impending journey. As a strategic partner, do you think you can help cheat solve this logic puzzle?

Hint

Note that the puzzle does not demand that the feeble special boxes be intact at the end of the process. So, you may choose to break both boxes if it helps you figure out the threshold floor in as few drops as possible. All the best!

Spoiler Alert

Beyond this section, I will be explicitly discussing the solutions to this puzzle. So, if you wish to solve this puzzle on your own, I recommend that you pause reading this essay at this point and try on your own.

Once you are done with your attempt, you may continue reading this essay. Optionally, if you are looking for inspiration, you may read the next few sections involving simple (but ineffective) algorithms that try to solve this puzzle.

This essay is supported by Generatebg

---

Setting Up Expectations for the Tricky Logic Puzzle

At the outset, I’d like to state that this puzzle is surprisingly deceptive. The good news is that it allows for several approaches. So, we have the freedom to try out a few different angles to solve it.

I will begin by discussing a simple algorithm that tries to solve this puzzle but in vain. Following this, I will discuss a few progressively more advanced algorithms that build on the failures of the previous ones but still don’t cut it.

Finally, I will present the solution to this puzzle, which also happens to be the most complex algorithm that I will be covering in this essay. Without any further ado, let us begin.

The Simple Algorithm

To summarise the situation, we have two thin special boxes that each break when dropped from a particular floor (and above) out of 100 floors. Given this situation, our task is as follows:

1. Figure out the highest floor from which the boxes may be dropped without breaking.

2. Achieve this task by dropping the boxes as few times as possible.

Let us start by forgetting the second part of the task. That is, let us focus on an algorithm that helps us figure out the threshold floor first.

The key realisation for me was the fact that the boxes don’t break when they are dropped from any floor below the threshold floor. So, we may choose to drop the first box from the first floor. If it does not break, we can drop it from the second floor.

If it still does not break, we can repeat the procedure from the third floor, and so on. Using this linear approach, we are bound to eventually arrive at the floor at which the first box breaks. Consequently, the floor directly beneath this one would be the threshold floor.

This approach helps us figure out the threshold floor, but suffers from a couple of issues:

1. If the threshold floor is ’n’, we need to drop the first box (n + 1) times. That is if the threshold floor is 99, we need to drop the first box 100 times.

2. We don’t even use the second box, which makes this approach terribly inefficient.

So, why don’t we look for a better approach?

Binary Search + Linear Search

Attacking this puzzle from a computer science point of view, my next approach was to combine linear search with binary search. We have a total of 100 floors. We could drop the first box from floor number 50 (100 ÷ 2).

If the box breaks, then we know for sure that the threshold floor belongs to the first 50 floors. If the box does not break, then we know that the threshold floor belongs to the second 50 floors.

That is, we have reduced our search field to one-half of the original field. But the next part becomes tricky. Say that the first box breaks when dropped from floor number 50. In a conventional binary search, we would divide 50 by 2, and drop the second box from floor number 25.

If the second box still does not break, we would repeat this logic. But if it does break, we can never know which floor is the threshold floor. So, we cannot follow the binary search algorithm with the second box.

Consequently, we are forced to go linear. That is, if the first box breaks at floor number 50, we start dropping the first box from floor number 1 upwards, one by one until we reach the threshold floor plus one (where the second box breaks).

If the threshold floor were floor number 99, using this approach you would need 51 drops. This is an improvement compared to our last approach. But we can still do better.

The Linear Leap Approach to Solve the Tricky Logic Puzzle

In this approach, we drop the first box from floor 10. If it does not break, we move 10 floors up, and drop it again from floor 20, and so on. Let us now say that the first box breaks when dropped from floor number 80.

Then, we know for sure that the threshold floor is somewhere between floor number 70 and floor number 80 (not including floors 70 and 80). At this point, we may just drop the second box from floor number 71, one by one upward linearly.

If the threshold floor were floor number 99, using this approach we would use 10 drops using the first box (as we drop in steps of 10 up to floor number 100). Then, we would drop the second box from each floor starting from 91 upwards. In total, we would use up 19 drops.

To summarise, for a hypothetical threshold of floor number 99, we started from 100 drops with the simple linear algorithm, then reduced it to 51 drops by combining it with binary search, and are now at 19 drops using a linear leap approach.

The big question is: can we reduce the drop count even further? The answer is: yes!

---

The Solution to the Tricky Logic Puzzle — Series Leaps

This approach happens to involve the most complex algorithm yet. However, this also happens to be the most satisfying algorithm as well. So, buckle up.

We start by dropping the first box from an arbitrary floor number, say x. If the box does not break, we then leap (x − 1) floors up and repeat the exercise. If the box does not break yet again, we leap (x − 2) floors up, and so on.

This is just an extension of the previous approach. Let us say that x = 10. Then, we drop the first box initially from the 10th floor. If it does not break, we move 9 floors up (10 − 1) and drop it again. If it does not break yet again, we move 8 floors up (10 − 2), and so on.

Why is this better? Well, this approach minimises the linear drops we have to test with the second box. The previous algorithm held the leap step at 10 with the first box and made us jump one floor up each time with the second box.

This approach reduces the leap step each time by 1, thereby reducing the number of floors we have to linearly traverse using the second box. To figure out what the optimal starting floor (x) is, we only need to solve the following equation:

x + (x − 1) + (x − 2) + (x − 3) + … + 1 = 100

If you look at the left-hand side of this equation, you might note that this is nothing but the sum of ‘x’ numbers. Replacing this series with its more compact form, we get our solution as follows:

Let us now fix x = 14 for 100 floors. If the threshold floor were floor number 99, we would need 14 drops to figure it out. In fact, regardless of which floor the threshold floor is, we would need only 14 drops. Here is a chart that illustrates this fact:

There we go. You just helped Cheat solve this tricky logic puzzle. I hope you had fun in the process.

If you are curious about Cheat’s journey beyond this point, keep an eye on this space. As a bonus, you are sure to come across more logic puzzles in the future as well!

---

If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you:

• How To Really Solve The Monkey And The Coconuts Puzzle?
• How To Really Solve This Fun Geometry Puzzle?
• How To Actually Solve The Königsberg Bridge Problem?

If you would like to support me as an author, consider contributing on Patreon.

Reference and credit: Simply Logical.