Archive for the ‘Math’ Category.

Maximum Egalitarian Cost in the Stable Marriage Problem

Assume that we have n men and n women, all of whom want to get married. They rank each other without ties. After that, we can match them into n pairs for marriage. The matching is called stable if there are no rogue couples. A rogue couple is defined as a man and a woman who prefer each other over their assigned future spouses.

A famous theorem says that, whatever all the rankings are, a stable matching always exists. But how good could a stable matching be? There is a way to assign a quality score to a matching, called the egalitarian cost. The egalitarian cost of any matching is the sum of the rankings that each person gave their assigned partner. The best potential outcome is when all people are matched with their first choices. This corresponds to the minimum egalitarian cost of 2n. But what is the maximum egalitarian cost of a stable matching? I couldn’t find it in the literature, so I proved that it is n(n+1).

Proof. It is easy to see that the egalitarian cost of n(n+1) is achievable. For example, if all men gave an identical ranking to the women, and vice versa, the matching algorithm will end up with couples having mutual rankings (j,j) for different values of j. Another example is a Latin preference profile. Each woman ranks a man n+1−x whenever he ranks her x. In this case, every potential couple’s mutual rankings sum to n+1. Thus, any matching for such rankings ends up with the egalitarian cost of n(n+1).

The next step is to prove that the egalitarian cost can’t be greater. Suppose the cost of a stable matching is C and is greater than n(n+1). Then, for every person, we count the number of people who are better (ranked smaller) than their assigned partner and sum these numbers over all the people. The result must be C−2n, which is the number of pairs of people of opposite genders such that the first person prefers the second one over their assigned partner. Moreover, the result is greater than n(n−1).

The total number of possible couples is n2. Thus, the number of unrealized potential couples is n(n−1). We can conclude that we counted one of these unrealized couples twice. In such a couple, two people prefer each other over their assigned partners. Thus, they form a rogue couple, contradicting our assumption that the matching is stable.

Share:Facebooktwitterredditpinterestlinkedinmail

Whitehead Links for Ukraine

Whitehead Links for Ukraine

This is my second crocheting project to help finance our new program, Yulia’s Dream, in honor of Yulia Zdanovska, a young Ukrainian math talent killed in the war.

I made four Whitehead links in the colors of the Ukrainian flag. You can read about my other crocheting project in my previous post: Hyperbolic Surfaces for Ukraine.

Fun trivia about the Whitehead links.

  • Why are these links so famous? They are the simplest non-trivial links with the linking number zero.
  • What’s the linking number? The linking number is an invariant of a link. If two loops are not linked (they are called an unlink), their linking number is zero. If they are linked, then their linking number is usually not zero. Here the loops are linked, but the linking number is nevertheless zero. Thus, the linking number can’t differentiate this link from an unlink. To explain how to calculate the linking number, I need to explain another simpler invariant: the crossing number.
  • What’s the crossing number? The crossing number is the smallest number of crossings when projecting the link on a plane. The top two pictures have 6 crossings, and the bottom two pictures have 5. The top two pictures emphasize the symmetry of the link, and the bottom two pictures have the smallest possible number of crossings for the Whitehead link. So the crossing number of the Whitehead link is 5.
  • Can you now explain how to calculate the linking number? One way to calculate the linking number is to choose directions for the blue and yellow loops and select the crossings where the blue is on top. After that, following the chosen direction of the blue loop, at each crossing with the yellow loop, check the latter’s direction. If the direction is from right to left, count it with a plus and, otherwise, with a minus. The total is the linking number. In the case of the Whitehead link, it is zero.
  • Is there a more elegant explanation for why the Whitehead link has the linking number zero? Yes. The linking number only looks at the crossings of two different strands and ignores self-crossings. If you look at the two bottom pictures, there is one self-crossing of the blue loop. Now imagine you change the crossing by moving the top blue strand underneath. After such a transformation, the crossing number doesn’t change, but the loops become unlinked. Thus, the linking number of the Whitehead link must be zero.
Share:Facebooktwitterredditpinterestlinkedinmail

Hyperbolic Surfaces for Ukraine

Hyperbolic Surfaces for Ukraine

As you might know, my team started a project, Yulia’s Dream, in honor of Yulia Zdanovska, a young Ukrainian math talent killed in the war.

