Archive for the ‘Puzzles’ Category.

Kyiv Olympiad, 1978

Here is a problem from the 1978 Kyiv Olympiad for 7 graders.

Is it possible to place seven points on a plane so that among any three of them, two will be at distance 1 from each other?


The Problem with Two Girls

Puzzle. Two girls were born to the same mother, at the same time, on the same day, in the same month, in the same year, and yet somehow they’re not twins. Why not?

I won’t tell you the expected answer, but my students are inventive. They suggested all sorts of scenarios.

Scenario 1. There are two different fathers. I had to google this and discovered that, indeed, it is possible. This phenomenon is called heteropaternal superfecundation. It happens when two of a woman’s eggs are fertilized by sperm from two different men. Unfortunately for my students, such babies would still be called twins.

Scenario 2. The girls are born on the same date, but not on the same day. This could happen when transitioning from the Julian to Gregorian calendar. The difference in birth times could be up to two weeks. I had to google this and discovered that twins can be born months apart. The record holders have a condition called uterus didelphys, which means that the mother has two wombs. Unfortunately for my students, such babies would still be called twins.

Scenario 3. The second girl is a clone. This scenario can potentially happen in the future. Fortunately for that student, I suspect that such babies would be called clones, not twins.

I decided to invent my own scenario outside of the actual answer, and I did.

Scenario 4. Two girls are from the same surrogate mother, but they are not twins. I had to google this and discovered that this actually happened: Surrogate mother of ‘twins’ finds one is hers.

Sometimes life is more interesting than math puzzles.


Martin Gardner’s Surprise

Martin Gardner's Surprise

In his article on Möbius strips, Martin Gardner included a cute construction.

Construction. Cut out a cross from a piece of paper. Then glue one pair of opposite ends to make a cylinder and the other pair to make a Möbius strip. Then Martin instructs, “Trisect the twisted band, then bisect the untwisted one, and open up for a big surprise!”

In my effort to reuse Möbius strips, I started making them out of zippers. So Martin’s construction had its destiny zipped. The first picture shows the construction before it is being dissected. I was quite happy with my plan to use zippers as it had its advantages over paper. For the surprise to work, the twisted band shouldn’t be cut completely. Meaning, the middle part of the Möbius strip shouldn’t be cut. I sewed my zipper monstrosity not to cause any ambiguities: there is nothing to cut, just unzip the zippers.

Little did I know that unzipping is not the issue, but zipping back up is. I tried to zip the surprise back up several times; all of them unsuccessfully, as you can see on the two other pictures. I finally had to invite the real expert — my grandson — to do it.

Martin Gardner's Surprise 2
Martin Gardner's Surprise 2


Meta Solving a Probability Puzzle

I recently posted my new favorite probability puzzle from the fall 2019 issue of Emissary, submitted by Peter Winkler.

Puzzle. Alice and Bob each have a biased coin that flips heads with probability 51% and 100 dollars to play with. The buzzer rings, and Alice and Bob begin flipping their coins once per minute and betting one dollar on each flip against the house. The bet is at even odds: each round, each of them either loses or wins a dollar. Alice always bets on heads, and poor Bob, always on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: They play the same game as above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assuming both eventually go broke, who is more likely to have lost their money first?

One might assume that Bob obviously got a bad deal. He will lose his money very fast. So the answer to both questions must be that Bob loses his money first. If you know me, you should realize that I wouldn’t have given you this puzzle if the answer was that intuitive. I love counter-intuitive puzzles.

Bob has a disadvantage, so he is guaranteed to lose eventually. Alice has an advantage, so she might lose, or she might not. If she goes broke, that means there should be more tails in the flips than if she doesn’t go broke. How does this influence the second scenario, in which they use the same coin? As we are expecting a lot of tails in the flips, the situation should be better for Bob as compared to the first scenario. Given that I posed this puzzle, one might decide that in the follow-up question Bob doesn’t go broke first. Is it a tie?

