Noisy Violinists

My PRIMES project last year, done with Rich Wang, was about violinists living in a hotel and being annoyed with each other. The project was suggested by Darij Grinberg and based on the following puzzle.

Puzzle. Consider a hotel with an infinite number of rooms arranged sequentially on the ground floor. The rooms are labeled from left to right with consecutive integers. A finite number of violinists are staying in the hotel with no more than one violinist in a room. Each night, two violinists staying in adjacent rooms get fed up with each other’s playing, and both request different rooms from the manager. The manager moves one of them to the nearest unoccupied room on the left and the other to the nearest unoccupied room on the right. This keeps happening every night as long as there are two violinists in adjacent rooms. Prove that this relocation will stop after a finite number of nights.

The project was not to solve the puzzle, and I won’t describe the solution, leaving it to my readers to ponder on their own. The project was to take this puzzle and see what we could discover. The relocation process in the puzzle is reminiscent of chip-firing, with a few differences.

Let me explain chip-firing in terms of violinists. The starting position would allow any number of violinists per room. Each night, two violinists in the same room will get annoyed with each other and request new rooms. There might be more violinists in that same room, but only two at a time are really annoyed. The manager will put one of them into the room on the left and the other into the room on the right, regardless of how crowded the rooms are.

In the chip-firing example, violinists always move to the next room. In our puzzle, they might need to go miles to a new room. And carry their luggage with them!

The original puzzle above implies that after several nights the relocations will stop, and violinists will enjoy the hotel in peace. This peaceful configuration is called a final state. Interestingly, depending on the order in which violinists are getting annoyed with each other, a starting configuration can result in different final states.

For example, consider the smallest interesting case, where only 3 violinists are staying in a hotel. We use 1 to describe a noisy room with a violinist and 0 to describe an empty room. Suppose the starting configuration is 0011100, where we ignore rooms far away from the noise. Depending on which two rooms have the complaining violinists on the first night, we can end up with a final state 0101001 or 1001010.

Initially, in the project, we looked at final states where we start with N violinists in consecutive rooms. We call such a configuration an N-clusteron. The example above describe the final states of a 3-clusteron. Here is an exercise for the reader: prove that in the final state, the gaps between occupied rooms have to be 1 or 2.

A final state can be described by the index of the leftmost occupied room and the sequence of gaps between occupied rooms. In the exercise above, it is easy to prove that the gaps must be size 1 or 2. In our paper, we proved a more refined statement: any final state has exactly one gap of size 2. Thus, a final state has two parameters: the index of the leftmost room and the location of the size 2 gap. For example, this means that in a final state, the span between the leftmost and the rightmost rooms, inclusive, is 2N.

As we continued exploring final states, we discovered something else. But first, I need to define the shadow of a final state. Let’s denote an occupied room with a one and an empty room with a zero. Then a final state corresponds to an infinite sequence of zeros and ones. But the interesting part of the final state is not infinite: it is a subsequence between the leftmost and rightmost ones, inclusive. We call this subsequence the shadow of the final state. In other words, the shadow describes the final state up to a translation and is completely defined by one parameter: the location of the 2-gap. In our example of a 3-clusteron, there are 2 final states with 2 distinct shadows. For larger clusterons, the situation is more interesting. There are 5 different possible final states for a 4-clusteron but only three distinct shadows. We discovered the following conjecture.

Conjecture. If we start from an N-clusteron and at each state uniformly select a move to perform from all possible moves, then the shadows of the final states are equiprobable.

You can find more details in our paper Ending States of a Special Variant of the Chip-Firing Algorithm. This conjecture is beautiful as it shows that there are hidden symmetries in this process of appeasing the fussy violinists. We didn’t prove this conjecture. Can you do it?

Share:Facebooktwitterredditpinterestlinkedinmail

Follow Your Heart?

“Follow your heart!” This is the most common advice for young people contemplating their future career path. This is not good advice. At some point in my life, the most popular aspiration among my friends’ children was to become opera singers. But the world only has room for a few opera singers. All of these children ended up doing something completely unrelated.

Aspiring to be a mathematician is a much more practical dream. There are so many professions that are friendly to mathematicians: actuary, finance, economics, teaching, computer science, cryptography, and programming, to name a few. Unlike opera singers, skilled mathematicians can find a way to get paid for their mathematical gifts.

