Logical Puzzles

Today’s Topic is dedicated to a special topic, logical puzzles. These puzzles have always fascinated me and I can’t help but try to solve them.

During one of the job interviews I had, the interviewer gave me a logical puzzle out of curiosity. After thinking about it, I can’t seem to derive the correct conclusion.

After the interview, I asked him about it and it turns out I just missing a logical step. I was so close to the answer but I just couldn’t see it.

So that experience led me to this blog post

The history of logical puzzles #

Logical puzzles were first introduced in the 19th Century by Charles Lutwidge Dodgson, better known as Lewis Carroll (His pen name).

In his book, he introduced a game to solve problems using logic given a set of premises. A simple example will be sudoku, where the solver must derive the numbers in a 9 by 9 grid using the rules of sudoku.

Rules of Sudoku:

1. Each row must contain the numbers 1 to 9
2. Each column must contain the numbers 1 to 9
3. Each predefined 3 by 3 grid must contain the numbers 1 to 9

Just by following this set of rules and using logical reasoning, we can solve the puzzle.

Logical Puzzles #

Let’s just dive right in and try to solve some of the puzzles. The questions will be laid out in this section and the answers will be in the next section. If you want to try to solve it yourself, please do so before reading the answers.

The knights and the knaves #

You are travelling to the nearby town to visit your family. However, halfway through your journey, you find yourself lost at the crossroads of the K kingdom. It contains 2 identical paths to continue on. However, taking the wrong path will cause you to miss your family reunion. In order to be on your way, you will have to ask for directions to your hometown.

You try to recall what you know about K kingdom

1. The kingdom only consists of knights and knaves
2. Knights always tell the truth
3. Knave will always lie
4. Knights and Knaves dress differently but you cannot remember which is which.

Just after thinking about what to do, 2 strangers dressed very differently came to the crossroads. You stopped them to ask for directions.

As they are rushing, you only have time to ask 1 question. What will you ask to get the correct answer?

The 5 cups #

You are at a carnival booth looking around. You see a corner booth with an interesting game.

There is a sign which shows you how to play the game:

1. There are 5 cups in a row
2. Under 1 cup there is a prize
3. If you guess the cup with the prize you will win
4. You have 6 guesses
5. After each wrong guess, I will have to move the coin from 1 cup to an adjacent cup

You think to yourself and felt like you can always win the game.

What are the cups that you guess in order to guarantee the win?

The interview Puzzle #

This is the puzzle which I received during that faithful interview.

Premise:

1. There are tigers and sheep
2. There is only 1 sheep
3. There can be 1 or more tigers
4. When a tiger eats a sheep, the tiger turns into a sheep
5. The tigers want to eat the sheep while avoid being eaten as a sheep
6. The tigers a fully logical.

Questions:

1. Where there are 100 tigers, will the tigers eat the sheep?
2. What about 101 tigers?

The answers #

In this section, I will be laying down the answers to the logical puzzles above as well as the step-by-step derivation to arrive at the answer

The knights and the knaves #

In this case, we know that the knave must always lie and the knight always tells the truth. Judging from what they are wearing, we know that one of them is a knight and the other is a knave.

In order to solve this problem, we must make the knight and the knave answer the question in a way that results in the same answer.

To make them answer the same way, we can make use of questions which gauge what the other answers.

In this case, we can make use of the answer What will the other person answer to the following question: "Where is the direction to town x"?

If we ask the knight, the knight will say the truth about the knave who will lie about the direction. If we ask the knave, the knave will lie about the knight who will say the truth about the direction. At the end of the day, both of them will point in the wrong direction at the crossroad. As a result, you will know that you need to take the other road.

You are now on your way to the family reunion. Even though you do not know which is the knight and which is the knave, you know that you will be enjoying your sweet family reunion.

The 5 cups #

For this question, let us start by visualizing the moving of the cups.

_ _ _ c _ -> _ _ c _ _
1 2 3 4 5    1 2 3 4 5

For each move, we notice that the coin will move from an even number cup to an odd number cup. Is there a way to exploit this property?

Yes there is, if we guess the sequence 2,3,4,2,3,4 we are guaranteed to find the coin.

For the first 3 guesses, if all 3 of them fail, we can see that the coin can only be at 1, 3 or 5.

For the case of 1, the position of the coin will be 1, 2, 3 or 1, 2, 1.

For the case of 3, the position of the coin will be 3, 4, 5 as it out runs the guess.

For the case of 5, the position of the coin will be 5, 4, 5.

Notice that all of them ends in a odd number. During the 4th guess, all of them will have to change to an even number which the sequence 2, 3, 4 will definitely find.

You continue to play the booth many many times. The booth master had enough of the game and decided to close the booth for the day. Happy that you have won your prize, you happily made your way home.

The interview puzzle #

When we first look at the question, we might not know where to start. In this case, let us look at how the situation breaks down from 100 tigers.

If there are 100 tigers and 1 sheep, what will happen when 1 of the tigers eat the sheep?

In this case, the 100 tigers and 1 sheep will become 99 tigers and 1 sheep.

We can see from the above that the larger problem breaks down into smaller subproblems. We can solve such problems through recursion.

Base Case #

Let’s take a look at the base cases and keep track of them in a table.

When there is only 1 tiger and 1 sheep, the tiger will eat the sheep. When there are 2 tigers and 1 sheep, both tigers will not eat the sheep as they do not want to be eaten as a sheep.

By putting in the 2 base cases, this is what we get so far. Now that we have the base case, let us slowly increase the number of tigers and see what happens.

Recursive Step v1 #

The next step is to have 3 tigers and 1 sheep.

What do you think will happen then?

If there are 3 tigers, they know that each of them can eat the sheep if they eat the sheep right? Does that mean that any number of tigers above 2 will not eat the sheep??

If you are following the train of thought above, you have the same idea as me during my interview. However, there is 1 crucial step we are not looking at.

Recursive Step v2 #

We are not taking into account the previous cases which we have calculated for. We know that for 3 tigers and 1 sheep, if a tiger eats the sheep, it will transform the problem into the 2 tiger 1 sheep problem.

From the table that we had earlier, we know that if there are 2 tigers, they will not eat the sheep as they know the other tiger will eat them. In this case the third tiger who ate the sheep can eat the sheep and get away scot-free.

We can update the table and see the following

Extending from this train of thought, we can see that if the number of tigers are even, the tigers will not eat the sheep and if the tigers are odd, there will be 1 tiger who wants to eat the sheep.

Answering the question #

So to link back to the question, if there are 100 tigers, they will all not eat the sheep as they know eventually, it will be similar to the base case of 2 tigers and 1 sheep where they first eat the sheep will result in them being eaten.

However, if there is an odd number of tigers, the first tiger can safely eat the sheep as the rest of the tigers will not eat the sheep because of the paragraph above.

The tigers are sad that they might not get to eat the sheep. However, they also rest easy knowing that they will not eventually be eaten.

Conclusion #

Having that questions asked during an interview was a refreshing experience for me as it helped me realize that concepts we have learnt in school can be applied in different situations in real life if we can discover how to map them to the logical constructs we have learnt in class.

Hope you guys liked it and see you guys in the next post.

References #

• mathisfun.com
• Knights and Knave
• Logical Puzzle Wiki