Tanya Khovanova's Math Blog

I’ve been too busy lately, so I stopped checking my Number Gossip website. Luckily, my website has fans. So one of them, Neil, notified me that my website was hijacked, and instead of describing properties of numbers, was selling steroids. I emailed Dreamhost, my hosting provider. They requested proof that I owned the domain. Why didn’t they request proof from the people selling steroids? Or were they selling steroids themselves?

I fixed my steroid issue and since I was thinking about it anyway, I decided to update Number Gossip. I ended up spending tons of time on it — I had ten years of emails with suggestions for new properties, and I went through all of them and added the interesting ones. For example, Joshua Gray emailed me a cute property of 1331 mentioned on Wikipedia: 1331 was said to be the only cube of the form x² + x − 1. I didn’t see how to prove it, so I posted it as a question on mathoverflow. It turns out that 1331 is actually not the only cube of this form. There are three of them: −1 (for x = 0 or −1), 1 (for x = 1 or −2), and 1331 (for x = 36 or −37). So 1331 is the only non-trivial cube with this property. I had to fix Wikipedia. By the way, did you notice a symmetry? Plugging in x and −x − 1 into the quadratic produces the same value.

After processing all the emails related to Number Gossip, I got excited, so I continued working on it and added tons of new unique properties. Some of them I invented myself, some more were inspired by sequences in the OEIS database. I now have a collection of my new favorite unique properties, which I will post soon.

For the last year, I’ve been obsessed with Penney’s game. In this game, Alice picks a string of coin tosses, say HHH for three heads. After that, Bob picks his string of tosses of the same lengths, say HTH. Then they toss a fair coin. The person whose string shows up first wins. For example, if the tosses are THTTHHH, then Alice wins after the seventh toss. For these particular choices, Bob wins with probability 3/5.

With my PRIMES student, Sean Li, we looked at this game and asked a different question. Suppose Alice picks a pattern of three tosses in a row that are the same. Suppose after that, Bob chooses a pattern of three alternating tosses. Then they toss a fair coin. Alice is hoping for HHH or TTT, while Bob is hoping for HTH or THT. The person whose pattern shows up first wins. For example, if the tosses are THTTHHH, then Bob wins after the third toss. For these particular choices, Bob wins with probability 1/2.

In this example, what actually happens. We assume that the group of two elements acts on the alphabet of two letters. The group’s non-identity element swaps letters H and T. We assume that two strings are equivalent if they belong to the same equivalency class under the group action. We call such an equivalency class a pattern.

In the new game we invented, we have an alphabet of any size and any group acting on the alphabet. Then Alice and Bob pick their patterns. After that, they play the Penney’s game on these patterns. The answers to all the relevant questions are in our paper, The Penney’s Game with Group Action, posted at the math.CO arxiv 2009.06080.

I wrote a paper Confirming the Labels of Coins in One Weighing together with my PRIMES STEP students Isha Agarwal, Paul Braverman, Patrick Chen, William Du, Kaylee Ji, Akhil Kammila, Shane Lee, Alicia Li, Anish Mudide, Jeffrey Shi, Maya Smith, and Isabel Tu. The paper is available at math.HO arxiv:2006.16797. Below my students describe what happens in the paper in their own words.

Tragedy has struck in an iCOINic land known as COINnecticut. One day, while everyone was minding their own business, the vault door of the bank was found to have been forcefully opened. COINcerns spread amongst the COINmoners that someone had tampered with their n sacred COINtainers of coins! The COINtainers are labeled with the integers 1 through n, which usually describe the weight of each of the countless coins inside that corresponding COINtainer. For example, the COINtainer labeled 1 should only COINtain coins that weigh 1 gram, the COINtainer labeled 2 should only COINtain coins that weigh 2 gram, and so on, you get the COINcept.

The acCOINtants COINclude that someone may have switched around the labels on the COINtainers. To resolve this COINplication, aka to check if the labels have been tampered with, they bought a balance scale for a microsCOINpic amount of money. However, they can only use the scale to COINduct one weighing as the angry COINmoners are impatient and wish to withdraw their money ASAP.

The COINfused acCOINtants COINvinced 11 COINspicuous students from Boston’s COINmunity to help them. With their COINbined efforts, they COINcluded that indeed, no matter how many COINtainers there are, their labels can be COINfirmed as correct or incorrect with just one weighing! Unfortunately, sometimes, such a weighing requires the use of many coins or coins with a large COINbined weight, which could potentially break the scale. Seeing this COINundrum, the students wished to be eCOINomical and find the least amount of coins or weight they need to place on the scale.

The acCOINtants and the 11 students COINtinued examining the nature of these weighings and discovered patterns that occur within them. They COINfined their research to special weighings they called downhill. They COINfirmed the effectiveness of such weighings to solve the problem at hand. The students estimated the weight and the number of coins, thus COINpleting their task.

My PRIMES STEP students invented several variations of Penney’s game. We posted a paper about these new games at math.HO arxiv:2006.13002.

In Penney’s game, Alice selects a string of coin-flip outcomes of length n. Then Bob selects another string of outcomes of the same length. For example, Alice chooses HHT, and Bob chooses THH. Then a fair coin is tossed until Alice’s or Bob’s string appears. The player whose string appears first wins. In our example, Bob has a greater probability of winning, namely, 3/4. If the first two flips are HH, then Alice wins; otherwise, Bob wins.