In this program, we will do what we are great at — help gifted youngsters pursue advanced math. To help the program, I started crocheting hyperbolic surfaces in the colors of the Ukrainian flag. These crochets are designed as gifts to encourage individual donors.

Fun trivia about these hyperbolic surfaces.

  • Why are these surfaces so famous? These surfaces prove that Euclid’s fifth axiom is independent of the other four axioms. The fifth axiom (also known as the parallel postulate) says that if there is a line L and a point P outside of L, then there is exactly one line through P parallel to L. On these hyperbolic surfaces, the first four of Euclid’s axioms hold, while the fifth one doesn’t: if there is a line L and a point P outside of L on such a surface, then there are infinitely many lines through P parallel to L.
  • But what is a line on a hyperbolic surface? A line segment connecting two points is defined as the shortest path between these points, known as a geodesic.
  • How can such a surface be crocheted? I crocheted a tiny circle and continued in a spiral, making 6 stitches in each new row for every 5 stitches in the previous row. This means that each small piece of the crocheted surface is the same throughout the thingy, making these thingies hyperbolic surfaces of constant curvature.
  • What is the constant curvature good for? Constant curvature makes it easy to find lines. You can just fold the thingy, and the resulting crease is a line.
  • Is this thingy a hyperbolic plane? No. A cool theorem states that a hyperbolic plane can’t fit into a 3D space, so whatever someone crochets has to be finite. On second thought, anything someone crochets has to be finite anyway. But I digress. This shape can be viewed as a disc with a hole.
  • The Ukrainian flag is half blue and half yellow, so why do the colors here seem so unevenly distributed? My goal was to use the same amount of blue and yellow yarn per thingy. I leave it as an exercise for the reader to calculate that regardless of how many rows of one color I crochet, to use the same amount of yarn in the second color, I need more than 3 and less than 4 rows of that color. Since I wanted the thingy to be symmetrical, sometimes I had 3, and other times, I had 4 rows of the second color. I also made 4 surfaces where I switched colors every row.

Overall, I crocheted 10 hyperbolic surfaces. If you are interested in donating to help Ukrainian students receive coaching from our program at MIT, the details will be announced on our website shortly.

Share:Facebooktwitterredditpinterestlinkedinmail

My Vision for Number Gossip

I run Number Gossip, where you can input a number and get some of its cute properties. For example, the number 63 is composite, deficient, evil, lucky, and odd. In addition, it has a unique property: 63 is the smallest number out of two (the other being 69), such that the common alphabetical value of its Roman representation is equal to itself. Indeed, the Roman representation of 63 is LXIII, where L is the 12th digit, X is the 24th, and I is the 9th. Summing them up, we get 12 + 24 + 9 + 9 + 9 = 63 — the number itself.

I have a list of about 50 properties of numbers that my program checks. Each number greater than one gets at least four properties. This is because I have four groups of properties that cover all the numbers. Every number is either odd or even. Every number is either deficient, perfect, or abundant. Every number greater than one is either prime or composite. Every number is either evil or odious.

In addition, I collect unique number properties. During the website’s conception, I decided not to list all possible unique properties that I could imagine but to limit the list to interesting and unusual properties. My least favorite properties of numbers are the ones that contain many parameters. For example, 138 is the smallest number whose base 4 representation (2022) contains 1 zero and 3 twos. If you are submitting a number property to me, keep this in mind.

Some parameters are more forgiving than others. For example, 361 is the smallest number which is not a multiple of 9, whose digital sum coincides with the digital sum of its largest proper divisor. In more detail, the digital sum of 361 is 3 + 6 + 1 = 10, while 19, the largest divisor of 361, has the same digital sum of 10. In this case, the parameter 9 is special: for a multiple of 9, it is too easy to find examples that work, such as 18, 27, and so on. Sequence A345309 lists numbers whose digital sum coincides with the digital sum of their largest proper divisor. The first 15 terms of the sequence are divisible by 9, and 361 is the smallest term that is not divisible by 9.

By the way, another number that is buried deep in a sequence is 945, which is the smallest odd abundant number. There are 231 abundant numbers smaller than 945; all of them are even.