However, most of the youngsters around me want to be research mathematicians. This is a different story. My adviser, Israel Gelfand, told everyone that if they could survive without mathematics, they should drop it. I did drop mathematics for some time to care for my children, but I couldn’t live without mathematics. I fed math to my children for breakfast and pursued math hobbies that could fit a single mother’s lifestyle. Well, that means I was mostly working with sequences for the Online Encyclopedia of Integer Sequences and building the database for my Number Gossip website. But I digress.

I agree with Gelfand. Research in math as a career choice is non-trivial. Here are some of the big issues:

  • Money. An entry-level salary for MIT undergraduate alums is about twice as much as graduate students’ stipends. This discrepancy in income continues for a long time.
  • Location. It is challenging to find a professorship. People looking for academic jobs are expected to send hundreds of job applications and accept a position anywhere in the country. This might be unacceptable for people who value their family and roots.
  • Time. Many research mathematicians I know work 24/7. Not always by choice. Some want to secure a future tenure and need to publish papers in addition to teaching innovative courses. Some do want to do research but are too distracted with their routine and administrative tasks. As a result, their research spills out into nights and weekends.
  • Gender and such. Discrimination is a separate big problem for women and minorities, which I do not want to discuss today.

So what would I suggest for young people who love math?

Many people who love math do not really love math per se. They love the way of thinking that math encourages. They love logic, generating ideas, precision, innovation, and so on. This makes their potential job search much wider. Such people might enjoy programming, cryptography, data science, actuarial science, finance, economics, computer science, engineering, etc. I know students planned to become mathematicians but tried an internship in finance and found their real passion.

For those who want to be closer to mathematics, there is always teaching: the world needs way more math teachers than research mathematicians. Plus, teaching provides a strong feeling of making an impact.

So what do I suggest for young people who love opera singing?

Many skills are less in demand than mathematics. It is important to be realistic. So here is my advice:

  • Expand your skill set. If you love opera singing, working as a voice coach might be a solution.
  • Explore secondary interests. If you also enjoy programming, you might find your happiness by building music software.
  • Have a backup plan. You might become a lawyer to support yourself and your family and keep your love of music as a hobby, for example, by singing in a choir.
  • Meet yourself halfway. You might get a half-time job to feed yourself and work on your music business for the other half of the time.

I know a former Soviet mathematician who worked as a night guard and used his quiet work time to invent theorems. He was a good mathematician but couldn’t find a research position because he was Jewish. He later immigrated to the US and found a professorship. So sometimes my advice for opera singers works for mathematicians too.


Share:Facebooktwitterredditpinterestlinkedinmail

A Silent Parrot

Puzzle. “I guarantee,” said the pet-shop clerk, “that this parrot will repeat every word it hears.” A customer bought the parrot but found it wouldn’t speak a single word. Nevertheless, the clerk told the truth. Explain.

The official answer:

  • The parrot is deaf.

Indeed, in this case, it is not a lie that the parrot will repeat every word it hears. My students had some other ideas. The following answer differs from the official one by one letter, but the spirit of the solution is the same.

  • The parrot is dead.

Another idea my students had was to introduce a time component.

  • The parrot wasn’t guaranteed to say the lines immediately; it would wait 30 years before repeating any words.
  • The parrot only repeated the words in the customer’s absence.

And a couple of outside-of-the-box answers.

  • The parrot was a toy and did not have a battery in it.
  • The customer mistook the pet-shop owner to say the statement about the parrot when in fact, the parrot was saying it.

Share:Facebooktwitterredditpinterestlinkedinmail

A Puzzle Courtesy of Dick Hess

Puzzle. Alice and Bob divide a pie. Alice cuts the pie into two pieces. Then Bob cuts one of those pieces into two more pieces. Then Alice cuts one of the three pieces into two pieces. In the end, Alice gets the smallest and the largest piece, while Bob gets the two middle pieces. Given that both want to get the biggest share of the pie, what is Alice’s strategy? How much can she get?


Share:Facebooktwitterredditpinterestlinkedinmail

An Affair

Many years ago, I visited a distant country and rekindled my friendship with a nice couple, Alice and Bob. I changed the names and do not remember the exact words. But here is the story.

One evening, I found myself chatting with Bob, and he decided to open up. He told me he was having an affair. After he finished his long story, I asked him whether he thought Alice might also be having an affair. He replied, “It’s impossible. She was never a passionate person. And recently, she became even more cold and distant.” I didn’t follow his logic but didn’t pursue the topic.

Several days later, I chatted with Alice, and she decided to open up. She told me that she had met someone and was having an affair. She told me that she never quite enjoyed sex with her husband, but the new guy fitted her perfectly. For the sake of symmetry, I asked her whether she thought her husband might also be having an affair. She replied, “It’s impossible. He is too busy at work, and recently, even more so. He goes on business trips twice a week and is always tired.”