The reader can check that HHT beats HTT with 2 to 1 odds. Thus, the game contains a non-transitive cycle it is famous for: THH beats HHT beats HTT beats TTH beats THH.

I already wrote about the No-Flippancy game that my students invented. It starts with Alice and Bob choosing different strings of tosses of the same length.

However, in the No-Flippancy game, they don’t flip a coin but select a flip outcome deterministically according to the following rule: Let i ≤ n be the maximal length of a suffix in the sequence of “flips” that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next “flip.” Alice goes first, and whoever’s string appears first in the sequence of choices wins.

My favorite game among the invented games is the Blended game, which mixes the No-Flippancy game and Penney’s game.

In the game, they sometimes flip a coin and sometimes don’t. Alice and Bob choose their strings as in Penney’s game and the No-Flippancy game. Before each coin flip, they decide what they want by the rule of the No-Flippancy game above. If they want the same outcome, they get it without flipping a coin. If they want different outcomes, they flip a coin. Whoever’s string appears first in the sequence of `flips’ wins.

For example, suppose Alice selects HHT, and Bob selects THH. Then Alice wants H and Bob wants T, so they flip a coin. If the flip is T, then they both want Hs, and Bob wins. If the first flip is H, they want different things again. I leave it to the reader to see that Bob wins with probability 3/4. For this particular choice of strings, the odds are the same as in Penney’s game, but they are not always the same.

This game has a lot of interesting properties. For example, similar to Penney’s game, it has a non-transitive cycle of choices. Surprisingly, the cycle is of length 6: THH beats HHT beats THT beats HTT beats TTH beast HTH beat THH.

My STEP students invented a coin-flipping game that doesn’t require a coin. It is called The No-Flippancy Game.

Alice and Bob choose distinct strings of length n consisting of the letters H (for heads) and T (for tails). The two players alternate selecting the outcome of the next “flip” to add to the sequence by the rule below.

The “flip” rule: Let i < n be the maximal length of a suffix of the sequence of chosen outcomes that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next term in the sequence.

Alice goes first, and whoever’s string appears first in the sequence of choices wins. In layman terms, the game rules mean that the players are not strategizing, but rather greedily finishing their strings.

Suppose n = 2 and Alice chose HH. If Bob chooses HT, then Bob wins. Alice has to choose H for the first flip. Then Bob chooses T and wins. On the other hand, if Bob chooses TT for his string, the game becomes infinite. On her turn, Alice always chooses H, while on his turn Bob always chooses T. The game outcome is an alternating string HTHTHT… and no one wins.

Suppose n = 4, Alice chooses HHTT, and Bob chooses THHH. The game proceeds as HTHHTHHH, at which point Bob wins.

This game is very interesting. The outcome depends on how Alice’s and Bob’s chosen strings overlap with each other. We wrote a paper about this game, which is available at math.CO arXiv:2006.09588.

Suppose we want to pack a unit square with non-overlapping rectangles that have sides parallel to the axes. The catch is that the lower left corners of all the rectangles are given. By the way, such rectangles are called anchored. Now, given some points in the unit square, aka the lower left corners, we want to find anchored rectangles with the maximum total area.

When the given points are close to the right upper corner of the square, the total area is small. When a single point is in the bottom left corner of the square, we can cover the whole square. The problem becomes more interesting if we add one extra assumption: one of the given points has to be the bottom left corner of the square. In the 1960’s, it was conjectured by Allen Freedman that any set of points has an anchored rectangle packing with the area of at least one half. The problem is quite resistant. In 2011, Dumitrescu and Tóth showed that every set of points has a packing of area at least 0.09, which was the first constant bound found, and is the best bound currently known.

I gave this problem to my PRIMES student Vincent Bian. He wrote a paper, Special Configurations in Anchored Rectangle Packings, that is now available at the arxiv. When you look at this problem you see that the number of ways to pack depends on the relative coordinates of the points. That means you can view the points as a permutation. Vincent showed that the conjecture is true for several different configurations of points: increasing, decreasing, mountain, split layer, cliff, and sparse decreasing permutations.

An increasing permutation is easy. There are two natural ways to pack the rectangles. One way, when rectangles are horizontal and each rectangle reaches to the right side of the square (see picture above). Another way, when rectangles are vertical. When you take the union of both cases, the square is completely covered, which means at least one of the cases covers at least half of the square. The worst case scenario, that is, the case when the maximum possible area is the smallest is when your points are placed equidistantly on the diagonal.

Other cases are more difficult. For example, Vincent showed that for a decreasing permutation with n points, the worst case scenario is when the points are arranged equidistantly on a hyperbola xy = (1-1/n)ⁿ. The picture shows the configuration for 15 points. The total area is more than one half.

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

By the way:

2019 = 1⁴ + 2⁴ + 3⁴ + 5⁴ + 6⁴.

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.

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 a_i (correspondingly b_i) 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) = ∑ a_izⁱ and g(z) = ∑ b_izⁱ. Then the desired result is that f(z)g(z) = ∑_j=0¹⁰ z^j/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 a₅=b₅=0 and the coefficient of z¹⁰ 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, a₀b₀ = a₅b₅ = 1/11. Then the probability of a total 7 is at least a₀b₅ + a₀b₅. The geometric mean of a₀b₅ and a₀b₅ 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?

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.

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:

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.

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.

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.

Share: