Archive for March 2011

## Subtleties of Lies

In a puzzle book by Mari Berrondo (in Russian), I found the following logic problem:

Alfred, Bertran and Charles are asked about their profession. One of them always lies; another one always tells the truth; and the third one [who I will refer to as a “half-liar”] sometimes lies and sometime tells the truth. Here are their answers:

Bertran: I am a painter, Alfred is a piano-tuner, Charles is a decorator.
Alfred: I am a doctor, Charles is an insurance agent. Concerning Bertran, if you ask him, he will tell you that he is a painter.
Charles: Alfred is a piano-tuner. Bertran is a decorator, and I am an insurance agent.
What is the profession of the half-liar?

The solution in the book is the following. As Alfred is right about what Bertran would say, Alfred can’t be a liar. If Alfred is a half-liar then the other two people would give the opposite statements, since one will be a truth-teller and the other a liar. But they both say that Alfred is a piano-tuner, therefore Alfred must be a truth-teller. Hence, Alfred’s statement about everyone’s profession must be the truth. Now we know that Charles is an insurance agent. As Charles confirms that, thus telling the truth in this instance, we recognize that he must be a half-liar. The answer to the problem is that the half-liar is an insurance agent.

But I have a problem with this problem. You see, a liar can say many things. He can say that he is a conductor, a mathematician, a beekeeper or whatever. So there is no way of knowing what a person who decides to lie can say. Let’s just analyze the statement by Alfred: “Concerning Bertran, if you ask him, he will tell you that he is a painter.”

If Alfred tells the truth about what Bertran would say, he needs to know for sure that Bertran will say that he is a painter. Hence, Bertran must be a truth-teller and a painter. If Alfred lies, he needs to be sure that Bertran won’t say that he is a painter. So Bertran must be either a truth-teller and not a painter, or a liar and a painter. Bertran can’t be a half-liar, because a half-liar can say that he is a painter as well as he can say something else, no matter what his real profession.

There is one interesting aspect of this that many people overlook. There are different types of people who are half-liars. In some books half-liars are introduced as people who, before making a statement, flip a coin to decide whether to lie or to tell the truth. Such a person needs to know in advance exactly what other people are saying, in order to construct a statement about what those people might say that corresponds to the coin flip. On the other hand, other types of half-liars exist. One half-liar can say something and then see later whether it is true. If Alfred is a half-liar who doesn’t care in advance about the truth of his statement, he can say that Bertran will claim that he is a painter.

I leave it to my readers to finish my analysis and see that the problem doesn’t have a solution. To end my essay on a positive note, I decided to slightly change the problem, so that there is no contradiction. In the same setting:

Bertran: I am a painter, Alfred is a piano-tuner, Charles is a decorator.
Alfred: I am a doctor, Charles is an insurance agent. Concerning Bertran, if you ask him, he will tell you that he is not a painter.
Charles: Alfred is a piano-tuner. Bertran is a decorator, and I am an insurance agent.
What is the profession of the half-liar?

## Why Are We Losing Female Mathematicians?

The data from annual surveys carried out by the American Mathematical Society shows the same picture year after year: the percentage of females in different categories decreases as the category level rises. For example, here is the data for 2006:

Category Percentage of Women
PhDs Granted 32
Fresh PhD hires in academic jobs 27
Full-time Faculty 27
Full-time tenured or tenure-track faculty 12

The high percentage of female math majors means that a lot of women do like mathematics. Why aren’t women becoming professors of mathematics? In the picture to the left, little Sanya fearlessly took her first integral. I hope, even as an adult, she will never be afraid of integrals.

I am one of the organizers of the Women and Mathematics Program at the Institute for Advanced Study at Princeton In 2009 we had a special seminar devoted to discussing this issue. Here is the report of our discussion based on the notes that Rajaa Al Talli took during the meeting.

Many of us felt, for the following three reasons, that the data doesn’t represent the full picture.

First, the different stages correspond to women of different ages; thus, the number of tenured faculty should be compared, not to the number of current math majors, but rather to women who majored in math many years ago. The percentage of female PhDs in mathematics has been increasing steadily for the past several years. As a result, we expect an eventual increase in the number of full-time female faculty.