Share:Facebooktwitterredditpinterestlinkedinmail

Refresh Your Greek to Solve a Puzzle

I invented this puzzle. It’s a variation of something I saw on Facebook.

Puzzle. The future dinner of an anthropophagusphagusphagus met for dinner the past study object of an anthropophaguslogist. What’s for dinner?


Share:Facebooktwitterredditpinterestlinkedinmail

A New Version of an Old Joke

Here is a famous old joke about Russian propaganda. I heard it when Leonid Brezhnev was General Secretary of the Communist Party of the Soviet Union and Ronald Reagan was the president of the US.

Joke. A Russian newspaper wrote an article about a two-person race between the Russian and the US leaders. They wrote, “Brezhnev got an honorable second place, while Reagan was almost last”.

Here is a modern version of this joke I heard going around.

Joke. A Russian TV commentator: Biden cowardly goes to war-torn Kyiv, while Putin heroically hides in his bunker.


Share:Facebooktwitterredditpinterestlinkedinmail

Dividing Chores

Before dividing chores, let’s divide a cake. Suppose I bought a two-layer cake. One layer is chocolate and the other is vanilla. Suppose I love chocolate and hate vanilla, My friend, Joe, is the opposite: he loves vanilla and hates chocolate. It’s very easy to divide the cake. I take all the chocolate, and Joe takes all the vanilla. I think I am lucky to get the full value of the whole cake. Joe feels lucky too.

My point is that people with different tastes can divide things so that both get more than half by their own estimates.

Let’s look at another example. Suppose Alice and Bob are divorcing. Their estate consists of one valuable thing: a portrait of Alice’s grandfather. Alice loved her grandfather and values the portrait at 10,000 dollars. Meanwhile, Bob values it the same as its market value, 2,000 dollars. There exists a division algorithm, called the Knaster procedure, which allows them to divide the portrait so that both of them end up with the same amount of money on top of their perceived half of the estate.

I will skip the calculations. The end result is that Alice gets the portrait and pays Bob 3,000 dollars. In her view, she gets a portrait worth 10,000 and loses 3,000. Her total gain is 7,000 dollars, which is 2,000 more than her estimated half. Bob gets 3,000 dollars. In his view, half of the estate is 1,000 dollars, and he gets 2,000 more than that.

The bigger the difference in perceived value, the more each person gets in addition to their expected half. Suppose this difference is D. If you trust my calculations, the Knaster procedure means each person gets D/4, in addition to one half of their estate’s perceived value.

The same idea can be applied to chores. Suppose I hate shopping while my husband hates doing the dishes. So, I can do the dishes, and he can shop. And we can live happily ever after without doing the things we hate.

So, theoretically, it is very profitable for two people to live together. Have you seen couples where each one thinks that they won the lottery by marrying their partner? Such couples benefit from dividing chores, appreciate their partners’ help, and are happy.

I have seen such couples, though not many. Actually, not many at all. If mathematics says that living together should be profitable, then why are happy couples such a rarity?

I will divide unhappy couples into four categories depending on whether they both benefit from dividing the chores and whether they both appreciate each other.

Benefit and appreciate. In this case, other parameters could affect their happiness: love, sex, children, jobs, and so on. Consider, for example, Alice and Bob. Alice relies on her husband for financial support for her and their small children and appreciates said support. Bob likes how Alice cares for the children and appreciates her for that. However, Alice doesn’t love Bob anymore, and Bob wants something special in his sex life but is afraid to request it from Alice. They are both profoundly unhappy.

Benefit and do not appreciate. It is possible that both people do not appreciate each other, or it could be just one. In addition, it could be that a person underestimates the real value of the partner’s contribution, or it could be that the appreciation is not enough for the partner. This became a more complicated paragraph than I initially expected. As Lev Tolstoy said, “All happy families are alike; each unhappy family is unhappy in its own way.” So, let me have two subcases.

Benefit and do not appreciate. Case 1. Underestimation. Such couples have a good division of labor but underestimate each others’ contribution. For example, Bob thinks that staying at home with children is a walk in the park. He thinks his job is way more difficult than his wife’s daily caring for the house and the children. He assumes that when he returns from work, the house needs to be clean and dinner ready. He is very angry when this doesn’t happen. Alice is very unhappy as she knows how much she actually works.

