Fast Thinking

How much time will it take you to answer the following question?

Can the equation 29x + 30y + 31z = 366 be solved in natural numbers?


Happy 2019!

Happy 2019, the first 4 digit number to appear 6 times in the decimal expansion of Pi.

By the way:

2019 = 14 + 24 + 34 + 54 + 64.

Also, 2019 is the product of two primes 3 and 673. The sum of these two prime factors is a square.

This is not all that is interesting about factors of 2019. Every concatenation of these two prime factors is prime. Even more unusual, 2019 is the largest known composite number such that every concatenation of its prime factors is prime. [Oops, the last statement is wrong, Jan 3,2019]

Happy Happy-go-Lucky year, as 2019 is a Happy-go-Lucky number: the number that is both Happy and Lucky.

In case you are wondering, here is the definition of Happy numbers: One can take the sum of the squares of the digits of a number. Those numbers are Happy for which iterating this operation eventually leads to 1.

In case you are wondering, to build the Lucky number sequence, start with natural numbers. Delete every second number, leaving 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, …. The second number remaining is 3, so delete every third number, leaving 1, 3, 7, 9, 13, 15, 19, 21, …. The next number remaining is 7, so delete every 7th number, leaving 1, 3, 7, 9, 13, 15, 21, …. The next number remaining is 9, so delete every ninth number, etc.


Puzzle Ninja

Puzze Ninja by Alex Bellos

Alex Bellos sent me his new book Puzzle Ninja: Pit Your Wits Against The Japanese Puzzle Masters. What has he done to me? I opened the book and couldn’t close it until I solved all the puzzles.

This is a fantastic book. There are many varieties of puzzles, including some types that I’ve never seen before. Also, the beautifully designed puzzles are great. Often puzzles of the same type target different solving ideas or have varied cool themes.

This book is more than a bunch of puzzles; it also contains poetic stories about puzzle histories and Japanese puzzle designers. Fantastic puzzles together with a human touch: this might be my favorite puzzle book.

Wolf and Sheep Slitherlink Puzzle 1

I present two puzzles from the book. The puzzle type is called Wolf and Sheep Slitherlink. The Slitherlink is a famous puzzle type with the goal of connecting some of the neighboring dots into a single non-self-intersecting loop. A number inside a small square cell indicates how many sides of the square are part of the loop. Wolf and Sheep Slitherlink is a variation of Slitherlink in which all sheep should be kept inside the fence (loop) and all the wolves outside.

Ignore the numbers in the title as they just indicate the order number of Wolf and Sheep Slitherlink puzzles in the book. The number of ninja heads shows the level of difficulty. (The hardest puzzles in the book have four heads.) The difficulty is followed by the name of the puzzle master who designed the puzzle.

The first puzzle above is slightly easier than the second. I like the themes of these two puzzles. In the first one, only one cell—lonely wolf—marks the relationship to the fence. In the second one, the wolf in the center—who needs to be outside the fence—is surrounded by a circle of sheep who are in turn surrounded by a circle of wolves.

Wolf and Sheep Slitherlink Puzzle 2


Two Dice

My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.

Problem. Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?

The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.

I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let ai (correspondingly bi) be the probabilities that die A (correspondingly B) shows i + 1. It would be very useful later that that i ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ aizi and g(z) = ∑ bizi. Then the desired result is that f(z)g(z) = ∑j=010 zj/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a5=b5=0 and the coefficient of z10 in their product is also 0, contradiction.

Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a0b0 = a5b5 = 1/11. Then the probability of a total 7 is at least a0b5 + a0b5. The geometric mean of a0b5 and a0b5 is 1/11 (from above), so their arithmetic mean is at least 1/11 and their sum is at least 2/11. Therefore, the uniform distribution for sums is impossible.

So 1/11 is impossible, but how close to it can you get?


My 1975 IMO Team

My IMO Team, 1975