Second, international women mathematicians might be having a great impact on the numbers. Let’s examine a hypothetical situation. If many female professors come to the US after completing their studies in other countries, it would be logical to assume that they would raise the numbers. But since the numbers are falling, we might be losing more females than we think. Or, it could be the opposite: international graduate students complete a PhD in mathematics in the USA and then go back to their own countries. In this case we would be losing fewer females to professorships than the numbers seem to suggest. Unfortunately, we can’t really say which case is true as we do not know the data on international students and professors.

Third, many women who major in mathematics also have second majors. For example, the women who have a second major in education probably plan to become teachers instead of pursuing an academic career. It would be interesting to find the data comparing women who never meant to have careers in science with those women who left because they were discouraged. If we are losing women from the sciences because they decide not to pursue scientific careers, then at least that is their choice.

It is also worth studying why so few women are interested in careers in mathematics in the first place. Changing our culture or applying peer pressure in a different direction might change the ambitions of a lot of people.

We discussed why the data in the table doesn’t represent the full picture. On the other hand, there are many reasons why women who can do mathematics and want to do mathematics might be discouraged from pursuing an academic career:

• Marriage and children distract from mathematics.
• The lack of legal protections for pregnant women, of required maternity leave and of childcare provision.
• The cultural skepticism that women can do math on a high level.
• An educational system that tends to tell students that math is very difficult, thus discouraging women from the early stages of their academic life.
• Boys tend to be more competitive than girls.
• The lack of job opportunities.
• A career in math often requires moving.

Our group proposed many solutions to help retain women in mathematics:

1. Find a way to get men pregnant as well.
2. Incorporate ideas from other countries (like Portugal), where they don’t have this problem.
3. Increase the level of social care for pregnant women and young children.
4. Create new laws to protect the rights of pregnant women.
5. Educate secondary, high school and college math teachers how to present math — such as through games — as an interesting subject, not as a difficult one.

At the end of our meeting, everyone accepted Ingrid Daubechies‘ proposal that we do the following:

Each woman in mathematics should take as her responsibility the improvement of the mathematical environment in which she works. If every woman helps change what’s going on in her university or the school where she teaches, that will help solve the problem on the larger scale.

## Should You Date a Mathematician?

The book How to Drive Your Man Wild in Bed by Graham Masterton has a chapter on how to choose a lover. It highlights red flags for men who need to be approached with caution. There is a whole list of potentially bad signs, including neglecting to shower in the previous week and talking only about himself.

The list of bad features also includes professions to avoid. Can you guess the first profession on the list? OK, I think you should be able to meta-guess given the fact that I am writing about it. Indeed, the list on page 64 starts:

Avoid, on the whole, mathematicians…

I am an expert on NOT avoiding mathematicians: in fact, I’ve married three of them and dated x number of them. That isn’t necessarily because I like mathematicians so much; I just do not meet anyone else.

When I was a student I had a theory that mathematicians are different from physicists. My theory was based on two conferences on mathematical physics I attended in a row. The first one was targeted for mathematicians and the second for physicists. The first one was very quiet, and the second one was all boozing and partying. So I decided that mathematicians are introverts and physicists are extroverts. I was sure then that my second husband chose a wrong field, because he liked booze and parties.

By now, years later, I’ve met many more mathematicians, and I have to tell you that they are varied. It is impossible and unfair to describe mathematicians as a type. One mathematician even became the star of an erotic movie. I write this essay for girls who are interested in dating mathematicians. I am not talking about math majors here, I am talking about mathematicians who do serious research. Do I have a word of advice?

I do have several words of caution. While they don’t apply to all mathematicians, it’s worth keeping them in mind.

First, there are many mathematicians who, like my first husband, are very devoted to mathematics. I admire that devotion, but it means that they plan to do mathematics on Saturday nights and prefer to spend vacation at their desks. If they can only fit in one music concert per year, it is not enough for me. Of course, this applies to anyone who is obsessed by his work.

Second, there are mathematicians who believe that they are very smart. Smarter than many other people. They expand their credibility in math to other fields. They start going into biology, politics and relationships with the charisma of an expert, when in fact they do not have a clue what they are talking about.

Third, there are mathematicians who enjoy their math world so much that they do not see much else around them. The jokes are made about this type of mathematician:

What is the difference between an extroverted mathematician and an introverted one? The extroverted one looks at your shoes, rather than at his own shoes.

