Archive for the ‘Math Education’ Category.

My Virtual Stars

I like rewarding my students. Before covid, I used to give them star stickers for good ideas. When I started to teach remotely, I wondered what I should do instead. I could tell them that they had won a star, but it felt too weak. The next idea was to show them a star and tell them that it belonged to them. But that still felt insufficient. Then I had an epiphany. I would say to them they earned a star, show it to them, and stick it to my face. So they, and all the other students, would see it for the rest of the class. The photo shows how I looked at the end of a successful lesson.

Tanya getting a prize at a linguistics Olympiad

Another picture shows what my MathRoots students posted on our Discord channel.

Students about Tanya's stars

Now that I am back teaching in person, my students asked me to continue sticking their stars to my face. Sometimes I forget about the stars and, after my class, wander around MIT star-covered.


Share:Facebooktwitterredditpinterestlinkedinmail

Joint-Groups Sudoku

My students (Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) and I recently wrote a paper connecting the stable marriage problem and Sudoku. I just blogged about it. By the way, my students are in grades 7-9.

On the way, we invented a new type of Sudoku, which we call joint-groups Sudoku. This type is in contrast to a famous type of Sudoku, called disjoint-groups Sudoku. In a disjoint-groups Sudoku, in a particular place in a 3 by 3 box, all the digits are distinct across all the boxes. For example, the top-left corners of nine boxes have all the digits 1 thought 9. This creates nine additional disconnected regions (depending on the placements inside a 3 by 3 box) to add to columns, rows, and boxes that have to contain distinct digits.

For our new type, we wanted the digits in a particular place in each box, instead of being different, to be the same as much as possible. How much of sameness is possible? The first row contains three top-left corners. Thus, by Sudoku rules, these top-left corners have to be distinct. Thus, the top-left corners in all nine boxes have to contain at least three distinct digits. So here is the rule for the joint-groups Sudoku: the nine digits in a particular place in a 3 by 3 box contain not more than three distinct digits. It is easy to see that it means they contain exactly 3 distinct digits, each of them three times.

Here are two Sudoku puzzles from our paper. Each puzzle, when completed, forms a joint-groups Sudoku.

Joint-groups Sudoku

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

Penney’s Game and Groups

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.

Share:Facebooktwitterredditpinterestlinkedinmail

Confirming the Labels of Coins in One Weighing

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.

Share:Facebooktwitterredditpinterestlinkedinmail

The No-Flippancy Game

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.

Share:Facebooktwitterredditpinterestlinkedinmail

SET Tic-Tac-Toe

The academic year is over and my junior PRIMES STEP group finished their paper about a classification of magic SET squares. A magic SET square is a 3 by 3 square of SET cards such that each row, column, and diagonal is a set. See an example below. The paper is posted at the arXiv:2006.04764.

A magic SET square

In addition to classifying the magic SET squares, my students invented the game of SET tic-tac-toe. It is played on nine cards that form a magic SET square. Two players take turns picking a card from the square. The first player who has a set wins.

One might think that this game is the same as tic-tac-toe, as a player wins as soon at they have cards from the same row, column, or diagonal. But if you build a magic SET square, you might notices that each magic SET square contains 12 sets. In addition to rows, columns, and diagonals, there are sets that form broken diagonals. The picture below shows all the sets in a magic SET square.

Sets in magic SET squares

There are more ways to win in this game than in a regular tic-tac-toe game. My students proved that ties are impossible in this game. They also showed, that, if played correctly, the first player always wins.

Share:Facebooktwitterredditpinterestlinkedinmail

Anchored Rectangles

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.

Imcreasing permutation

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.

Decreasing permutation

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)n. The picture shows the configuration for 15 points. The total area is more than one half.


Share:Facebooktwitterredditpinterestlinkedinmail

Meta Logic

Here is a logic puzzle.

