Archive for September 2009

## Mythematics

In the book “Mythematics: Solving the Twelve Labors of Hercules” Michael Huber adds details to Hercules’ labors so that in order that he can do each task, you need to help Hercules solve two or three math problems. For example, to defeat the Nemean Lion Hercules needs to solve the problem “Zeus Makes a Deal”, which is a Greek-myth version of the Monty Hall problem.

The problems in Mythematics are quite advanced. They range in topic from algebra, geometry and probability to differential equations and integral calculus. Plus, as a reward for helping Hercules, Huber gives you variations on Sudoku puzzles.

Solving some nice math problems might not be the only reason for people to buy this book. Here are some other reasons:

• Greek myth lovers may find extra motivation to do mathematics.
• People will earn that extra gratification of imagining that they are doing good deeds while solving math puzzles.
• Puzzle lovers can learn or refresh their knowledge of Hercules’ labors.

I like Huber’s approach. Future possibilities for more books are endless. Let’s write new math problems based on Harry Potter, Batman, the Bible or, maybe, The Joy of Sex.

## Another Coins Sequence, jointly with Alexey Radul

Konstantin Knop sent me the following coins puzzle, which was created by Alexander Shapovalov and first appeared at the Regional round of the all-Russian math Olympiad in 2000.

Baron Münchhausen has 8 identical-looking coins weighing 1, 2, …, 8 grams. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct one weighing on a balance scale, so that the guests will be convinced about the weight of one of the coins. Can the Baron do this?

This being a sequence-lover blog, we want to create a sequence out of this puzzle. The sequence is the following: Let the Baron initially have n identical-looking coins that weigh exactly 1, 2, …, n grams. Then a(n) is the minimum number of weighings on a balance scale that the Baron needs in order to convince his guests about the weight of one of those coins.

The original puzzle can be restated as asking whether a(8) = 1. The sequence is defined starting from index 1 and the first several terms are easy to calculate: 0, 1, 1, 1, 2, 1, 1, 1. Can you continue this sequence?

Let’s look at where ones occur in this sequence:

Theorem. If the weight of a coin can be confirmed with one weighing, then one cup of that weighing must contain all the coins with weights from 1 to some i, and the other cup must contain all the coins with weights from some j to n. Furthermore, either the scale must balance, or the cup containing the 1-gram coin must be lighter.

Proof. What does it mean for the Baron to convince his guests about the weight of some coin with one weighing? From the perspective of the guests, a weighing is a number of coins in one cup, a number of coins in the other cup, and a number of coins not on the scale, together with the result the scale shows (one or the other cup heavier, or both the same weight). For the guests to be convinced of the weight of some particular coin, it must therefore be the case that all possible arrangements of coin weights consistent with that data agree on the weight of the coin in question. Our proof strategy, therefore, is to look for ways to alter a given arrangement of coin weights so as to change the weight given to the coin whose weight is being demonstrated, thus arriving at a contradiction.

First, obviously, the coin whose weight k the Baron is trying to confirm has to be alone in its group: either alone on some cup or the only coin not on the scale. After that we can divide the proof of the theorem into several cases.

Case 1. The coin k is on a cup and the scale is balanced. Then we want to show two things: k = n, and the coins on the other cup weigh 1, 2, …, i grams for some i. For the first part, observe that if k < n, then the coin with weight k+1 must not be on the scale (otherwise it would overbalance coin k). Therefore, we can substitute coin k+1 for coin k, and substitute a coin one gram heavier for the heaviest coin that was on the other cup, and produce thereby a different arrangement with the same observable characteristics but a different weight for the coin the Baron claims has weight k.

To prove the second part, suppose the contrary. Then it is possible to substitute a coin 1 gram lighter for one of the coins on the other cup. Now, if coin k-1 is not on the scale, we can also substitute k-1 for k, and again produce a different arrangement with the same observable characteristics but a different weight for the coin labeled k. On the other hand, if k-1 is on the scale but k-2 is not, then we can substitute k-2 for k-1 and then k-1 for k and the weighing is again unconvincing. Finally, if both k-1 and k-2 are on the scale, and yet they balance k, then k=3 and the theorem holds.

Consequently, k = n = 1 + 2 + … + i is a triangular number.

Case 2. The coin k is on the lighter cup of the scale. Then: first, k = 1, because otherwise we could swap k and the 1-gram coin, making the light cup lighter and the heavy cup heavier or unaffected; second, the 2-gram coin is on the heavy cup and is the only coin on the heavy cup, because otherwise we could swap k with the 2-gram coin and not change the weights by enough to affect the imbalance; and finally n = 2 because otherwise we could change the weighing 1 < 2 into 2 < 3.