A more recent addition to my collection is related to the sequence of distended numbers (A051772). Distended numbers are positive integers n for which each divisor of n is greater than the sum of all smaller divisors. It is easy to see that for distended numbers, all sums of subsets of divisors are distinct. The opposite is not true: 175 is the smallest number, where all sums of subsets of its divisors are distinct, but the number itself is not distended.

It is difficult to find special properties for larger numbers, so I am less picky with them. For example, 3841 is the number of intersections of diagonals inside a regular icosagon. The word icosagon hides a parameter, but I still like the property.

I invite people to submit number properties to me. And I received many interesting submissions. For example, the following oxymoronic property was submitted by Alexey Radul: 1 is the only square-free square.

The numbers below 200 that still lack unique properties are 116, 147, 155, 162, 166, 182, and 194. The earliest century that doesn’t have unique number properties ranges between 7000 and 7100. The next ones are 8000–8100 and 9100–9200. By the way, my site goes up to ten thousand.

I also have a lot of properties in my internal database that I haven’t checked yet. I am most interested in the proof of the following property: 26 is the only number to be sandwiched between any two non-trivial powers.

Share:Facebooktwitterredditpinterestlinkedinmail

Fun with Latin Squares

Last year, our junior PRIMES STEP group studied Latin squares. We invented a lot of different types of Latin squares and wrote a paper about it, Fun with Latin Squares. Recall that a Latin square is an n by n table containing numbers 1 through n in every cell, so that every number occurs once in each row and column. In this post, I want to talk about anti-chiece Latin squares.

First, what’s a chiece? A chiece is a portmanteau word made out of two words, chess and piece, and, not surprisingly, it means a chess piece. Given a chiece, an anti-chiece Latin square is a Latin square such that any two cells, where our chiece can move from one cell to the other, according to the rules of chess, can’t contain the same number. Let’s see what this means.

Let’s start with rooks, which move along rows and columns. An anti-rook Latin square can’t have the same numbers repeating in any one row or column. Ha, anti-rook Latin squares are just Latin squares. Anti-bishop and anti-queen Latin squares can’t have the same numbers repeating on any diagonal.

Now, here is a picture of an anti-knight Latin square in which no two identical numbers are a knight’s move apart. This particular Latin square also forms a mini-Sudoku: not only does each row and column, but also each 2 by 2 corner region, contains all distinct numbers.

Anti-knight Sudoku

Consider all instances of some number, say 1, in an anti-chiece Latin square. If the board is n by n, we get n instances of non-attacking chieces. A famous math puzzle asks to place eight non-attacking queens on a standard chessboard. So the instances of any one particular number in an anti-queen Latin square solves the problem of placing n non-attacking queens on an n by n chessboard. Thus, building an anti-queen Latin square is more complicated than solving the non-attacking queens puzzle. The former requires filling the chessboard with n non-overlapping sets of non-attacking queens. The picture below gives an example of an anti-queen 5 by 5 Latin square.

Anti-queen Sudoku

This square has some interesting properties. It can be formed by cycling the first row. It also happens to be one of the chiece Latin squares we study in our paper. A chiece Latin square is a Latin square such that for each number in a cell, there is another cell, a chiece’s move apart, containing the same number. You can check that our anti-queen Latin square is at the same time a knight Latin square.

I wonder, can anyone build an anti-queen Latin square on the standard 8 by 8 chessboard?


Share:Facebooktwitterredditpinterestlinkedinmail

Reversible Tetrahedra

Do you know what an isosceles tetrahedron is? I didn’t until recently. An isosceles tetrahedron has all of its faces congruent. Equivalently, all pairs of opposite edges are of equal length. Such tetrahedra are also called disphenoids. Here are some cute statements about them.

  • If the four faces of a tetrahedron all have the same perimeter, then the tetrahedron is a disphenoid.
  • If the four faces of a tetrahedron all have the same area, then the tetrahedron is a disphenoid.

Disphenoids have three nontrivial symmetries: 180-degree rotations around three lines connecting the midpoints of opposite edges.

Is it possible to have a tetrahedron with fewer symmetries than disphenoids? Yes, it is. Dan Klain just published a fascinating paper about such tetrahedra: Tetrahedra with Congruent Face Pairs. The results are so elegant and simple that I was surprised that they were new. I got curious and started to google aggressively. I found an official name for this kind of tetrahedron: phyllic disphenoid, but no theorems about them. Their name is quite unappealing: no wonder people didn’t want to study them much. Obviously, Dan wasn’t as aggressive at googling, so he didn’t find this official name and called them reversible tetrahedra. But my favorite name for them is the name Dan thought of but didn’t use in his paper: bi-isosceles tetrahedra.

