Archive for the ‘Math’ Category.

The Dying Art of Mental Math Tricks

Without using a calculator, can you tell how much 752 is? If you are reading my blog, with high probability you know that it is 5625. The last two digits of the square of a number ending in 5 are always 25. So we only need to figure out the first two digits. The first two digits equals 7 times 8, or 56, which is the first digit of the original number (7) multiplied by the next number (8).

I was good at mental arithmetic and saved myself a lot of money back in the Soviet Union. Every time I shopped I calculated all the charges as I stood at the cash register. I knew exactly how much to pay, which saved me from cheating cashiers. To simplify my practice, the shelves were empty, so I was never buying too many items.

When I moved to the US, the situation changed. Salespeople are not trying to cheat, not to mention that they use automatic cash registers. In addition, the US sales taxes are confusing. I remember how I bought three identical chocolate bars and the total was not divisible by 3. So I completely dropped my at-the-cash-registers mental training.

Being able to calculate fast was somewhat useful many years ago. But now there is a calculator on every phone.

John H. Conway is a master of mental calculations. He even invented an algorithm to calculate the day of the week for any day. He taught it to me, and I too can easily calculate that July 29 of 1926 was Thursday. This is not useful any more. If I google “what day of the week is July 29, 1926,” the first line in big letters says Thursday.

One day a long time ago I was watching a TV show of a guy performing mental tricks: remembering large numbers, multiplying large numbers, and so on. At the end, to a grand fanfare, he showed his crowned trick. A member from the audience was to write down a 2-digit number, and to raise it to the fifth power using a calculator. The mental guy, once he is told what the fifth power was, struggled with great concentration and announced the original number.

I was so underwhelmed. Anyone knows that the last digit of a number and its fifth power are the same. So he only needs to guess the first digit, which can easily be estimated by the size of the fifth power.

I found the description of this trick online. They recommend memorizing the fifth powers of the numbers from 1 to 9. After that, you do the following. First, listen to the number. Next, the last digit of the number you hear is the same as the last digit of the original number. To figure out the first digit of the original number, remove the last 5 digits of the number you hear. Finally, determine between which fifth powers it fits. This makes sense. Or, you could be lazy and remember only meaningful digits. For example, 395=90,224,199, and 405=102,400,000. So if the number is below 100,000,000, then the first digit is less than 4.

You do not have to remember the complete fifth powers of every digit. You just need to remember significant ranges. Here they are:

first digit range
1 between 100,000 and 3,000,000
2 between 3,000,000 and 24,000,000
3 between 24,000,000, 100,000,000
4 between 100,000,000 and 300,000,000
5 between 300,000,000 and 750,000,000
6 between 750,000,000 and 1,600,000,000
7 between 1,600,000,000 and 3,200,000,000
8 between 3,200,000,000, and 5,900,000,000
9 above 5,900,000,000

Besides, for this trick the guy needed to guess one out of one hundred number. He had a phenomenal memory, so he could easily have remembered one hundred fifth powers. Actually he doesn’t need to remember all the numbers, only the differentiated features. On this note, there is a cool thing you can do. You can guess the number before the whole fifth power is announced. One caveat: a 1-digit number x and 10x when taken to the fifth power, both begin with the same long string of digits. So we can advise the audience not to suggest a 1-digit number or a number divisible by 10, as that is too easy (without telling the real reason).

Now we can match a start of the fifth power to its fifth root. Three first digits are almost always enough. Here is the list of starting digits and their match: (104,16), (107,64), (115,41), (116,65), (118,26), (12,66), (130,42), (135,67), (141,17), (143,27), (145,68), (147,43), (156,69), (161,11), (164,44), (17,28), (180,71), (184,45), (188,18), (19,72), (2051,29), (2059,46), (207,73), (221,74), (229,47), (23,75), (247,19), (248,12), (253,76), (254,48), (270,77), (282,49), (286,31), (288,78), (30,79), (33,32), (345,51), (348,81), (370,82), (371,13), (38,52), (391,33), (393,83), (40,21), (4181,53), (4182,84), (44,85), (454,34), (459,54), (470,86), (498,87), (50,55), (51,22), (525,35), (527,88), (53,14), (550,56), (558,89), (601,57), (604,36), (62,91), (64,23), (656,58), (659,92), (693,37), (695,93), (71,59), (73,94), (75,15), (77,95), (792,38), (796,24), (81,96), (84,61), (85,97), (902,39), (903,98), (91,62), (95,99), (97,25), (99,63).