Thus the theorem holds, and the only example of this case is k = 1, n = 2.

Case 3. The coin k is on the heavier cup of the scale. Then k = n and the lighter cup consists of some collection of the lightest available coins, by the same argument as Case 1 (but even easier, because there is no need to maintain the balance). Furthermore, k must weigh exactly 1 gram more than the lighter cup, because otherwise, k-1 is not on the lighter cup and can be substituted for k, making the weighing unconvincing.

Consequently, k = n = (1 + 2 + … + i) + 1 is one more than a triangluar number.

Case 4. The coin k is not on a cup and the scale is not balanced. Then, since k must be off the scale by itself, all the other coins must be on one cup or the other. Furthermore, all coins heavier than k must be on the heavier cup, because otherwise we could make the lighter cup even lighter by substituting k for one of those coins. Likewise, all coins lighter than k must be on the lighter cup, because otherwise we could make the heavier cup even heavier by substituting k for one of those coins. So the theorem holds; and furthermore, the cups must again differ in weight by exactly 1 gram, because otherwise we could swap k with either k-1 or k+1 without changing the weights enough to affect the result on the scale.

Consequently, the weight of the lighter cup is k(k-1)/2, the weight of the heavier cup is 1 + k(k-1)/2. Thus the total weight of all the coins is n(n+1)/2 = k2+1. In other words, case 4 is possible iff n is the index of a triangular number that is one greater than a square.

Case 5. The coin k is not on a cup and the scale is balanced. This case is hairier than all the others combined, so we will take it slowly (noting first that all the coins besides k must be on some cup).

Lemma 1. The two coins k-1 and k-2 must be on the same cup, if they exist (that is, if k > 2). Likewise k-2 and k-4; k+1 and k+2; and k+2 and k+4.

Proof. Suppose they’re not. Then we can rotate k, k-1, and k-2, that is, put k on the cup with k-1, put k-1 on the cup with k-2, and take k-2 off the scale. This makes both cups heavier by one gram, producing a weighing with the same outward characteristics as the one we started with, but a different coin off the scale. The same argument applies to the other three pairs of coins we are interested in, mutatis mutandis.

Lemma 2. The four coins k-1, k-2, k-3 and k-4 must be on the same cup if they exist (that is, if k ≥ 5).

Proof. By Lemma 1, the three coins k-1, k-2, and k-4 must be on the same cup. Suppose coin k-3 is on the other cup. Then we can swap k-1 with k-3 and k with k-4. Each cup becomes heavier by 2 grams without changing the number of coins present, the balance is maintained, and the Baron’s guests are not convinced.

Lemma 3. If coin k-4 exists, that is if k ≥ 5, all coins lighter than k must be on the same cup.

Proof. By Lemma 2, the four coins k-1, k-2, k-3 and k-4 must be on the same cup. Suppose some lighter coin is on the other cup. Call the heaviest such coin c. Then, by choice of c, the coin with weight c+1 is on the same cup as the cluster k-1, …, k-4, and is distinct from coin k-2 (because c is on a different cup from k-3). We can therefore swap c with c+1 and swap k with k-2. This increases the weight on both cups by 1 gram without changing how many coins are on each, but moves k onto the scale. The Baron’s guests are again unconvinced.

Lemma 4. The theorem is true for k ≥ 5.

Proof. By Lemma 3, all coins lighter than k must be on the same cup. Further, if a coin with weight k+4 exists, then by the symmetric version of Lemma 3, all coins heavier than k must also be on the same cup. They must be on the other cup from the coins lighter than k because otherwise the scale wouldn’t balance, and the theorem is true.

If no coin with weight k+4 exists, that is, if n ≤ k+3, how can the theorem be false? All the coins lighter than k must be on one cup, and their total weight is k(k-1)/2. Further, in order to falsify the theorem, at least one of the coins heavier than k must also be on that same cup. So the minimum weight of that cup is now k(k-1)/2 + k+1. But we only have at most two coins for the other cup, whose total weight is at most k+2 + k+3 = 2k + 5. For the scale to even have a chance of balancing, we must have

k(k-1)/2 + k+1 ≤ 2k + 5 ⇔ k(k-1)/2 ≤ k + 4 ⇔ k(k-1) ≤ 2k + 8 ⇔ k2 - 3k - 8 ≤ 0.

Finding the largest root of that quadratic we see that k < 5.

