Climbing Trees and Solving Puzzles

Here are some cool puzzles where thinking using binary trees helps solving them easily.

Puzzle 1:

What is the minimum number of comparisons required to sort three distinct numbers?

Solution:

There are six ways of arranging three numbers and one of these six will have the numbers sorted in the correct order.

The comparisons can be drawn up as a binary tree. Each comparison gives us two possible outcomes. So we need at least n comparisons where 2^n >= 6. It is easy to see that 3 is that n.

(And the straightforward, obvious algorithm shows that indeed 3 comparisons are sufficient.)

Puzzle 2:

There are three switches, all in the off position. One of these is connected to a light bulb upstairs. You have to determine which switch operates the bulb. The catch is that you can go upstairs and check only once. How do you do it?

Solution:

For sure this is an interesting question. Let us see what our tree analysis can tell us about this.

Now there are three possible outputs - switch 1, 2 or 3. The light bulb can be in two states - on or off. That does not give us enough states to point to three outputs. (2^1 = 2 < 3).

Based on our tree analysis, we need at least 2 states to nail down the switch.

So right away you can see that just by checking if the bulb is on or off you are not going to be able to determine the light switch.

So what other state information can the bulb provide? How about time? If the bulb was on for longer versus for a shorter time?

Possible, but you can't really look at a light bulb and say how long it has been on.

But, you can touch it and tell - yes, by how hot it is. (Okay, there are limits to how accurately you can measure the heat and how long interval you can measure. If you leave the bulb on for a long time, it comes into thermal equilibrium and doesn't get any hotter.)

Now you have two states, on/off and hot/cold. And indeed you can find out which switch operates the bulb.

1. Turn on switch 1. Keep for 5 min. Turn off switch 1.
2. Turn on switch 2.

Go upstairs and check.

1. If bulb is on, switch 2 operates it.
2. If bulb is off and hot, switch 1 operates it.
3. If bulb is off and cold, switch 3 operates it.

Now comes the teasers. Can we use a similar algorithm if there were four switches? Theoretically, we have enough number of states to make that determination.

What say?

Puzzle 3:

How many straight cuts are required to cut a cube into 27 smaller cubes, in a 3x3x3 array as in a rubik's cube? A straight cut is defined as a single, simple cut with a knife where the knife edge moves in a straight line. You are allowed to rearrange the pieces between cuts.

Solution:

Each straight cut can create two pieces. So in order to create 27 cubes, we need at least n cuts where 2^n >= 27. So we need at least 5 cuts.

But is 5 sufficient?

We know the "obvious" way of cutting the cubes in 6 cuts - two parallel to each axis.

So we know that the answer is between 5 and 6 cuts.

In order to resolve this, we notice that each cut also exposes two new surfaces.

Consider the innermost cube - it has 6 fresh cut surfaces. And since only straight cuts are allowed, we need 6 cuts to create this cube.

Thus the answer is 6.