I just got this picture from my friend Victor Gutenmacher, which I never saw before. My 1975 IMO team is posing at our training grounds before the Olympiad trip to Bulgaria.

Left to right: Boris Yusin, Yuri Ionin, Zoya Moiseyeva (front), Gregory Galperin (back), me, Ilya Yunus, Valentin Skvortsov, Aleksandr Kornyushkin, Sergei Finashin, Sergei Fomin (front), Alexander Reznikov (back), Yuri Shmelev (front), Yuri Neretin (back), Victor Gutenmacher.

Our coaches are in the shot as well. Surprisingly, or not surprisingly, all of them moved to the USA. Yuri Ionin, now retired, was a professor at Central Michigan University. Gregory Galperin is a professor at Eastern Illinois University. Sergei Fomin is a professor at the University of Michigan. Victor Gutenmacher worked for BBN Technologies and Siemens PLM Software, and is now retired.

There are two more adults in the picture: Valentin Anatolievich Skvortsov, our leader and Zoya Ivanovna Moiseyeva, our deputy leader. Skvortsov was working at the math department of Moscow State University at that time. The University was angry that he didn’t block some students with Jewish heritage from the team thus allowing them to be accepted to Moscow State University without exams. I wrote a story of how Zoya persuaded Alexander Reznikov not to go to Moscow University to help Valentin. It ruined Alexander’s live, and didn’t even help Valentin. 1975 was Valentin’s last trip as the leader.


An Orchestra Puzzle

An orchestra of 120 players takes 70 minutes to play Beethoven’s 9th Symphony. How long would it take for 60 players to play the symphony?Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

The Annoyance of Hyperbolic Surfaces

A hyperbolic surfaceI do not like making objects with my hands. But I lived in Soviet Russia. So I knew how to crochet, knit, and sew — because in Russia at that time, we didn’t have a choice. I was always bad at it. The only thing I was good at was darning socks: I had to do it too often. By the way, I failed to find a video on how to darn socks the same way my mom taught me.

Then I came to the US. I suddenly found myself in a rich society, where it was cheaper to buy new stuff than to spend the time doing things with my hands. So I happily dropped my craftsmanship.

After not working with my hands for 28 years, one day I needed hyperbolic surfaces for my classes and I couldn’t find any to buy. Hyperbolic surfaces are famous for providing an example when the Euclid’s Fifth axiom doesn’t work. These hyperbolic surfaces look flat locally, so you can continue a line in any given direction. If you draw a line on such a surface and pick a point that is not on the line, then you can draw many lines through the point that are parallel to the given line.

My students are more important than my dislike of crochet, so I decided to just do it myself. I asked my friend Debbie, who knows how to crochet, for advice, and she gave me more than advice. She gave me a hook and a piece of yarn and reminded me how to work the hook. She started me with a small circle. After that all I had to do was add two stitches for each stitch on the perimeter of the circle. The finished product is this green ballish thing that looks like a brain, as in the photo.

Outside the starting circle, each small surface segment of this “brain” looks the same, making the “brain” a surface of constant curvature.

I chose a ratio of 2 to 1, adding two new stitches for each previous stitch. With this ratio, my flattish surface started looking like a ball very fast. The length of the perimeter doubled for every row. Thus each new row I crocheted took the same total amount of time that I had already spent on the whole thing. All the hours I worked on this “brain,” I kept thinking: darn, it is so unrewarding to do this. Annoying as it was, the thing that kept me going was my initial decision to continue to use up all the yarn Debbie had given me. In the end, with this ratio, half the time I worked was spent making the final row.Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

3-Inflatable Permutations

We can inflate one permutation with another permutation. Let me define the inflation by examples and pictures. Suppose we have a permutation 132 which we want to inflate using permutation 21. The result is the permutation 216543 that can be divided into three blocks 21|65|43. The blocks are ordered as the first permutation 132, and within each block the order is according to the second permutation. This operation is often called a tensor product of two permutations. The operation is non-commutative: the inflation of 21 with 132 is 465132.