So for k ≥ 5, the collection of all coins lighter than k is heavy enough that either one needs all the coins heavier than k to balance them, or there are enough coins heavier than k that the theorem is true by symmetric application of Lemma 3.

Completion of Case 5. It remains to check the case for k < 5. If n > k+3, then coin k+4 exists. If so, all the coins heaver than k must be on the same cup. Furthermore, since k is so small, they will together weigh more than half the available weight, so the scale will be unbalanceable. So k < 5 and n ≤ k+3 ≤ 7.

For lack of any better creativity, we will tackle the remaining portion of the problem by complete enumeration of the possible cases, except for the one observation that, to balance the scale with just the coin k off it, the total weight of the remaining coins, that is, n(n+1)/2 - k must be even. This observation cuts our remaining work in half. Now to it.

Case 5. Seven Coins. n = 7. Then 5 > k ≥ n - 3 = 4, so k = 4. Then the weight on each cup must be 12. One of the cups must contain the 7 coin, and no cup can contain the 4 coin, so the only two weighings the Baron could try are 7 + 5 = 1 + 2 + 3 + 6, and 7 + 3 + 2 = 1 + 5 + 6. But the first of those is unconvincing because k+1 = 5 is not on the same cup as k+2 = 6, and the second because it has the same shape as 7 + 3 + 1 = 2 + 4 + 5 (leaving out the 6-gram coin instead of the asserted 4-gram coin).

Case 5. Six Coins. n = 6. Then 5 > k ≥ n - 3 = 3, and n(n+1)/2 = 21 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 9. The 6-gram coin has to be on a cup and the 3-gram coin is by presumption out, so the Baron’s only chance is the weighing 6 + 2 + 1 = 4 + 5, but that doesn’t convince his skeptical guests because it looks too much like the weighing 1 + 3 + 4 = 6 + 2.

Case 5. Five Coins. n = 5. Then 5 > k ≥ n - 3 = 2, and n(n+1)/2 = 15 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 6. The only way to do that is the weighing 5 + 1 = 2 + 4, which does not convince the Baron’s guests because it looks too much like 1 + 4 = 2 + 3.

Case 5. Four Coins. n = 4. Then the only way to balance a scale using all but one coin is to put two coins on one cup and one on the other. The only two such weighings that balance are 1 + 2 = 3 and 1 + 3 = 4, but they leave different coins off the scale.

The remaining cases, n < 4, are even easier. That concludes the proof of Case 5.

Consequently, by the argument similar to the one in case 4 we can show that the number of coins in case 5 must be the index of a square triangular number.

This concludes the proof of the theorem.

Now we can describe all possible numbers of coins that allow the Baron to confirm a coin in one weighing, or, in other words, the indices of ones in the sequence a(n). The following list corresponds to the five cases above:

1. n is a triangular number. For example, for six coins the weighing is 1+2+3 = 6.
2. n = 2. The weighing is 1 < 2.
3. n is a triangular number plus one. For example, for seven coins the weighing is 1+2+3 < 7.
4. n is the index of a triangular number that is a square plus one. For example, the forth triangular number, which is equal to ten, is one greater than a square. Hence the weighing 1+2 < 4 can identify the coin that is not on the cup. The next number like this is 25. And the corresponding weighing is 1+2+…+17 < 19+20 +…+25.
5. n is the index of a square triangular number. For example, we know that the 8th triangular number is 36, which is a square: our original problem corresponds to this case.

If we have four coins, then the same weighing 1+2 < 4 identifies two coins: the coin that weighs three grams and is not in a cup and the coin weighing four grams that is in a cup. The other case like this is for two coins. Comparing them to each other we can identify each of them. It is clear that there are no other cases like this. Indeed, for the same weighing to identify two different coins, it must be the n-gram on the cup, and the n-1 coin off the scale. From here we can see that n can’t be big.

As usual we want to give something to think about to our readers. We have given you the list of sequences describing all the numbers for which the Baron can prove the weight of one coin in one weighing. Does there exist a number greater than four that belongs to two of these sequences? In other words, does there exist a total number of coins such that the Baron can have two different one-weighing proofs for two different coins?

To conclude this essay we would like to note that the puzzle we are discussing is related to the puzzle in one of Tanya’s previous posts:

You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

The latter puzzle appeared at the last round of Moscow math Olympiad in 1991. The author of this problem was Sergey Tokarev.

## The Defining Moment

I would like to tell you a story from my childhood and how I started on my math path.

When I was in elementary and middle school, I was very good with mathematics. Actually, I was by far the best math student in my class and my math teacher didn’t know what to do with me. Our algebra book had 2,000 problems and was intended to cover three years of study. But I worked out those problems, one after another, whenever I had a free minute in my math class. As I result, I got way ahead of everyone else.

