Archive for the ‘Puzzles’ Category.

Thinking Inside and Outside the Box

The most famous thinking-outside-the-box puzzle is the Nine-Dots puzzle. This puzzle probably started the expression, “To think outside the box”. Here is the puzzle.

Puzzle. Without lifting the pencil off the paper, connect the nine dots by drawing four straight continuous lines that pass through all the dots.

9 dots puzzle

Most people attempt something similar to the picture below and fail to connect all the dots.

9 dots non solution

They try to connect the dots with line segments that fit inside the square box around the dots, mentally restricting themselves to solutions that are literally inside the box.

To get to the correct solution, the line segments should be drawn outside this imaginary box.

9 dots solution

Do you think that four line segments is the best you can do? Jason Rosenhouse showed me a solution for this puzzle that requires only three lines. Here, the outside-the-box idea is to use the thickness of the dots.

9 dots solution with three lines

This and many other examples of thinking outside the box are included in my paper aptly titled Thinking Inside and Outside the Box and published in the G4G12 Exchange book.

A section of this paper is devoted to my students, who sometimes give unexpected and inventive solutions to famous puzzles. Here is an example of such a puzzle and such solutions that aren’t in the paper because I collected them after the paper was published.

Puzzle. Three men were in a boat. It capsized, but only two got their hair wet. Why?

The standard answer is the following: One man was bald.

Lucky for me, my creative students suggested tons of other solutions. For example,

  • One man was wearing a waterproof helmet.
  • The boat capsized on land, and two men had their hair already wet.

My favorite example, however, is the following.

  • One man didn’t have a head.

Share:Facebooktwitterredditpinterestlinkedinmail

A Logic Puzzle about Sophists

I love knights-and-knaves puzzles: where knights always tell the truth, and knaves always lie. The following puzzle has a new type of person: a sophist. A sophist only makes statements that, standing in their place, neither a truth-teller nor a liar could make. For example, standing next to a liar, a sophist might say, “We are both liars.” Think about it. If the sophist was a truth-teller, then the statement would have been a lie, thus creating a contradiction. If the sophist was a liar, the statement would be true, again creating a contradiction.

Here is the puzzle with sophists. And by the way, this one is intended for sixth graders.

Puzzle. You are on an island inhabited by knights, knaves, and sophists. Once upon a time, a sophist made the following statements about the island’s inhabitants:
1. There are exactly 25 liars on this island.
2. There are exactly 26 truth-tellers on this island.
3. The number of sophists on this island is no less than the number of truth-tellers.
How many inhabitants were on the island once upon that time?

I love this new sophist character in logic puzzles, but I have no clue why they are called sophists. Can anyone explain this to me?

Share:Facebooktwitterredditpinterestlinkedinmail

Brick Puzzle

After reading my post, Shapovalov’s Gnomes, Grant, one of my readers, directed me to the Brick puzzle from Section 2.3 of Xinfeng Zhou’s A Practical Guide to Quantitative Finance Interviews.

Puzzle. Can you pack 53 bricks with dimensions 1-by-1-by-4 into a 6-by-6-by-6 box?

The solution in Zhou’s book has some flaws. So I am posting my own solution here.

Solution. We start with a sanity check. The box contains 216 unit cube cells, and 53 bricks would take up 212 cells. So there is no contradiction with the volume. We need to look at something else.
Let’s divide the box into 27 smaller 2-by-2-by-2 boxes and color the smaller boxes in a checkerboard manner. We get 13 boxes of one color, say white, and 14 boxes of another color, say black. Whichever way we place a brick inside the original box, it has to cover 2 white cells and 2 black cells. But we have a total of 104 white cells, which is only enough for 52 bricks.

Share:Facebooktwitterredditpinterestlinkedinmail

Cool New Coin Problems

Alexander Gribalko designed a new coin problem, two versions of which appeared at the 43rd Tournament of the Towns. I will start with the easier version.