Reversible Tetrahedron

Here is the picture of a bi-isosceles tetrahedron from Dan’s paper. It has two faces with sides a, b, and c, and two faces with sides a, b, and d. The edges of this tetrahedron are: a, a, b, b, c, and d. It has one nontrivial symmetry: a 180-degree rotation around the line connecting the midpoints of the unequal opposite edges c and d. The picture emphasizes this symmetry. The figure in the picture is a projection of a bi-isosceles tetrahedron onto a plane, such that the line of symmetry is projected onto the point of symmetry of the projection. The two cute statements above, about disphenoids, can be generalized to the case of bi-isosceles tetrahedra.

  • If the four faces of a tetrahedron can be split into two pairs with the same perimeter, then the tetrahedron is bi-isosceles.
  • If the four faces of a tetrahedron can be split into two pairs with the same area, then the tetrahedron is bi-isosceles.

The first property is trivial, while the second one is proven in Dan’s paper. Dan also shows how to calculate the volume of a bi-isosceles tetrahedron:

Reversible Tetrahedron Volume

Share:Facebooktwitterredditpinterestlinkedinmail

Zipper Math

Zipper Surfaces

Each time I teach my students about the Möbius strip, I bring paper, scissors, and tape to class. The students make Möbius strips, and then I ask them to cut the strips in half along the midline and predict the result.

Then we move to advanced strips. To glue the Möbius strip, you need one turn of the paper. An interesting experiment is to glue strips with two, three, or more turns. In this case, too, it is fun to cut them along the midline and predict the shape of the resulting thingy. My class ends with a big paper mess.

As you might know, I am passionate about recycling. So I have always wanted to buy Möbius strips that can be cut in half and then put back together. I didn’t find them, so I made them myself from zippers. Now I can unzip them along the midline and zip them back together. I hope to have less mess in my future classes. We’ll see.

Share:Facebooktwitterredditpinterestlinkedinmail

Borromean Rings

Borromean Rings

Here are my newly-made Borromean rings: two identical sets of them. They are an example of three linked rings, with any two of them not linked. The top set is positioned the way the Borromean rings are usually presented. You can see that any two rings are not linked by mentally ignoring the third one. For example, the red ring is on top of the green one, the green one is on top of the blue one, and the blue one is on top of the red one. They have a non-transitive ordering.

The bottom set of rings is arranged for a lazier thinker. Obviously, the blue and green rings are not linked.


Share:Facebooktwitterredditpinterestlinkedinmail

The Stable Marriage Problem and Sudoku

As you may know, I run PRIMES STEP, a local program where we do mathematical research with students in grades 6-9. Last academic year, we looked at the stable marriage problem and discovered its connection to Sudoku. Our paper The Stable Matching Problem and Sudoku (written jointly with Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) is now available at the arxiv.

Consider 3 men and 3 women who want to be married to each other in heterosexual couples. They rank each other without ties. The resulting 6 permutations of numbers 1, 2, and 3 that describe the six rankings are called the preference profile of this group of people. A matching is unstable if two people would be happier to run away together than to marry into the assigned couples. The two potential runaways are called a rogue couple. A matching is called stable if no rogue couple exists. The Gale-Shapley algorithm, invented by Gale and Shapley, finds a stable matching for any preference profile, implying that stable matching is always possible.

We discovered that preference profiles form a natural bijection with ways to place one digit into a Sudoku grid. So we wrote a paper describing the stable marriage, rogue couples, the Gale-Shapley algorithm, soulmates, and such in terms of Sudoku.

Oops, I forgot to explain who the soulmates are. We invented this term to describe two people who rank each other first. Though it is possible to have several stable matchings for the same preference profile if the soulmates exist, they must always be matched together.

We also invented a new Sudoku type, which I will explain next time.

Share:Facebooktwitterredditpinterestlinkedinmail

Number Gossip on Steroids

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 x2 + 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.

Share:Facebooktwitterredditpinterestlinkedinmail