One day a new boy named Lenya Kostyukov joined our class. He had extraordinarily long eye-lashes that covered his eyes, and all the girls envied him. He was a nice smart kid, but other than his lashes, I didn’t notice him very much. After a year or two, he announced that he was leaving our school, because he had been accepted to a math school for gifted children.

“Why is he going to a math school? I am the math star here. Why aren’t I going to a math school?” I knew about math schools, and I knew that I was good at math; I just never made the connection. I never felt that I was supposed to apply. Despite enjoying my reputation, I just passively went with the flow. Lenya figuratively kicked me in the butt. If he can, why can’t I?

So I applied to the same school on the last permissible day and was accepted. It turned out that I accidentally went to the room where they were giving the test for a grade higher than mine. I passed it with flying colors. My parents, though, were scared of a long commute and didn’t really want me to go so far away. They found a different math school closer to home, and used my extraordinary results to convince that school to accept me, even though their application date had passed.

For many years I continued to be a very passive person. Applying to a math school was the single big step I took for myself, but it was a defining step. I am grateful to Lenya for that. Or more likely to his parents, who were actively looking around trying to find the best place for their gifted son, and as a byproduct found a place for me. Once I was on the path of mathematics, I had the guidance of teachers and supervisors, for better or for worse, which allowed me to continue to be passive.

I have described my defining moment to you, but I don’t want to leave you in the dark about Lenya’s fate. Here’s what happened to him.

As I mentioned, Leonid (Lenya’s formal name) and I ended up in different math schools, so I lost track of him. Four years later I went to study math at Moscow State University and stumbled upon a guy with very long eye-lashes. We recognized each other immediately and eventually became friends.

He was doing logic and was very good at it. He was recommended for graduate school. But by that time our MSU administration noticed his lashes too. The lashes were obviously very suspicious; they hinted at the existence of non-Russian blood in his veins. As it was the period of brutal anti-semitism at MSU, they didn’t allow him to go to graduate school.

Leonid Kostyukov dropped mathematics and became a famous writer.

## Papaya Words and Numbers, jointly with Sergei Bernstein

Here is a strange puzzle that was inspired by the palindrome problem. Suppose you have a sequence of words in some alphabet with the initial term a and all the other terms b: a, b, b, b, b, etc. Suppose this sequence generates palindromes every time you concatenate the first several terms, not counting the first term itself. So, ab, abb, abbb, and so on — are all palindromes. We call words b “papaya” words, when a exists, such that a and b generate the sequence with this palindrome property. Can you describe papayas?

Theorem. The word b is a papaya word if and only if b is a substring of Reverse(b)Reverse(b).

Proof. After we have added b so many times that the initial part a is much smaller than half of the concatenated string, the middle part of the concatenated string would consist of several words copies of the word b. The middle of the reverse string consists of several concatenations of Reverse(b). So the word b must be a substring of Reverse(b)Reverse(b). On the other hand, suppose b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby, and we can choose a = y.

Theorem. Papaya words are either palindromes or concatenations of two palindromes.

Proof. Suppose our word consists of two palindromes cd. Then the reverse of it is dc and its double is dcdc. The word cd is a substring of dcdc, thus according to the first theorem, cd is a papaya word. Let’s do the other direction. Suppose the word b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby. Then b = yx, and Reverse(b) = xy, which equals Reverse(x)Reverse(y). From here, Reverse(x) = x and Reverse(y) = y. If x or y has zero length, then our word is a palindrome. QED.

Hey, do you already know why we call these words papayas?

Just for fun we would like to study the structure of papaya words. Any one-character or two-character word is a papaya word, so the patterns are: a, aa, ab. For three-character words there are four patterns: aaa, aab, aba, abb. For four-character words there are 10 patterns: aaaa, aaab, aaba, abaa, aabb, abab, abba, abbb, abac, abcb. In this manner we get the sequence of the number of n-character papaya patterns: 1, 2, 4, 10, 21, 50 etc, which is sequence A165137 in the OEIS. This sequence depends on the number of letters in your alphabet. But the first n terms of these sequences are the same for all alphabets that have at least n letters.

Let us assume that we are working with an infinite alphabet. The complementary sequence would be the number of patterns for non-papaya words. The total number of patterns is described by sequence A000110 — Bell numbers: the number of word structures of length n using an infinite alphabet. So the beginning of this complementary sequence A165610 is: 0, 0, 1, 5, 31, 153, etc. The list of corresponding patterns is abc, aabc, abbc, abcc, abca, abcd, etc.