Puzzle. You are visiting an island where all people know each other. The islanders are of two types: truth-tellers who always tell the truth and liars who always lie. You meet three islanders—Alice, Bob, and Charlie—and ask each of them, “Of the two other islanders here, how many are truth-tellers?” Alice replies, “Zero.” Bob replies, “One.” What will Charlie’s reply be?

The solution proceeds as follows. Suppose Alice is a truth-teller. Then Bob and Charlie are liars. In this situation Bob’s statement is true, which is a contradiction. Hence, Alice is a liar. It follows, that there is at least one truth-teller between Bob and Charlie. Suppose Bob is a liar. Then the statement that there is one truth-teller between Alice and Charlie is wrong. It follows that Charlie is a liar. We have a contradiction again. Thus, Alice is a liar and Bob is a truth-teller. From Bob’s statement, we know that Charlie must be a truth-teller. That means, Charlie says “One.”

But here is another solution suggested by my students that uses meta considerations. A truth-teller has only one possibility for the answer, while a liar can choose between any numbers that are not true. Even if we assume that the answer is only one of three numbers—0, 1, or 2—then the liar still has two options for the answer. If Charlie is a liar, there can’t be a unique answer to this puzzle. Thus, the puzzle question implies that Charlie is a truth-teller. It follows that Alice must be lying and Bob must be telling the truth. And the answer is the same: Charlie says, “One.”

Share:Facebooktwitterredditpinterestlinkedinmail

Playing with Pascal’s Triangle

The beautiful Pascal triangle has been around for many years. Can you say something new about it?

Pascal Triangle Mod 2

Of course you can. Mathematicians always find new way to look at things. In 2012 RSI student, Kevin Garbe, did some new and cool research related to the triangle. Consider Pascal’s triangle modulo 2, see picture which was copied from a stackexchange discussion.

A consecutive block of m digits in one row of the triangle modulo 2 is called an m-block. If you search the triangle you will find that all possible binary strings of length 2 are m-blocks. Will this trend continue? Yes, you can find any possible string of length 3, but it stops there. The blocks you can find are called accessible blocks. So, which blocks of length 4 are not accessible?

There are only two strings that are not accessible: 1101 and 1011. It is not surprising that they are reflections of each other. Pascal’s triangle respects mirror symmetry and the answer should be symmetric with respect to reflection.

You can’t find these blocks on the picture, but how do we prove that they are not accessible, that is, that you can’t ever find them? The following amazing property of the triangle can help. We call a row odd/even, if it corresponds to binomial coefficients of n choose something, where n is an odd/even number. Every odd row has every digit doubled. Moreover, if we take odd rows and replace every double digit with its single self we get back Pascal’s triangle. Obviously the two strings 1101 and 1011 can’t be parts of odd rows.

What about even rows? The even rows have a similar property: every even-indexed digit is a zero. If you remove these zeros you get back Pascal’s triangle. The two strings 1101 and 1011 can’t be part of even rows. Therefore, they are not accessible.

The next question is to count the number of inaccessible blocks of a given length: a(n). This and much more was done by Kevin Garbe for his RSI 2012 project. (I was the head mentor of the math projects.) His paper is published on the arxiv. The answer to the question can be found by constructing recurrence relations for odd/even rows. It can be shown that a(2r) = 3a(r) + a(r+1) − 6 and a(2r+1) = 3a(r) + 2a(r+1) − 6. As a result the number of inaccessible blocks of length n is n2n + 2. I wonder if there exists a direct proof of this formula without considering odd and even rows separately.

This RSI result was so pretty that it became a question at our entrance PRIMES test for the year 2013. In the test we changed the word accessible to admissible, so that it would be more difficult for applicants to find the research. Besides, Garbe’s paper wasn’t arxived yet.

The pretty picture above is from the stackexchange, where one of our PRIMES applicants tried to solicit help in solving the test question. What a shame.Share:Facebooktwitterredditpinterestlinkedinmail