Problem. Alice and Bob found eleven identical-looking coins; four of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob four specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eleven coins for weighing purposes.

Surprisingly, the more difficult version has fewer coins.

Problem. Alice and Bob found eight identical-looking coins; three of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob three specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eight coins for weighing purposes.

Share:Facebooktwitterredditpinterestlinkedinmail

More Gnomes

I recently posted a cute Shapovalov’s puzzle about gnomes. Here is another easier gnome puzzle, also by Alexander Shapovalov.

Puzzle. All gnomes are knights or knaves: knights always tell the truth, and knaves always lie. There is a gnome on every cell of a 4 by 4 chessboard. It is known that both knights and knaves are present in this group. Every gnome states, “Among my neighbors, the number of knaves is the same as the number of knights”. How many knaves are there, if by neighbors they mean orthogonally adjacent gnomes?

The next gnome puzzle has a different author, Alexander Gribalko. Gnomes in this puzzle are not knights or knaves but rather friendly and polite beings.

Puzzle. Nine gnomes repeated the following procedure three times. They arranged themselves on a 3 by 3 chessboard with one gnome per cell and greeted all their orthogonal neighbors. Prove that not all pairs of gnomes greeted each other.


Share:Facebooktwitterredditpinterestlinkedinmail

Shapovalov’s Gnomes

Here is another lovely problem from a prolific problem writer, Alexander Shapovalov.

Problem. Every cell of a 7 by 7 chessboard has a gnome standing on it. For every pair of gnomes whose cells share an edge, their beards’ lengths differ by no more than 1 inch. Now, we take these gnomes and sit them around a table. Prove that we can do so in a way that any two gnomes sitting next to each other have their beards’ lengths differ by no more than 1 inch.

A standard chessboard is 8 by 8. Why would this problem have a 7 by 7 board? Let’s see.

For even-sized boards, the problem is easy. I will explain why, but first, let me construct a graph related to a board, in this case, any board.

Each cell is a vertex, and two vertices are connected by an edge if the corresponding cells are orthogonal neighbors (share an edge) on the board. A cycle that goes through a graph and visits every vertex exactly once is called a Hamiltonian cycle. A Hamiltonian cycle is a potential way to sit the gnomes around the table and solve the problem. When we sit the gnomes in a circle following a Hamiltonian cycle, two neighbors at the table are also neighbors on the board, and so they have their beards’ lengths differ by no more than 1 inch.

The problem is easy for even-sized boards because it is easy to draw a Hamiltonian cycle on them. An odd-sized chessboard can’t have a Hamiltonian cycle. To prove this, let me color the board in a checkerboard manner. Then, cells that share an edge are different colors. And you can’t make a cycle through the board, where you switch colors at each step, but the total number of steps is odd.

It follows that for odd-sized boards, it is impossible to solve the problem by just connecting neighboring cells on the board. There should be another way. Can you find it?

Share:Facebooktwitterredditpinterestlinkedinmail

The Books for My Dog

I want to discuss a problem from a test I gave recently.

Problem. My dog, Fudge, likes books. He brought two books to his corner in the morning and three more books in the evening. How many books will he read tonight?

As I expected, many students didn’t pay attention and just summed up the two numbers in the problem and gave five as the answer. Here are three answers that I especially liked.

Answer 1. Zero, because most dogs can’t read.

This cautious student added most to be on the safe side.

Answer 2. You cannot tell how many books he will read. Just because he brings books to his corner doesn’t mean he will read them.

The second answer demonstrates great logical thinking, were Fudge a human. But the third answer made me laugh.

Answer 3. Three. If he brought three more books to his corner in the evening, it means he finished the two from that morning, so there are three books left for him to read.

Share:Facebooktwitterredditpinterestlinkedinmail

I Will Be Hanged

Here is an old goodie.

Puzzle. A criminal is sentenced to death. He is offered the last word. He is allowed to make one statement. If the statement is true, the criminal will be electrocuted. If the statement is false, he will be hanged. Can you find a good piece of advice for this man?