Historically, we first invented the corresponding sequence for numbers, not for words. We call a number a papaya number if it is a palindrome or a concatenation of two palindromes. If we use numbers instead of words in the problem, we need to carefully look at what happens if we encounter initial zeroes. Let’s take the papaya number 2200100, and see if we can find a number a, such that adding 22010 repeatedly to this sequence starting with a will always generate a palindrome. The number a must be 00100. But this is not a number. We have two choices: to say that we are working with strings of digits, or to allow several numbers to start the sequence before we add b repetitively and before getting to palindromes. In the latter case our sequence can start 0, 0, 100, 22010, 22010, and so on.

As we mentioned before, the number of patterns of papaya numbers will start the same as the number of patterns of papaya words. Later the sequence of patterns of numbers A165136 will be smaller than the corresponding sequence for words. As the sequence of Bell numbers is much more famous than the sequence A164864 of patterns of numbers, we expect the papaya patterns sequence corresponding to the infinite alphabet to be more interesting and important than the sequence of papaya patterns for numbers.

Though papaya numbers might be less important than papaya words with an infinite alphabet, they have an advantage in that we can generate more sequences with them. For example we can calculate the number of positive papaya number with n digits, as in the sequence A165135: 9, 90, 252, 1872, 4464, 29250, etc. And we can also calculate the sequence A165611 of n-digit non-papaya numbers: 0, 0, 648, 7128, 85536 etc.

## Points on the Plane

This geometric problem was given to me by Arkady Berenstein:

There are n points on the plane, but not all of them are on one line. Prove that a line exists that passes through exactly two points of this set.

Arkady gave me a beautiful solution to this problem. First, draw a line through each pair of points. Suppose you calculate all the distances from each point to all the lines that the point doesn’t belong to. Pick the smallest distance. The corresponding line will be the one with two points. To finish the solution you need to fill in the details. That process is usually left to the reader.

I suspect that there might also be a solution using linear algebra. Can you find one?

I would like to reformulate this problem without using geometry. Suppose there is a set of n elements. Let’s call a family of subsets line-like if any two distinct subsets of this family can have as an intersection not more than one element. Then the geometry problem above has a set-theoretical analogue:

You have a set of n elements and a line-like family of subsets of this set such that any two elements of the set belong to a subset from this family, and that the family doesn’t contain the whole set. Is it true that there always exists a subset in this family consisting of two elements?

Usually I give such problems as homework for the reader, but this time I decided to change my habit, so I’m including the picture which contains the solution of this problem by my son Alexey Radul.

Conclusion: geometry is important.

## Why is the South Pole Colder than the North Pole?

I remember this question from my childhood:

Why is the South Pole colder than the North Pole?

Indeed, the average winter temperature at the North Pole of -34°C is the same as the temperature at the South Pole at the beginning and end of its summer. The South Pole is only warmer than the North Pole 40 days per year. So the South Pole is a much, much colder place. According to Wikipedia there are three major reasons for this:

1. The North Pole is at sea level, while the South Pole is elevated to almost three kilometers. The higher a land mass the colder it is.
2. The North Pole sits on water whose temperature never goes below -2°C. Compared to the South Pole, this is like keeping the North Pole on the stove top.
3. The South Pole is farther from the ocean, so it has higher continentality, which is usually associated with colder temperatures.

I remember when I was a child my father gave me a completely different explanation.

The Earth’s orbit is not a circle, but rather an ellipse. According to Kepler’s second law: “A line joining a planet and the sun sweeps out equal areas during equal intervals of time.” This means that the earth has a slower angle motion around the aphelion — in its furthest point — than around the perihelion — in its closest point to the Sun. Consequently, the summer is longer than the winter for the North Pole, whereas the opposite is true for the South Pole.

Something in my father’s explanation bothered me. Now I understand what: though the summer is longer at the North Pole, it should get less sunshine as the North Pole is further away from the Sun than the South Pole during its summer. So the effects might cancel each other out. In any case, as the earth’s orbit is almost circular, the contribution of the shape of the orbit should be minor, compared to the effects of elevation, the water underneath and continentality.

On the other hand, it is possible that my father wasn’t talking about the poles, but rather about the difference in hemispheres. I wonder if someone can calculate if there is a difference in the amount of sunlight the poles get due to the fact that the Earth’s orbit is not circular. Is the temperature different for the places that are equidistant from the equator, and have similar elevation and continentality, but which are located in different hemispheres?

I remember a funny article explaining why the northern hemisphere has more land. They said that continents drifted into the northern hemisphere because they wanted a nicer climate.