Yes, I have met a lot of mathematicians like that. Do you think that their wives complain that their husbands do not notice their new haircuts? No. Such triviality is not worth mentioning. Their wives complain that their husbands didn’t notice that the furniture was repossessed or that their old cat died and was replaced by a dog. My third husband was like that. At some point in my marriage I discovered that he didn’t know the color of my eyes. He didn’t know the color of his eyes either. He wasn’t color-blind: he was just indifferent. I asked him as a personal favor to learn the color of my eyes by heart and he did. My friend Irene even suggested creating a support group for the wives of such mathematicians.

While you need to watch out for those traits, there are also things I like about mathematicians. Many mathematicians are indeed very smart. That means it is interesting to talk to them. Also, I like when people are driven by something, for it shows a capacity for passion.

Mathematicians are often open and direct. Many mathematicians, like me, have trouble making false statements. I stopped playing —Mafia— because of that. I prefer people who say what they think and do not hold back.

There is a certain innocence among some mathematicians, and that reminds me of the words of the Mozart character in Pushkin’s poetic drama, Mozart and Salieri: —And genius and villainy are two things incompatible, aren’t they?— I feel this relates to mathematicians as well. Many mathematicians are so busy understanding mathematics, they are not interested in plotting and playing games.

Would I ever date a mathematician again? Yes, I would.

## The Horsemen Sequences

33 horsemen are riding in the same direction along a circular road. Their speeds are constant and pairwise distinct. There is a single point on the road where the horsemen can pass one another. Can they ride in this fashion for an arbitrarily long time?

The puzzle appeared at the International Tournament of the Towns and at the Moscow Olympiad. Both competitions were held on the same day, which incidentally fell on Pi Day 2010. Just saying: at the Tournament the puzzle was for senior level competitors; at the Moscow Olympiad it was for 8th graders.

Warning: If you want to solve it yourself first, pause now, because here is the solution I propose.

First, consider two horsemen who meet at that single point. The faster horseman passes the slower one and gallops ahead and the slower one canters along. The next meeting point should be at the same place in the circle. Suppose the slower horseman rides n full circles before the next meeting, then the second horseman could not have passed the first in between, so he has to ride n+1 full circles. That means their speeds should have a ratio of (n+1)/n for an integer n. And vice versa, if their speeds have such a ratio, they will meet at the same location on the circle each time. That means that to solve the problem, we need to find 33 different speeds with such ratios.

As all speed ratios are rational numbers, we can scale speeds so that they are relatively prime integers. The condition that two integers have a ratio (n+1)/n is equivalent to the statement that two integers are divisible by their difference. So the equivalent request to the problem is to find a set of 33 positive integers (or prove non-existence), such that every two integers in the set are divisible by their difference.

Let’s look at examples with a small number of horsemen. For two riders we can use speeds 1 and 2. For three riders, speeds 2, 3 and 4.

Now the induction step. Suppose that we found positive integer speeds for k horsemen. We can add one more horseman with zero speed who quietly stays at the special point and everyone else passes him. The difference condition is satisfied. We just need to tweak the set of speeds so that the lazy horseman starts moving.

We can see that if we add the least common multiple to every integer in a set of integers such that every two numbers in a pair are divisible by their difference, then the condition stays satisfied. So by induction we can find 33 horsemen. Thus, the answer to the problem is: Yes they can.

Now I would like to apply that procedure from the solution to calculate what kind of speeds we get. If we start with one rider with the speed of 1, we add the second rider with speed 0, then we add 1 to both speeds, getting the solution for two riders: 1 and 2. Now that we have a solution for two riders, we add a third rider with speed 0 then add 2 to every speed, getting the solution for three horsemen: 2, 3 and 4. So the procedure gave us the solutions we already knew for two and three horsemen.

If we continue this, we’ll get speeds 12, 14, 15 and 16 for four riders. Similarly, 1680, 1692, 1694, 1695, and 1696 for five riders.

We get two interesting new sequences out of this. The sequence of the fastest rider’s speed for n horsemen is: 1, 2, 4, 16, 1696. And the sequence of the least common multiples for n−1 riders — which is the same as the lowest speed among n riders — is: 1, 1, 2, 12, 1680, 343319185440.

The solution above provides very large numbers. It is possible to find much smaller solutions. For example for four riders the speeds 6, 8, 9 and 12 will do. For five riders: 40, 45, 48, 50 and 60.

I wonder if my readers can help me calculate the minimal sequences of the fastest and slowest speeds. That is, to find examples where the integer speed for the fastest (slowest) horseman is the smallest possible.