Inflation Definition

As one might guess this post is related to k-symmetric permutations, that is, permutations that contain all possible patterns of size k with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples of 3-symmetric permutations are 349852167 and 761258943 in size 9.

A permutation is called k-inflatable if its inflation with k-symmetric permutation is k-symmetric. One of my PRIMES projects was about 3-inflatable permutations. The result of this project is the paper On 3-Inflatable Permutations written with Eric Zhang and posted at the arxiv.

The smallest non-trivial examples of 3-inflatable permutations are in size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8, where capital letters denote numbers greater than nine. Another cool property discovered in the paper is that the tensor product of two k-inflatable permutations is k-inflatable.Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

Symmetries of k-Symmetric Permutations

I am fascinated by 3-symmetric permutations, that is, permutations that contain all possible patterns of of size three with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples are in size 9.

When I presented these examples at a combinatorics pre-seminar, Sasha Postnikov suggested to draw the permutations as a graph or a matrix. Why didn’t I think of that?

Below are the drawings of the only two 3-symmetric permutations of size 9: 349852167 and 761258943.

3-Symmetric Permutations

As I already mentioned in the aforementioned essay the set of 3-symmetric permutations is invariant under the reversal and subtraction of each number from the size of the permutation plus 1. In geometrical terms it means reflection along the vertical midline and central symmetry. But as you can see the pictures are invariant under 90 degree rotation. Why?

What I forgot to mention was that the set of k-symmetric permutations doesn’t change after the inversion. In geometrical terms it means the reflection with respect to the main diagonal. If you combine a reflection with respect to a diagonal with a reflection with respect to a vertical line you get a 90 degree rotation. Overall, the symmetries of the k-symmetric permutations are the same as all the symmetries of a square. Which means we can only look at the shapes of the k-symmetric permutations.

There are six 2-symmetric permutations: 1432, 2341, 2413, 3142, 3214, 4123. As we can see in the picture below they have two different shapes.

2-Symmetric Permutations

Here is the list of all 22 2-symmetric permutations of size 5: 14532, 15342, 15423, 23541, 24351, 24513, 25143, 25314, 31542, 32451, 32514, 34152, 34215, 35124, 41352, 41523, 42153, 42315, 43125, 51243, 51324, 52134. The list was posted by Drake Thomas in the comments to my essay. Up to symmetries the permutations form four groups. Group 1: 14532, 15423, 23541, 32451, 34215, 43125, 51243, 52134. Group 2: 15342, 24351, 42315, 51324. Group 3: 24513, 25143, 31542, 32514, 34152, 35124, 41523, 42153. Group 4: 25314, 41352. The picture shows the first permutation in each group.

2-Symmetric Permutations of Size 5


3-Symmetric Graphs

In my previous post I described 3-symmetric permutations. Now I want to define 3-symmetric graphs.

A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

The above definition is difficult to generalize. So I rephrase: a graph G is 2-symmetric, if the density of any subgraph H with 2 vertices in G is the same as the expected density of H in a random graph where the probability of an edge equals 1/2. This definition is easy to generalize. A graph G is k-symmetric, if the density of any subgraph H with k vertices in G is the same as the expected density of H in a random graph where the probability of an edge equals 1/2. In particular, here are the densities of all four possible subgraphs with 3 vertices in a 3-symmetric graph:

  • A complete graph with 3 vertices: 1/8,
  • A path graph with 3 vertices: 3/8,
  • A graph with 3 vertices and only one edge: 3/8,
  • A graph with 3 isolated vertices: 1/8.

For a graph G to be 3-symmetric, the number of vertices, n, in G needs to be such that n choose 3 is divisible by 8. The first non-trivial case is n = 8. Here are the pictures of two 3-symmetric graphs. The first one is a wheel, and the second one is its complement.

A Wheel Graph with 8 vertices           A Complement to the Wheel Graph with 8 vertices