Or, you can come to the mental guy’s performance and beat him by shouting out the correct answer before he can even finish receiving the last digit. This would be cool and cruel at the same time.


Stern-Brocot Trees

Since I was a child I prided myself on knowing arithmetic. I knew how to add fractions. I knew that 2/3 plus 1/4 is 11/12. Some kids around me were struggling and often summed it up the wrong way by adding numerators and denominators separately and getting 3/7 as a result.

As I grew older I found more reasons to ignore the wrong way. For example, the result of such addition depends on the representation of a fraction, not on the fraction itself, and this was bad.

Oh well. I was growing older, but not wiser. Now mathematicians study this wrong addition of fractions. They call such a sum a mediant of two rational numbers. To avoid the dependency on the representation of fractions, the fractions are assumed to be in the lowest terms.

Let us start with the sequence of fractions: 0/1 and 1/0. This sequence is called the Stern-Brocot sequence of order 0. The Stern-Brocot sequence of order n is generated from the Stern-Brocot sequence of order n − 1 by inserting mediants between consecutive elements of the sequence. For example, the Stern-Brocot sequence of order 2 is 0/1, 1/2, 1/1, 2/1, 1/0.

Where are the trees promised in the title? We can build a portion of this binary tree out of the sequence of order n in the following manner. First, ignore the starting points 0/1 and 1/0. Then assign a vertex to every number in the sequence. After that, connect every mediant to one of the two numbers it was calculated from. More precisely, if a number first appeared in the i-th sequence, its only parent is the number that first appeared in the sequence i−1.

There is beautiful theorem that states that every non-negative rational number appears in the Stern-Brocot sequences. The proof is related to continued fraction. Suppose a rational number r is represented as a continued fraction [a0;a1,a2,…,ak], where ak is assumed to be greater than 1 for uniqueness. Then this number first appears in the Stern-Brocot tree of order a0 + a1 + a2 + … + ak + 1, and its parent is equal [a0;a1,a2,…,ak − 1].

My PRIMES student, Dhroova Ayilam, was working on a project suggested by Prof. James Propp. The goal was to find out what happens if we start with any two rational numbers in lowest terms. Dhroova proved that as with the classical Stern-Brocot trees, any rational number in a given range appears in the tree. His paper Modified Stern-Brocot Sequences is available at the arXiv.


Nim Automaton

I mentor three PRIMES projects. One of them, with Joshua Xiong from Acton-Boxborough Regional High School, is devoted to impartial combinatorial games. We recently found a connection between these games and cellular automata. But first I need to remind you of the rules of Nim.

In the game of Nim there are several piles with counters. Two players take turns choosing a pile and removing several counters from it. A player loses when he or she who doesn’t have a turn. Nim is the most famous impartial combinatorial game and its strategy is well known. To win, you need to finish your move in a so called P-position. Nim P-positions are easy to calculate: Bitwise XOR the number of counters in all the piles, and if the result is zero then it’s a P-position.

The total number of counters in a P-position is even. So we calculated the sequence a(n): the number of P-positions in the game of Nim with three piles with the total number of counters equal to 2n. As soon as we got the sequence we plugged it into the OEIS, and voilà it was there: The sequence A130665 described the growth of the three branches of the Ulam-Warburton cellular automaton.

U-W automaton

The first picture shows the automaton after 6 generations. The automaton consists of cells that never die and it grows like this: start with a square on a square grid. In the next generation the squares that share exactly one side with the living squares are born. At the end remove the Southern branch.

Everything fell into place. We immediately realized that the language of the automata gives us the right words to describe what we know about the game of Nim.