## Heard on the Street

I bought the book Heard on The Street: Quantitative Questions from Wall Street Job Interviews” by Timothy Falcon Crack several years ago when I was looking for a job and felt that working in finance was a possibility. Despite having bought it simply to prepare for employment interviews, I actually enjoyed the math problems in the book.

The book has problems in logic, probability, statistics and finance, as well as a very useful chapter of general interview questions. If you’re interested in buying this book, I should mention that some questions require calculus and knowledge of financial terms.

I love the author’s taste in problems, and here are some sample questions from the book.

Question 2.7: How many degrees (if any) are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?

Question 5.1.14: Welcome to your interview. Sit in this chair. Excuse me while I tie your arms and legs to the chair. Thank you. Now we are going to play “Russian roulette.” I have a revolver with six empty chambers. Watch me as I load the weapon with two contiguous rounds (i.e., two bullets side-by-side in the cylindrical barrel). Watch me as I spin the barrel. I am putting the gun against your head. Close your eyes while I pull the trigger. This is your lucky day: you are still alive! Our game differs from regular Russian roulette because I am not going to add any bullets to the barrel before we continue, and I am not going to give you the gun.
My question for you: I am going to shoot at you once more before we talk about your résumé. Do you want me to spin the barrel once more, or should I just shoot?

Question 6.1.16: Tell me something you tried but ended up quitting on.

I can tell you what I would have answered to the last question: I tried smoking, but ended up quitting.

## Gay Polygamy

Mathematically we can describe a marriage by a graph. People are vertices and two spouses are connected by an edge.

Mathematical models tend to oversimplify life, so let us assume that a person can only be one of two genders. Therefore, the vertices of a graph are colored in two colors: pink and blue. In this article I explore the graph theory of different types of marriages.

A monogamous couple is represented as a complete K2 graph: two vertices connected by an edge. The graph is bipartite, no matter how you color it. But actually our vertices are already colored from the start. If we are considering traditional marriage, one vertex is pink and the other is blue.

Historically, the second most common type of marriage is polygyny, in which one man has several wives. Less common in history, but a mathematically equivalent type, is polyandry, in which one woman has several husbands. Both these types of marriages emphasize inequality, as husbands and wives have completely different sets of rights.

From a mathematical point of view, polygyny and polyandry are described by star graphs. Star graphs are bipartite graphs and the natural coloring is the one that proves bipartiteness.

The final type of marriage is polygynandry, which refers to a group marriage, where more than one man and more than one woman create a family. Everyone can have sex with everyone else of the other gender. Mathematically this type of marriage corresponds to a complete bipartite graph Kn,m. Actually, in this case I can imagine that a particular pair of people of different genders wouldn’t like each other and might not consummate their marriage. So this graph is not necessarily complete.

How can same-sex marriages change the graph theory of marriages? As a graph, a monogamous same-sex marriage is the same bipartite K2 graph as a heterosexual marriage. It will just be less colorful, as both vertices will be of the same color.

But what happens if we add the same-sex idea to polygamous marriages?

Suppose a homosexual man wants to live with several spouses at the same time. What name can we give to a family unit of more than two homosexual men? Homopolygamy? Their marriage graph will be a star graph in which all the vertices are of the same color.

If a man can have several spouses, what about his spouses? Can they form multiple marriages too? If only one person is allowed to engage in several marriages, then we will see inequality within the same gender. If any spouse is allowed to form other marriages, then we will have a situation in which several men are all spouses to each other. So mathematically we will see complete graphs with more than two vertices to represent a marriage. If two people in a group do not like each other and do not want to be married, then the corresponding graph doesn’t need to be complete.

By symmetry we can describe a marriage of several women, and mathematically it will be similar to a marriage of several men.

Another interesting aspect is the idea of mixed types of marriages involved in polygamy. Suppose a husband has several wives. Some of them might get bored waiting for his attention, and start spending so much time with each other that they end up developing feelings for each other. Suppose two wives of the same man decide to marry each other. What name would we give to this type of marriage? I am afraid that we do not have enough words to cover all the potential situations.

Suppose we have a heterosexual married couple and the man decides to bring another woman into their house. Thus the transition from a traditional marriage to a polygyny is created. If they got along so well that the first wife decides to marry the second wife, this would require a transition to a new type of marriage. Oh, I see that my essay just went in another direction — how different types of marriages might evolve into each other. For now, I’ll leave this for future research.

