Archive for the ‘Puzzles’ Category.

Hanged or Electrocuted?

Here is a standard logic puzzle:

A criminal is sentenced to death. He is allowed to make one last statement. If the statement is true, the criminal will be sent to the electric chair. It the statement is false, he will be hanged. Can you suggest a good piece of advice for this man?

I can offer many pieces of advice to this man. The simplest thing is to keep silent. Or he can communicate without making statements, like asking, “Can I have some crème brûlée, please?”

One can argue that the puzzle implies that it’s a favor to allow the prisoner to make a last statement, but without it he will die anyway. In this case the standard piece of advice to this man would be to create a paradoxical situation by saying, “I will be hanged.”

Another, less standard, idea is to state something that is very difficult to check. For example, to give the exact number of planets in our galaxy, or posit that P = NP. My son, Sergei, suggested saying that “Schrödinger’s cat is dead.”

But the most popular idea among my AMSA students is to say, “I am sorry.” I’m not 100% sure that they mean it as a statement that is impossible to check. Maybe they think that these words can do magic and save lives. Or maybe it could be the best thing for a criminal to say before dying.

Share:Facebooktwitterredditpinterestlinkedinmail

What’s Hidden?

Anyone knows that sometimes the text is not exactly what it seems to be. There are many different simple ways to hide a secret message inside your text. So, your humble blogger decided to run an experiment. How should we go about it? I decided to hide a secret message inside this short essay. Do you see it? Do you notice that my text is artificially adjusted for some extra purpose? Everyone can feel that this text sounds different than my usual postings. Nothing should stop you from solving this puzzle now.

Share:Facebooktwitterredditpinterestlinkedinmail

Linear Algebra for Pirates

I’ve got this puzzle from Nick Petry.

Captain Flint is dying. All his treasures are buried far away. He only has 99 pieces of gold with him. Filled with remorse at the last moments of his life, he decides that he only wants to take one piece of gold with him to his grave. The rest of the gold he will give to the families of two men that he had killed the day before.

Though Captain Flint is heavily drunk he notices that no matter which piece he takes for himself, he can divide the leftover 98 pieces into two piles of 49 pieces each of the same weight. Prove that all the gold pieces are of the same weight.

For an additional challenge, Sasha Shapovalov suggested the following generalization of the previous puzzle.

Captain Flint has N gold pieces and yesterday he killed not two but K men. He wants to take one piece with him to his grave and to divide the rest into equi-weighted piles, not necessarily of the same number of pieces. If he can choose any piece to take with him and is able to divide the rest, prove that N – 1 is divisible by K.

Both of these puzzles can be easily solved if the weight of every gold piece is an integer or even a rational number. If you don’t assume that the weights are rational numbers, then I do not know an elementary solution, but I do know a simple and beautiful solution using linear algebra for both puzzles.

Even pirates need linear algebra to divide their treasure. Hooray for linear algebra!

Share:Facebooktwitterredditpinterestlinkedinmail

Library Puzzle

Here is a logic puzzle for kids:

— John has more than a thousand books, said Pete.
— No, he has less than one thousand books, said Ann.
— Surely, he has at least one book, said Mary.

If only one statement is true, are you sure you know how many books John has?

Share:Facebooktwitterredditpinterestlinkedinmail

Four Puzzles for the Price of One

Here is a math problem from the 1977 USSR Math Olympiad:

Let A be a 2n-digit number. We call this number special if it is a square and a concatenation of two n-digits squares. Also, the first n-digit square can’t start with zero; the second n-digit square can start with zero, but can’t be equal to zero.

  • Find all two- and four-digit special numbers.
  • Prove that there exists a 20-digit special number.
  • Prove that not more than ten 100-digit special numbers exist.
  • Prove that there exists a 30-digit special number.

Obviously, these questions are divided into two groups: show the existence and estimate the bound. Furthermore, this problem can be naturally divided into two other groups. Do you see them? The puzzle about special numbers makes a special day today — you get a four-in-one puzzle.

Share:Facebooktwitterredditpinterestlinkedinmail

A Math Puzzle that Sounds like a Computer Science Puzzle

David Bernstein gave me this puzzle. He says that the puzzle was given at a Moscow math Olympiad a long time ago. At that time there were no computer science olympiads yet. I do not know why this puzzle feels to me like computer science. Maybe because the trivial solution is of order N, the easy solution is of order square root of N and the requested solution is of order logarithm of N:

Can you cut a square into N convex pieces minimizing the number of possible intersections of any straight line with your pieces?

It is easy to maximize the number of intersections. If you cut your square with N-1 parallel cuts into N equal thin rectangles, then there exists a line with N intersections.

It is easy to cut a square to guarantee no more than 2√N intersections. Can you cut your square so that any line makes no more than 2log2N intersections?

Share:Facebooktwitterredditpinterestlinkedinmail

Linear Algebra at a Math Olympiad

A puzzle from the 1977 USSR math Olympiad can be solved naturally with linear algebra:

Seven dwarfs are sitting at a round table. Each dwarf has a cup partially filled with milk. Each dwarf in turn divides all his milk evenly between the six other cups. After the seventh dwarf has done this, every cup happens to contain the initial amount of milk. What was the initial distribution of milk?

Can you use linear algebra to intelligently solve this puzzle?

Share:Facebooktwitterredditpinterestlinkedinmail

The Polynomial Game

This puzzle is a generalization of a problem from the 1977 USSR math Olympiad:

At the beginning of the game you are given a polynomial, which has 1 as its leading coefficient and 1 as its constant term. Two people play. On your turn you assign a real value to one of the unknown coefficients. The person that goes last wins if the polynomial has no real roots at the end. Who wins?

It is clear that if the last person’s goal is for the polynomial to have a root, then the game is trivial: in this case, he can always make 1 a root with the last move. Also, an odd degree polynomial always has a real root. Therefore, to make the game interesting we should assume that the degree of the polynomial is even.

Though I can’t imaging myself ever being interested in playing this game, figuring out the strategy is a lot of fun.

Share:Facebooktwitterredditpinterestlinkedinmail

Recounting Cats

Here is a math puzzle for kids from a nice collection of ThinkFun Visual Brainstorms:

Wendy has cats. All but two of them are Siamese, all but two of them are Persian, and all but two of them are Maine Coon. How many cats does Wendy have altogether?

This puzzle has two answers: the expected answer and an unexpected answer. Can you find both?

Share:Facebooktwitterredditpinterestlinkedinmail

An Organic Puzzle

Here is a puzzle that my ex-brother-in-law, Dodik, gave to me today:

Prove that every group with more than two elements has a non-trivial automorphism.

I usually love puzzles that are solved with a counter-intuitive brilliant idea. This puzzle is different — I didn’t solve it in one elegant swoop. But I still love the puzzle: it feels so natural, and it’s solution feels so natural, that I even decided to call this puzzle “organic.” Or, maybe, I am just in an organic mood today waiting for my organic bananas to be delivered from Boston Organics.

Share:Facebooktwitterredditpinterestlinkedinmail