Now we want to describe the automaton related to any impartial combinatorial game. Again, the cells never die and the initial cells correspond to terminal P-positions. People who write programs for calculating P-positions will find a notion of the next generation very natural. Indeed, the program usually starts with the terminal P-positions: they are generation 0. Then we can proceed by induction. Suppose we have found P-positions up to generation i. Denote the positions that are one move away from generation i and earlier as Ni. Then the P-positions that do not belong to generation i and earlier and from which all moves belong to Ni are the P-positions from generation i + 1.

This description explains the generations, but it doesn’t explain who is the parent of a particular P-position. The parent-child relations are depicted as edges on the cellular automaton graph. The parent of position P1 from generation i + 1 is a P-position P2 in generation i that can be reached from P1 in the game.

The parent-child relationship in the game of Nim is especially easy to explain. A P-position P1 is a parent of a P-position P2 if P1 differs from P2 in exactly two piles and it has one fewer counter in each of these piles. For example, a P-position (1,3,5,7) has six parents, one of them is (1,3,4,6). In the game with thee piles a P-position always has exactly one parent.

A position in the game of Nim with three piles is naturally depicted as a triple of numbers, that is as a point in 3D. The picture below shows the Nim automaton in 3D at generation 6.

Nim Automaton

Our paper, Nim Fractals, about sequences enumerating P-positions and describing the automaton connection in more detail is posted at the arXiv:1405.5942. We give a different, but equivalent definition of a parent-child relationship there. A P-position P1 is a parent of P2 if there exists an optimal game such that P1 is achieved from P2 in exactly two moves in a game which takes the longest number of possible moves.


Beer Jokes and Hat Puzzles

This is one of my favorite jokes:

Three logicians walk into a bar. The waitress asks, “Do you all want beer?”
The first logician answers, “I do not know.”
The second logician answers, “I do not know.”
The third logician answers, “Yes.”

This joke reminds me of hat puzzles. In the joke each logician knows whether or not s/he wants a beer, but doesn’t know what the others want to drink. In hat puzzles logicians know the colors of the hats on others’ heads, but not the color of their own hats.

This is a hat puzzle which has the same answers as in the beer joke. Three logicians walk into a bar. They know that the hats were placed on their heads from the set of hats below. The total number of available red hats was three, and the total number of available blue hats was two.

Red Hat Red Hat Red Hat Red Hat Red Hat

Three logicians walk into a bar. The waitress asks, “Do you know the color of your own hat?'”
The first logician answers, “I do not know.”
The second logician answers, “I do not know.”
The third logician answers, “Yes.”

The puzzle is, what is the color of the third logician’s hat?

This process of converting jokes to puzzles reminds me of the Langland’s Program, which tries to unite different parts of mathematics. I would like to unite jokes and puzzles. So here I announce my own program:

Tanya’s Program: Find a way to convert jokes into puzzles and puzzles into jokes.


Four More Papers

I submitted four papers to the arXiv this Spring. Since then I wrote four more papers:

  • (with Leigh Marie Braswell) Cookie Monster Devours Naccis. History and Overview arXiv: arXiv 1305.4305.

    In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.

  • A Line of Sages.

    A new variation of an old hat puzzle, where sages are standing in line one behind the other.

  • (Jesse Geneson and Jonathan Tidor) Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs. Combinatorics arXiv: arXiv 1307.1169.

    We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

  • (with Leigh Marie Braswell) On the Cookie Monster Problem. History and Overview arXiv: arXiv 1309.5985.

    The Cookie Monster Problem supposes that the Cookie Monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number of a set is the minimum number of moves the Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. We also construct sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number between 0 and 1 inclusive.



Tanya Khovanova and Joel Brewster Lewis

In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).

In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.

Skyscraper Puzzle

Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.

Let’s continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.

Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let’s denote the total number of permutations by fn(a, b). We will assume that a is on the left and b is on the right.

In a previous example, we showed that fn(n, 1) = 1. And of course we have fn(a, b) = fn(b, a).

Let’s discuss a couple of other examples.