Talking about different directions. I recently wrote a piece about condoms. Now I have a new generalization for the classic condom puzzle. Suppose we have a mixed-type marriage defined by a graph. Suppose tonight every couple of people corresponding to the edge of this graph wants to have sex with each other. What is the smallest number of condoms they can use? In my condom essay, I didn’t define the condom usage for the sex of two women. I will leave it to your imagination and definition.

## Archive Labeling Sequences, jointly with Gregory Marton

What follows is the story of a pair of integer sequences, which started life as a Google interview puzzle back in the previous century when VHS video tapes were in use:

Suppose you are buying VHS tapes and want to label them using the stickers that came in the package. You want to number the tapes consecutively starting from 1 and the stickers that come with each package are exactly one of each digit [”0″…”9″]. For your first tape you use only the digit “1″, and save all the other digit stickers for later tapes. The next time you will need a digit “1″ will be for tape number 10. By this time you will have several unused “1″ stickers. What is the next tape number such that after labeling the tape with that number you will not have any “1″ stickers remaining?

We can formalize this puzzle in the following way:

Consider a function f which, for a given whole number x, returns the number of times that the digit 1 is needed to write all of the numbers between one and x. For example, f(13) = 6. Notice that f(1) = 1. What is the next largest x such that f(x) = x?

Thus f(x) is the number of “1″ stickers needed to label all the tapes up to tape x. When f(x) = x then we have used all of the “1″ stickers in labeling the first x tapes.

Let’s consider any non-zero digit. In the single and double-digit numbers, there are ten of each digit in the ones column, and ten of each digit in the tens column, so 20 altogether. Early on, the tape number is ahead of the digit count. By the time we get to 20-digit numbers, though, there should be, on average, two of any single non-zero digit per number. Thus, the number of times that any digit is used should eventually catch up with the tape numbers.

Encouraged by assurance of reaching our goal somewhere, we might continue our estimate. In the up-to three-digit numbers there are 300 of each non-zero digit; in the numbers below 10,000 there are 4000; then 50,000, and so on up to 1010, where f(x) and x must (almost) meet. In particular, there are 10,000,000,000 counts for any non-zero digit in the numbers below 10,000,000,000. Hence, were the puzzle asking about any of the digits 2–9, then ten billion could have been an easy answer or, at least a limit on how far we need to search.

Sadly, there is a 1 in the decimal representation of ten billion (and a few zeroes), so we require 1010+1 of the digit “1″ to write the numbers [1…1010]. Thus, f(1010) ≠ 1010, so 1010 cannot be the answer to the original puzzle. Thus stymied, Gregory wrote a program to find the solution to the original Google’s puzzle. And the answer turned out to be 199,981.

Gregory was overstymied, so he actually wrote a program to solve the puzzle for any non-zero digit. He calculated the beginning of the sequence a(n), where a(n) is the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] exactly x times.

We already know that a(1) is 199,981. The sequence continues as follows: 199,981,   28,263,827,   371,599,983,   499,999,984,   10,000,000,000,   9,500,000,000,   9,465,000,000,   9,465,000,000,   10,000,000,000, ….

Did you expect this sequence to be increasing? You could have, because smaller numbers tend to contain smaller digits than larger numbers. Then why is the sequence not increasing? As Gregory failed to find a value for the digit 5 below ten billion, he noticed that it’s fairly easy to imagine a scenario where you have one less than the number you need, and then the next value has more than you need for equality, and then you equalize again later. In response, Alexey Radul, a friend of one author and a son of the other, suggested a related sequence:

Let a(n) be the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] more than x times.

The key difference being “more than” rather than “exactly”. Starting at 1 then, here are the first nine terms of each sequence:

n = >
1 199,981 199,991
2 28,263,827 28,263,828
3 371,599,983 371,599,993
4 499,999,984 499,999,994
5 10,000,000,000 5,555,555,555
6 9,500,000,000 6,666,666,666
7 9,465,000,000 7,777,777,777
8 9,465,000,000 8,888,888,888
9 10,000,000,000 9,999,999,999

Some of these pairs are interesting in their own right. Notice that 199,991 is ten more than the previously found 199,981. For all the numbers in between, the initial equality holds. Likewise for n=3, each of the numbers between 371,599,983 and 371,599,993 has exactly one three. Hence, the increase in a number by one is the same as the increase in the count of threes. A similar situation holds for n=4.

Gregory has submitted these two new sequences to the Online Encyclopedia of Integer Sequences, as they turned out not to be there yet, and they can be found using the identifiers A163500 for the “=” sequence and A164321 for the “>” sequence. It’s not surprising that the values matching this relaxed second condition are more well behaved than those with equality. Do you think the second sequence is always increasing? Wait a minute, let’s check that sequence for zero.