The standard answer to this puzzle is for the criminal to say, “I will be hanged.” This creates a paradox. If he is hanged, the statement is true, and he should be electrocuted. If he is electrocuted, the statement is false, and he should be hanged.

Thinking about it, any paradox works. If the man says, “This statement is false,” then the type of punishment he gets can’t be determined.

Thinking about it some more, asking a question instead of making a statement will confuse his executioners all the same.

One of my students advised the criminal to stay silent. This was not my favorite solution, as staying silent requires some concentration. My favorite solution was the statement, “It will rain exactly a thousand years from now.” This way, the criminal can relax, at least for a thousand years.

Share:Facebooktwitterredditpinterestlinkedinmail

Scooter Ideas

Today I discuss ideas for solving the puzzle I posted previously in my blog: A Scooter Riddle.

Riddle. Alice, Bob, and Charlie are at Alice’s house. They are going to Bob’s house, which is 33 miles away. They have a 2-seat scooter that goes 25 miles per hour with 1 rider, or 20 miles per hour with 2 riders. Each of the 3 friends has a walking pace of 5 miles per hour. What is the fastest time that all three of them can end up at Bob’s house?

Let’s start.

  • The scooter and the three people should always be on the move. Moreover, whenever the scooter moves towards Bob’s house, it should carry two people, and only the driver should be on the scooter whenever it is going back.
  • We do not care about each individual’s path: whenever people meet at the same place at the same time, we can swap them. Therefore, we can assume that the scooter’s driver is the same person at all times.
  • Thinking about it, we can ignore the scooter’s driver and assume that the scooter is self-driving, and there are only two people, Alice and Bob, who need to get to Bob’s house.
  • If Alice and Bob arrive at Bob’s house at different times, there is room for improvement: the fastest person should have used the scooter less and walked more, allowing the other person more use of the scooter. Hence, we can assume that they arrive at Bob’s house simultaneously.
  • Without loss of generality, we can assume that Alice starts on the scooter first.
  • So the scooter should carry Alice for some time, drop her off, come back for Bob, then drop him off, come back for Alice, and so on. Without loss of generality, we can combine all scooter trips by the same person into one ride.
  • Thus, the plan is the following. The scooter drives Alice for x hours, drops her off, and she finishes on foot. Meanwhile, Bob starts on foot. The scooter goes back after dropping off Alice, picks up Bob, and drives him x hours the rest of the way.

Now this is just algebra. Each person covers 20x miles on the scooter and 33 − 20x miles on foot. The walking takes 33/5 − 4x hours. Thus the total trip for each person takes 33/5 − 3x hours.

Now we calculate what the scooter does. The scooter covers 20x miles with Alice and the same number of miles with Bob. It covers 40x − 33 miles alone. Thus the scooter spends 2x + (40x − 33)/25 hours in transit. The two times must be the same. So we have an equation: 6.6 − 3x = 2x + 1.6x − 1.32. Thus, x = 1.2, and the answer to the puzzle is 3 hours.


Share:Facebooktwitterredditpinterestlinkedinmail

Looking for a Well-Educated Gentleman

If you can figure out my number without the Internet, call me.

  • The number of letters in the first name of Anna Karenina’s love.
  • The number of times the word nevermore appears in the famous poem, subtracted from the month when the events took place.
  • The only number in the title of a Bergman movie.
  • The number of vowels in the original and more historically meaningful name for the sorcerer’s stone in Harry Potter books.
  • The number of vertices of the other geometric shape in “Girl on a Ball”.
  • The cube root of the age mentioned in one of the earliest Beatles songs.
  • The number corresponding to the lexicographically first string representing an integer in English.
  • The first digit of the age at which Pushkin and Mozart died.
  • The smallest of two primes such that their sum and difference are also prime.
  • The only triangular number that is also prime.

(Just in case: this is a joke and not my actual phone number.)


Share:Facebooktwitterredditpinterestlinkedinmail