First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, fn(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.

Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case fn(a,n+1-a) is (n-1) choose (a-1). Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a-1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.

Before going further let us see what happens if only one of the maxima is given. Let us denote by gn(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a-1 of them. If the shortest building is not on the left, then it can be in any of the n-1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function gn(a) satisfies the recurrence:

Skyscraper Formula 1

Actually gn(a) is a well-known function. The numbers gn(a) are called unsigned Stirling numbers of the first kind (see; not only do they count permutations with a given number of left-to-right (or right-to-left) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)…(x + n), among other places. (Another pair of exercises.)

We are now equipped to calculate fn(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b-1 more buildings are seen from the right. That is fn(1, b) = gn-1(b-1).

Here is the table of non-zero values of fn(1, b).

b=2 b=3 b=4 b=5 b=6 b=7
n=2 1
n=3 1 1
n=4 2 3 1
n=5 6 11 6 1
n=6 24 50 35 10 1
n=7 120 274 225 85 15 1

Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. We can take any permutation counted by fn(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n-1, the first k values form a permutation with a – 1 left-to-right maxima and the last n – k – 1 values form a permutation with b – 1 right-to-left maxima, and there are no other restrictions. Thus:

Skyscraper Formula 2

Let’s have a table for f7(a,b), of which we already calculated the first row:

b=1 b=2 b=3 b=4 b=5 b=6 b=7
a=1 0 120 274 225 85 15 1
a=2 120 548 675 340 75 6 0
a=3 274 675 510 150 15 0 0
a=4 225 340 150 20 0 0 0
a=5 85 75 15 0 0 0 0
a=6 15 6 0 0 0 0 0
a=7 1 0 0 0 0 0 0

We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).

The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.


Halving Lines

One of the 2012 PRIMES projects, suggested by Professor Jacob Fox, was about bounds on the number of halving lines. I worked on this project with Dai Yang.

Suppose there are n points in a general position on a plane, where n is an even number. A line through two given points is called a halving line if it divides the rest of n−2 points in half. The big question is to estimate the maximum number of halving lines.

Let us first resolve the small question: estimating the minimum number of halving lines. Let’s take one point from the set and start rotating a line through it. By a continuity argument you can immediately see that there should be a halving line through any point. Hence, the number of halving lines is at least n/2. If the point is on the convex hull of the set of points, then it is easy to see that it has exactly one halving line through it. Consequently, if the points are the vertices of a convex n-gon, then there are exactly n/2 halving lines. Thus, the minimum number of halving lines is n/2.

Finding the maximum number of halving lines is much more difficult. Previous works estimated the upper bound by O(n4/3) and the lower bound by O(ne√log n). I think that Professor Fox was attracted to this project because the bounds are very far from each other, and some recent progress was made by elementary methods.

Improving a long-standing bound is not a good starting point for a high school project. So after looking at the project we decided to change it in order to produce a simpler task. We decided to study the underlying graph of the configuration of points.

Suppose there is a configuration of n points on a plane, and we are interested in its halving lines. We associate a graph to this set of points. A vertex in the configuration corresponds to a vertex in the graph. The graph vertices are connected, if the corresponding vertices in the set have a halving line passing through them. So we decided to answer as many questions about the underlying graph as possible.

For example, how long can the longest path in the underlying graph be? As I mentioned, the points on the convex hull have exactly one halving line through them. Hence, we have at least three points of degree 1, making it impossible for a path to have length n. The picture below shows a configuration of eight points with a path of length seven. We generalized this construction to prove that there exists a configuration with a path of length n−1 for any n.


We also proved that:

  • The largest cycle can have length n − 3.
  • The largest clique is of the order O(√n).
  • The degrees of two distinct vertices sum to at most n, if they are connected by an edge, and at most n − 2 otherwise.

After we proved all these theorems, we came back to the upper bound and improved it by a constant factor. Our paper is available at arXiv:1210.4959.


Three out of Three

Davidson Institute for Talent Development announced their 2012 Winners. Out of 22 students, three were recognized for their math research. All three of them are ours: that is, they participated in our PRIMES and RSI programs:

  • David Ding’s project, “Infinitesimal Cherednik Algebras of gln,” came out of his participation in the PRIMES program.
  • Sitan Chen’s project, “On the Rank Number of Grid Graphs,” came out of his participation in the RSI program.
  • Xiaoyu He’ project, “On the Classification of Universal Rotor-Routers,” came out of his participation in the PRIMES program.

I already wrote about Xiaoyu’s project. Today I want to write about Sitan’s project and what I do as the math coordinator for RSI.

RSI students meet with their mentors every day and I meet with students once a week. On the surface I just listen as they describe their projects. In reality, I do many different things. I cheer the students up when they are overwhelmed by the difficulty of their projects. I help them decide whether they need to switch projects. I correct their mistakes. Most projects involve computer help, so I teach them Mathematica. I teach them the intricacies of Latex and Beamer. I explain general mathematical ideas and how their projects are connected to other fields of mathematics. I never do their calculations for them, but sometimes I suggest general ideas. In short, I do whatever needs to be done to help them.

I had a lot of fun working with Sitan. His project was about the rank number of grid graphs. A vertex k-ranking is a labeling of the vertices of a graph with integers from 1 to k so that any path connecting two vertices with the same label passes through a vertex with a greater label. The rank number of a graph is the minimum possible k for which a k-ranking exists for that graph. When Sitan got the project, the ranking numbers were known for grid graphs of sizes 1 by n, 2 by n, and 3 by n. So Sitan started working on the ranking number of the 4 by n graph.

His project was moving unusually fast and my job was to push him to see the big picture. I taught him that the next step, once he finishes 4 by n graphs is not to do 5 by n graphs, as one might think. After the first step, the second step should be bigger. He should use his insight and understanding of 4 by n graphs to try to see what he can do for any grid graphs.

This is exactly what he did. After he finished the calculation of the rank number of the 4 by n graphs, he found a way to improve the known bounds for the ranking number of any grid graph. His paper is available at the arXiv.

I just looked at my notes for my work with Sitan. The last sentence: “Publishable results, a potential winner.”


A Measure of Central Symmetry

Consider central symmetry: squares and circles are centrally symmetric, while trapezoids and triangles are not. But if you have two trapezoids, which of them is more centrally symmetric? Can we assign a number to describe how symmetric a shape is?

Here is what I suggest. Given a shape A, find a centrally symmetric shape B of the largest area that fits inside. Then the measure of central symmetry is the ratio of volumes: B/A. For centrally symmetric figures the ratio is 1, and otherwise it is a positive number less than 1.

Five Discs

The measure of symmetry is positive. But how close to 0 can it be? The picture on the left is a shape that consists of five small disks located at the vertices of a regular pentagon. If the disks are small enough than the largest symmetric subshape consists of two disks. Thus the measure of symmetry for this shape is 2/5. If we replace a pentagon with a regular polygon with a large odd number of sides, we can get very close to 0.

Triangle's Symmetricity

What about convex figures? Kovner’s theorem states that every convex shape of area 1 contains a centrally symmetric shape of area at least 2/3. It is equal to 2/3 only if the original shape is a triangle. That means every convex shape is at least 2/3 centrally symmetric. It also means that the triangle is the least centrally symmetric convex figure. By the way, a convex shape can have only one center of symmetry.

After I started writing this I discovered that there are many ways in which people define measures of symmetry. The one I have defined here is called Kovner-Besicovitch measure. The good news is that the triangle is the least symmetric planar convex shape with respect to all of these different measures.


Interlocking Polyominoes

Locking HexesSid Dhawan was one of our RSI 2011 math students. He was studying interlocking polyominoes under the mentorship of Zachary Abel.

A set of polyominoes is interlocked if no subset can be moved far away from the rest. It was known that polyominoes that are built from four or fewer squares do not interlock. The project of Dhawan and his mentor was to investigate the interlockedness of larger polyominoes. And they totally delivered.

They quickly proved that you can interlock polyominoes with eight or more squares. Then they proved that pentominoes can’t interlock. This left them with a gray area: what happens with polyominoes with six or seven squares? After drawing many beautiful pictures, they finally found the structure presented in our accompanying image. The system consists of 12 hexominoes and 5 pentominoes, and it is rigid. You cannot move a thing. That means that hexominoes can be interlocked and thus the gray area was resolved.

You can find the proofs and the details in their paper “Complexity of Interlocking Polyominoes”. As you can guess by the title, the paper also discusses complexity. The authors proved that determining interlockedness of a a system that includes hexominoes or larger polyominoes is PSPACE hard.