In counting zeroes, it is important to remember that we start with one, not zero. In this case the smallest number x such that x is less than or equal to the number of 0s in the decimal representations of [1 … x] is 100,559,404,366. But what is the corresponding number for the “=” sequence? It appears that no such number exists. The challenge of accurately proving it, as they say, is left as an exercise to the reader.

There is no reason that we should be constrained to single digits. The formal statement of the problem provides an obvious generalization, where we consider substrings of each of the numbers [1 … x] rather than digits in those numbers. We should note that we count every occurrence of a substring separately. Thus 11 will be counted twice as a substring of 1113.

We can prove that the “more than” sequence is increasing after the first term. Indeed, for two integers i and j, if i is less than j, then for every occurrence of j, by replacing j with i we get a smaller number with an occurrence of i.

Inspired, Tanya wrote another fancier and faster program to find values of this sequence for two-digit numbers. Here is the smallest number x for which the number of “10″s as substrings of the numbers [1…x] is more than or equal to x. And by a lucky strike the equality holds. The number is: 109,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,810. Now the reader can do an exercise and find the number for the “more than” sequence.

The value of a(11) might seem like a miracle: 119,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,811. Note how strikingly similar it is to the tenth element of the sequence! Can you explain that similarity between a(10) and a(11)?

Sadly, a(12) is not so pretty: 1,296,624,070,230,872,986,615,199,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,812.

We cannot leave off without at least mentioning that the sequence function should next take one more parameter: the base of representation.

We have found only the first few members of these new sequences, and there are many related sequences to be catalogued. We would love to hear tales from your explorations. Enjoy the sequence hunt!

## Fine Dining with a Pizza Puzzle

Peter Winkler gave a talk at MIT last fall and, as is customary, the audience was invited to join him for dinner afterwards at a local restaurant. I was eager to dine with Peter because he is a puzzle collector and I was hoping to hear a new puzzle. I got what I was hoping for — tripled. We got a pizza puzzle, a cake puzzle and a tart puzzle to complement our dinner. Today I will discuss the pizza puzzle.

Peter is now a columnist at ACM communications. His column is called “Puzzled” and it is featured as part of the section titled “Last Byte.” Writing these paragraphs has made me so hungry that I need to go grab something to bite.

Okay, I am back and here is the pizza puzzle.

Alice and Bob ordered a pizza. The pizza is cut into several radial pieces. Both Alice and Bob are greedy and well-mannered at the same time. They each want to get as much pizza as possible for themselves, but they don’t want to be obvious about it. They take pieces in turn, starting with Alice. Because they are well-mannered and not obvious, when it is their turn, they only take a piece that is adjacent to the pieces already taken. Throughout the process of consuming this pizza, the untaken pieces are contiguous.

The question is: Is it possible to cut the pizza in such a way that although Alice starts, Bob can guarantee himself more than half?

If you want to think about this puzzle on your own, now would be a good time to pause. Why? Because in the next paragraph, I will give you some hints about how to approach this question.

If the number of pieces is even, then Alice can’t lose. She can number the pieces around the circle consecutively, decide whether all the odd pieces or all the even pieces make up a bigger chunk, and then follow the parity.

But what happens if there are an odd number of pieces? Alice has an advantage, for she will get more pieces. But is that enough to guarantee that she will get at least half? Suppose she starts by taking a minuscule piece. Then Bob can number all of the leftover pieces in order and decide if he prefers the even-numbered group or the odd-numbered group. He is in control now, so he can guarantee himself the bigger part of the leftover pieces.

However, that might not be good enough for Bob to win. For example, if there is a very big piece, one that is bigger than half of the pizza, then in the first move Alice wins.

On the other hand, would Alice necessarily win by starting with the biggest piece?

Suppose the biggest piece is significantly less than half. Would Bob have a chance? To his advantage, he does have a lot of control. He can choose the parity of the pieces he wants at the beginning, and he can also switch this parity later, depending on what Alice does. Does he control the situation enough that it would be possible to cut the pizza in his favor?

I have to add that if you can find a solution with N pieces, then you can easily build a solution with N+2 pieces. Suppose you start with a pizza cut into N pieces, such that Bob will win. If you add two adjacent pieces of zero value to this pizza, you will get a pizza cut into N+2 pieces, such that Bob can still win. Indeed, Bob will follow the strategy he used with the N-pieces pizza, except that each time Alice takes one of the new pieces, Bob takes the other.

Can you find a way to cut a pizza so that Bob can guarantee himself more than half?