Benefit and do not appreciate. Case 2. No gratitude. Such couples have a good division of labor but do not express their gratitude sufficiently for the other partner. For example, Alice wants Bob to take her out to dinner as a thank you. Or to say thank you on a regular basis. But Bob brags to his friends that he is lucky in marriage and thinks that this is enough. Everyone but her knows that he feels lucky.

Do not benefit. It is usually one person who is used. There are many ways for people to force their spouses to divide the chores in their favor. There are many types of abusive relationships. I do not even want to give an example. After all, my goal was to discuss the mathematics of chores’ division, not to analyze why people do not divide their labor fairly.

Special cases. Life is complicated. Here is the case that doesn’t quite fit the cases above as the division of chores with time delays. For example, Alice worked and cared for the children while Bob went to medical school. The benefit for Alice was implied in the future. Bob promised to shower her with money when he would get rich. However, as soon as he got rich, he showered someone else.

The mathematics show that living with a partner can be extremely beneficial for both. But people’s emotions are complicated. They do not follow mathematics and often mess it up in more ways than I can imagine.

Share:Facebooktwitterredditpinterestlinkedinmail

Towers

I got immediately attracted to the puzzle Oleg Polubasov recently posted on Facebook.

Puzzle. A rectangular clearing in a forest is an N-by-M grid, and some of the cells contain a tower. There are no towers in the cells that neighbor the forest. A tower protects its own cell completely and parts of the eight neighboring cells at a depth of half of a cell. Here by neighbors, we mean the cells horizontally, vertically, and diagonally adjacent to the given cell. In particular, if each cell is one square unit, a tower protects four square units. The protected area forms a square with borders that lie in between the grid lines. A tsar knows the towers’ locations and wants to calculate the protected area. Prove that the following formula gives the answer: the number of 2-by-2 subgrids that contain at least 1 tower.

The Inhabited Island

I like this puzzle because it has an elegant solution. But there is more. The puzzle reminds me of one of my favorite novels by Arkady and Boris Strugatsky: The Inhabited Island, also known as Prisoners of Power. This is a science fiction novel where Max Kammerer, a space explorer, ends up on a planet with desolate people who, twice daily, experience sudden bouts of enthusiasm and allegiance to the government. Later, it becomes clear that the love for the rulers comes from towers that broadcast mind-control signals suppressing critical thinking and making people prone to believe propaganda.

The novel was written in 1969 but accurately describes the modern Russian propaganda machine. It appears that there is no need for a secret signal. Just synchronized propaganda on government-controlled TV turns off people’s brains.

Share:Facebooktwitterredditpinterestlinkedinmail

Whitney Umbrellas

A Whitney umbrella is a cool surface I wanted to crochet. The umbrella continues to infinity, and there is no way I want to crochet the whole thing. I wanted to make a finite portion of a Whitney umbrella surrounding the most exciting point.

Crocheted Whitney Umbrellas

The result is seen in the picture. Technically, I crocheted not Whitney umbrellas but topologically equivalent surfaces. I am most proud of my secret — and painful — method of crocheting the self-intersecting segment. One day I will spill it.

As Wikipedia defines it: the Whitney umbrella is the union of all straight lines that pass through points of a fixed parabola and are perpendicular to a fixed straight line parallel to the parabola’s axis and lies on its perpendicular bisecting plane. If you look at the picture, the fixed straight line is the self-intersection line, which is a continuation of the line segment where the colors are woven through each other. You can find the parabola as the curve formed by the two-colored edge on either side of the umbrella. Oops, I forgot that only three of these umbrellas are made of two colors.

The Whitney umbrella is a ruled surface, meaning that for every point, there is a straight line on the surface that passes through the point. A ruled surface can be visually described as the set of points swept by a moving straight line.

Oh, look, the stitched rows can pretend to be these straight lines. Actually, if I fold these thingies, the stitched rows ARE straight lines. But, when I make the edges into parabolas, the rows stop being straight. In the real Whitney umbrella, if you look along the intersection line, the straight lines are closer to each other than they are along the parabola. But in crochets, the distances between rows have to be fixed. If my crochets are folded, they become rectangles and ruled surfaces. The real Whitney umbrella does not fold into a plane.

The Whitney umbrella is famous for being the only stable singularity of mappings from R2 to R3. I am grateful to Paul Seidel for emailing me the proof. This singularity is so famous it even has two names: pinch point and cuspidal point. Though my crochets are not exactly Whitney umbrellas, they show this singularity. Hooray! I found a secret way to crochet the most famous stable singularity!

Share:Facebooktwitterredditpinterestlinkedinmail