But, if Bob is the first to go broke in the first scenario, why would I include the first part of the puzzle at all? If you know me, you should wonder what makes the first question interesting. Or maybe, you know Peter Winkler, in which case you should also wonder the same thing.

I gave you enough meta information to guess the amazing counter-intuitive answers to these two questions: in the first scenario, they tie; and in the second scenario, Alice goes broke first with higher probability.

To prove that they tie in the first scenario, let me first define a switch on a sequence of coin flips. A switch changes each head into tails and vice versa. The switch creates a one-to-one correspondence between the sequences of flips where Bob goes broke with the sequences where Alice goes broke. Suppose p is the probability that Alice goes broke with a particular sequence a, and q is the probability that Bob goes broke with a `switched’ sequence b. Then p = rq, where r = (49/51)200. The reason is that sequence a has exactly 200 more tails than sequence b. The same ratio r works for any pair of switched sequences. Bob is guaranteed to go broke eventually. But to calculate the conditional probability of Alice going broke with sequence a, given that she does go broke, we need to divide the probability of the sequence a occurring by the probability that Alice goes broke. The resulting probability distribution on sequences of length n has to be the same as for Bob because it has to sum to one. If Alice goes broke, then the probability that she goes broke after n flips is the same as for Bob. That means they tie.

To answer the second question, we use the switch again. The switch creates a one-to-one correspondence between sequences of flips where Alice goes broke first and Bob second, and vice versa. The sequence for which Alice loses second has 200 more tails than the corresponding sequence where Bob loses second. Thus, in each pair of two switched sequences, the probability of the sequence where Alice loses second is equal to r times the probability of the sequence where Bob loses second. Thus, the probability of Alice winning is r times the probability of Bob winning, and r is a very small number.


Hats and Time

Here is a classical puzzle I often give to my students.

Puzzle. The sultan has three red hats and two blue ones. He wants to test his three wizards, who know his hat collection. He asks them to close their eyes and puts a hat on each of their heads. After the wizards open their eyes, they see each other’s hats, but not their own. The sultan asks each of them to guess the color of their own hat, without communicating with each other. In this particular test, the sultan only puts red hats on the wizards’ heads. Sometime after the wizards open their eyes, one of them guesses his hat’s color. How did he guess?

Here is how my students explain the solution. If a wizard sees two blue hats, he immediately knows that his hat must be red. That means, if no one immediately announces their hat’s color, at least two of them are wearing red hats. In this case, if a wizard sees one red hat, he knows that his hat must also be red. So such a wizard can guess the color of his hat. If after some more time, no one announces their hat color, all the hats worn must be red.

After the students solve the problem, I run an evil experiment on them. I show the students my two blue and three red hats and ask three volunteers to close their eyes. Then, I put two red hats and one blue hat on their heads, and the blue hat goes on the fastest thinker in the group. I did this experiment many times. Half the time, the fastest thinker overestimates how fast the other students think and guesses, mistakenly, that s/he is wearing the red hat. Gotcha!

After the experiment, we discuss what is really going on in this puzzle. This is how I start my class on common knowledge.


Fish Puzzle

Fish Puzzle

Here is a famous matchstick puzzle based on the given picture.

Puzzle. Can you move three matchsticks to turn the fish around?

Here is my bonus puzzle.

Bonus Puzzle. Can you turn the fish by moving two matchsticks?


2013 MIT Mystery Hunt

I usually collect puzzles related to math after each MIT mystery hunt. I just discovered that I never reviewed the 2013 hunt, though I started writing the post. Plus, I knew the puzzles of that year better than other year’s puzzles: I was on the writing team. Not to mention, the hunt had some real gems.

I start with mathematical puzzles:

  • In the Details by Derek Kisman. This is one of my favorite puzzles ever involving evil fractal word search. I even posted the puzzle and the solution on my blog.
  • Integers and Sequence by me. I used my number gossip database to include cool facts about numbers. The numbers form sequences, as hinted by the title. (The title had a typo: sequences should be plural.)
  • Permuted by Victoria de Quehen, David Roe, and Andrew Fiori, with illustrations by Kiersten Brown, Turing machine by Adam Hesterberg, and ideas from Daphna Harel and David Farhi. The puzzle has many mini puzzles related to different areas of mathematics.
  • Basic Alphametics by David Farhi and Casey McNamara. I love this puzzle and often give it to my students.
  • 50/50 by Derek Kisman; server by Ben Buchwald. This is a multi-layered statistics puzzle with a fantastic design and should be included in statistics books. It was the most difficult puzzle of the hunt. Unfortunately, the link is broken, but luckily, I blogged about this puzzle.

Logic puzzles:

  • Color Sudoku by Byon Garrabrant and Tanya Khovanova.
  • Turnary Reasoning by Timothy Chow, Alan Deckelbaum, and Tanya Khovanova. The puzzle looks like a mixture of chess, checkers, and Magic the Gathering.
  • Paint-by-Symbols by R.M. Baur, based on an idea by Eric Wofsey. As the name suggests, this is a paint-by-numbers puzzle.
  • Time Conundrum by David Farhi. Many people loved this puzzle.
  • Portals by Palmer Mebane. Ten interconnected Nikoli-type logic puzzles. It is a very difficult puzzle with a fantastic design; I immensely enjoyed testing it.
  • Random Walk by Jeremy Sawicki. Another Nikoli-type masterpiece that I enjoyed.
  • Lineup by Charles Steinhardt and Palmer Mebane. Another paint-by-numbers with a twist.
  • Agricultural Operations by Palmer Mebane, based on an idea by Dan Zaharopol. Kenken with a mathematical twist. It might be the most mathematical puzzle in the hunt, a masterpiece that I greatly enjoyed.
  • Lojicomix by Robyn Speer and Alex Rozenshteyn; art by DD Liu.

Computer science puzzles:

  • This Page Intentionally Left Blank by Dan Gulotta, with some help from Robyn Speer. Another puzzle worthy of textbooks: It covers different ways how information can be hidden.
  • Halting Problem by Dan Gulotta. You have to analyze programs in different languages: the programs are designed to run for a VERY LONG time.
  • Evolution by Karen Rustad; idea and some screenshots by Asheesh Laroia. A puzzle about email clients.
  • Git Hub by Robyn Speer. A git repository puzzle.
  • Call and Response by Asheesh Laroia, Glenn Willen, and Charles Steinhardt. You are given only an IP address.

Crypto puzzles:

  • Infinite Cryptogram by Anders Kaseorg.
  • Security Theater by Sean Lip. I enjoyed this puzzle that uses various ways to encrypt information.
  • Open Secrets by Tanya Khovanova and Robyn Speer. A puzzle with many famous ciphers.
  • Caesar’s Palace by Jason Alonso, with casino-formatting by Robyn Speer, clue phrase by Adam Hesterberg. An encrypted crossword which I greatly enjoyed.
  • Famous Last Letters by David Farhi. Another encrypted crossword.

Word puzzles:

  • Split the Difference by R.M. Baur and Eli Bogart. A puzzle with cryptic clues, which I enjoyed.
  • Mind the Gaps by R.M. Baur and Eli Bogart. You are given an empty rectangular grid without black cells and cryptic crossword clues.
  • Changing States by Charles Steinhardt, Robyn Speer, and David Roe. A lovely easy puzzle which I enjoyed tremendously.
  • Wordplay by Ken Fan, Matt Jordan, Tanya Khovanova, Derek Kisman, and Ali Lloyd. You are given grouped cryptic clues.
  • Plead the Fifth by Eli Bogart and R.M. Baur, based on an idea by Eric Wofsey. An elegant puzzle with several AHA moments.
  • CrossWord Complex by Robin Baur, Eli Bogart, and Jeff Manning. The puzzle consists of six crosswords that turn into serious mathematics.
  • Ex Post Facto by Derek Kisman; idea by Tom Yue. An inventive multi-layered crossword, which I greatly enjoyed.
  • The Alphabet Book by Halimeda Glickman-Hoch and Robyn Speer, based on an idea by Bryce Herdt. Loved it.
  • Funny Story by Lilly Chin, Eric Mannes, and Jenny Nitishinskaya.
  • Loss By Compression by Charles Steinhardt and Robyn Speer. A cool puzzle.
  • A Regular Crossword by Dan Gulotta, based on an idea by Palmer Mebane. A hexagonal crossword with regular expressions as clues.
  • A Set of Words by David Farhi. You are given several boggle grids. I loved this puzzle very much.
  • Czar Cycle by Yasha Berchenko-Kogan. This is a weird puzzle that uses English, Russian, and Greek alphabets.

Misc puzzles:

  • Substance Abuse by David Reiley and Timothy Chow, with assistance from Jill Sazama, Shrenik Shah, and Glenn Willen.
  • Puzzle-Regarding Vehicle by Katie Steckles, Paul Taylor, and Ali Lloyd. An interesting and difficult puzzle.
  • A Walk Around Town by Sean Lip, Ludwig Schmidt, and Freddie Manners, with help from Mary Fortune and Jonathan Lee. The puzzle looks like a walk around town but has more to it. The idea is awesome.
  • Something in Common by Dan Gulotta and Tanya Khovanova.
  • Too Many Seacrest by Robyn Speer. A cool and funny puzzle.
  • Analogy Farm by Robyn Speer, Adam Hesterberg, and Alan Deckelbaum; additional code by Anthony Lu and John Stumpo. A superb analogy game. I loved it so much that after we solved it, I came back and resolved it myself. I am not sure it works anymore, though.
  • I Can See For Miles by David Roe, based on an idea by Charles Steinhardt. You are given aerial views of buildings. I usually do not like puzzles that involve googling, but using google maps in this puzzle made me feel like I am flying around the world.

Other puzzles I worked on:

  • Cambridge Waldo by Tanya Khovanova starring Ben Buchwald, Adam Hesterberg, Yuri Lin, Eric Mannes, and Casey McNamara. The goal of this puzzle was to allow a chance for people to go for a walk around Cambridge. I am not sure we were successful: it could be that people used Google street-views to solve this puzzle.
  • Lost in Translation Gaetano Schinco, Natalie Baca, and Tanya Khovanova. You are given tangrams.
  • Linked Pairs by Herman Chau and Rahul Sridhar, with crosswords by Adam Hesterberg, Dan Gulotta, and Jenny Nitishinskaya, Manya Tyutyunik, and Tanya Khovanova. You are given three crossword grids, each with two sets of clues.
  • Magic: The Tappening by John Wiesemann, with help from Dan Gulotta and Tanya Khovanova.

Archimedes Helps Again

Below, you can find a lovely problem from the 2016 All-Russian Olympiad suggested by Bogdanov and Knop. I took some liberties translating it.

Problem. King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, …, 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?

And a bonus question from me.

Bonus. Add one more weighing to prove the weight of three more ingots.


Happy 2022!

2022 is abundant, composite, even, evil, square-free, and untouchable.

In addition, 2022 is the smallest number n such that n, n+1, n+2, and n+3 have the maximal exponents in prime factorization equal 1, 2, 3, and 4 correspondingly. Indeed, 2022 = 2·3·337, 2023 = 7·172, 2024 = 23·11·23, and 2025 = 34·52.

Problem. The numbers 22021 and 52021 are expanded, and their digits are written out consecutively on one page. How many total digits are on the page?


A Power Problem

Problem. For how many prime numbers p, the expression 2p + p2 is a prime?