A cute problem that illustrates the power of integers

The following problem was introduced to me as a ‘homework problem’ for the child of a certain genius-level mathematician, which is likely apocryphal. Nevertheless, the problem itself is interesting.

Problem: Three farmers brought 10, 16, and 26 chickens to the market to sell. To avoid a price war, they agreed to sell each chicken for the same price. By midday, none of them had sold all of their chickens. They then agreed to lower their prices by the same amount in order to unload all of their chickens. By the end of the day, each farmer sold all of the chickens they brought to the market and each made 35 dollars. What is the difference of the morning price and the afternoon price?

This question seems like it does not provide enough information. Indeed it does not, if one fails to consider that certain quantities (namely the amount of chickens) are integers. To wit, let us establish the solution as follows.

Let x,y,z respectively denote the number of chickens sold by farmer 1, 2, and 3 in the morning. Note that x,y,z are necessarily integers. Let C denote the price of a chicken in the morning, and C' denote the price of a chicken in the afternoon. Let D = C'/(C - C'). We then obtain the following equations:

Cx + (10 - x)C' = 35,

Cy + (16 - y)C' = 35, and

Cz + (26-z)C' = 35.

Subtracting the third equation from the first and second and re-arranging, we obtain

x - z = 16D, y - z = 10D.

Now the fact that x,y,z are positive integers really come in handy. In particular, we must have 16D, 10D are both integers. The first condition implies that the denominator of D must be a power of 2, and the second implies that it must in fact be exactly 2. Now we write D = G/2, where G is a positive odd integer. Now we examine the equation

x = 8G + z.

Note that since Farmer 1 did not sell all of his chickens in the morning, we must have

1 \leq x \leq 9.

However, G \geq 1 and z \geq 1, whence 8G + z \geq 9, and so x = 9 is the only possibility. Thus, z = 1 and G = 1. This shows that

y = 5G + 1 = 6.

With this information in hand, we go back to examine the equation

9C + C' = 35, 6C + 10C' = 35.

Substituting, we see that C = 15/4, C' = 5/4. So it would appear that C - C' = 15/4 - 5/4 = 5/2.

But wait! We had only shown that the values of C, C' above satisfy two of the three required equations, so for due diligence we must examine the final equation

C + 25C' = 35.

But

15/4 + 25(5/4) = 140/4 = 35,

so indeed C = 15/4, C' = 5/4 is an acceptable solution.

Note that the solution really required the fact that x,y,z were positive integers and constrained in a specific way. Without these (seemingly unimportant) tidbits of information, the problem would be intractable.

An innocent linear algebra problem and an application of the probabilistic method

The following question was posed to me by a friend:

Suppose that A \subset M_{n \times n}(\mathbb{R}) is a symmetric matrix with non-negative trace, and B \subset M_{n \times n}(\mathbb{R}) is a symmetric matrix with negative trace. Prove that there exists a vector \textbf{w} \in \mathbb{R}^n such that \textbf{w}^T A \textbf{w} \geq 0 and \textbf{w}^T B \textbf{w} < 0.

After fruitlessly trying to give an explicit construction and trying to work out an inductive argument, the hint provided by my friend proved to be ingenious: one should consider a probabilistic argument.

In the end, one can argue that the probabilistic method is not really needed as the argument used below is equivalent to a counting argument. Nevertheless, we give the following proof.

First, we may suppose that A is diagonalized, as the matrix P used to diagonalize A when applied to B gives PBP^{-1}, which remains a symmetric matrix with negative trace as trace is preserved under similarity. Now consider the random vector \textbf{x} = (x_1, \cdots, x_n) where the x_i are independent Bernoulli random variables with mean zero and variance 1. It is immediate that for any such vector \textbf{x}, we have

\textbf{x} A \textbf{x}^T \geq 0.

Now, we compute the expectation of \textbf{x} B \textbf{x}^T. By the linearity of expectation and the fact that the x_i‘s are independent, we have

\displaystyle E(\textbf{x} B \textbf{x}^T) = \sum_{j=1}^n b_{jj} \text{Var}(x_j) = \text{Tr}(B) < 0.

Hence there exists one particular vector \textbf{x}' for which $\textbf{x}’ B (\textbf{x}’)^T < 0$, and we are done.

As remarked earlier, this argument is equivalent to considering the set of vectors \textbf{x} = (\pm 1, \cdots, \pm1) and adding all of them and concluding that at least one of them must give the desired result.

An interesting problem on a function in two variables

One of the starkest differences between dealing with differentiation of a multi-variable function and a single variable function is that there are now an infinite number of ways to take a limit, and it becomes much more difficult to show that the derivative exists at a point by checking that derivatives exist along all possible paths. With functions in two variables, for example, one can usually play around with x and y separately to try to get different values at a limit point. Recently I ran across a problem that I found striking.

Let a,b,c,d be positive real numbers and let

\displaystyle f(x,y) = \frac{|x|^a |y|^b}{|x|^c + |y|^d}.

Prove that \lim_{(x,y) \rightarrow (0,0)} f(x,y) = 0 if \displaystyle \frac{a}{c} + \frac{b}{d} > 1 and that the limit does not exist if \frac{a}{c} + \frac{b}{d} \leq 1.

I found this particularly interesting because it is not at all clear why the quantity \displaystyle \frac{a}{c} + \frac{b}{d} should control the existence of the limit at (0,0). The proof, I thought, was quite clever.

In retrospect the case a/c + b/d \leq 1 is easier, as we just have to exhibit a path for which the limit as (x,y) approaches (0,0) along the path is non-zero. Indeed, trivially we have \lim_{(x,0) \rightarrow (0,0)} f(x,0) = 0 for any positive values of a,b,c,d, and so this suffices. Now we choose the path where x,y > 0, y = x^{c/d}. Then we have

\displaystyle f(x,y) = \frac{x^a x^{bc/d}}{x^c + x^c} = \frac{1}{2}x^{c\left(\frac{a}{c} + \frac{b}{d} - 1\right)}

and this limit is plainly 1/2 if a/c + b/d = 1 and + \infty if a/c + b/d < 1.

The other situation is much trickier. We will require two ad-hoc inequalities.

\displaystyle |x| = (|x|^c|)^{1/c} \leq (|x|^c + |y|^d)^{1/c},

\displaystyle |y| = (|y|^d)^{1/d} \leq (|x|^c + |y|^d)^{1/d}.

Now we have

\displaystyle |x|^a |y|^b \leq (|x|^c + |y|^d)^{a/c} (|x|^c + |y|^d)^{b/d},

whence

0 \leq f(x,y) \leq (|x|^c + |y|^d)^{a/c + b/d - 1},

and if a/c + b/d - 1 > 0 then the right hand side tends to 0 as (x,y) \rightarrow (0,0), thus establishing our proposition.

along this path.

Upcoming TV series about Emperor Wu to be the most expensive TV series made in Chinese history

An upcoming series chronicling the life of China’s only female emperor, Emperor Wu Zetian of the Zhou Dynasty (she was the only emperor of that dynasty, the emperor to come before and after her were all emperors of the more famous Tang Dynasty), is set to become the most expensive TV series ever made in China (http://en.wikipedia.org/wiki/The_Empress_of_China). The TV series will star Chinese megastar Fan Bingbing, and is also produced by her company.

The story of Emperor Wu is one of the most famous in the history of China. She seemed to have done the impossible: she assailed the entrenched sexism and misogyny embedded in feudal China and ascended to the title of Emperor, making her both the nominal and actual leader of China. It is noted that only three women in Chinese history has wielded as much power, Wu Zetian being the second. The other two were Empress Lü Zhi of the Han Dynasty, wife of Emperor Gaozu, the founder of the Han Dynasty and Empress Dowager Cixi, the wife of Emperor Xianfeng and mother of Emperor Tongzhi of the Qing Dynasty. However, the other two never managed to claim the title of Emperor for themselves, instead having to rule from ‘behind the curtain’. 

Much of China’s history, understandably, is written by men and for men. It was noted earlier that in fact Chinese historians have a habit of writing towards a very specific audience: future rulers. Thus Chinese history is written as a warning to future emperors of the challenges they must conquer in order to hold onto power. The most deleterious of these challenges is undoubtedly guarding against the women you trust most. It is no surprise then that all of the above strong women who managed to climb to the peak of power were later demonized in the annals of Chinese history. Both Lü Zhi and Wu Zetian were ‘renowned’ for their immense cruelty. For instance, it was said that Lü Zhi turned Gaozu’s favored concubine, Mistress Zhao, into a human ‘stump’ by cutting off her limbs and mutilating her face and then blinding her, but kept her alive. Wu Zetian was said to employ ‘cruel ministers’ to administer extraordinary acts of cruelty and torture against political opponents and ruled by a campaign of terror. Cixi is widely regarded by modern Chinese history as the principal architect of the Qing Empire’s downfall, and the subsequent humiliation that the Chinese civilization suffered in the 20th century.

However, in more recent times, some familiar narratives of history have been challenged and re-imagined. One such case is that of the Qin Dynasty. Historically noted for their immense cruelty and extreme legal system and anti-Confucianism, the recent work 大秦帝国 has sought to re-tell the story of the rise of the Qin Empire, previously the Qin Kingdom in the Warring States Period, in a positive light. It sought boldly to re-imagine the Chinese civilization as having been born from a warrior nation (Qin), as opposed to a relatively meek and passive nation (context: after uniting China and establishing the Han Dynasty, Emperor Gaozu and his successors Wendi and Jingdi sought a policy of appeasement and compromise against the barbarians to the north, which was finally reversed by Emperor Wudi, who ordered several major military campaigns against China’s northern neighbors). The same has happened for the story of Wu Zetian, where more recent TV series have depicted her in a much more positive light, as a strong and wise leader far outweighing the weak Tang Emperors she replaced.

Underlying reasons for the unrest in Hong Kong

As some of you know, since earlier this year, there is civil unrest in Hong Kong centered around the so-called “Occupy Central” (referring to the Central Business district or 中环 in Chinese, not the Central Government of China, as several people I discussed this with mistakenly assumed) movement. The movement’s aims are to fight for true universal suffrage in 2017. While the current proposal drafted and now approved by the National People’s Congress offers universal suffrage to select the city’s leader, the Chief Executive, it also stipulates that all candidates must be approved by a majority the 1200 member Election Committee which contains many Beijing supporters, effectively ensuring that only those loyal to Beijing will be allowed to run for the top office. This is deemed unacceptable by the so-called pan-democratic persons in Hong Kong. The main goal of Occupy Central is to remove this stipulation in the 2017 election and allow anyone who chooses to run to be deemed a candidate.

On the surface, this seems like the same story that has happened again and again throughout history. Even the organizers behind Occupy Central have compared their proposed campaign of civil disobedience to the likes of Martin Luther King and Nelson Mandela, with the goal of opposing a tyrannical and oppressive regime and unfair treatment of people. This may very well be true, but there are other factors that run deep beneath the surface.

One has to understand that Hong Kong, aside from being a British colony for a hundred years and a place where the residents are used to a British style of government and way of life, it is also a prime destination for mainland refugees fleeing from various situations in China after the establishment of Communist China in 1949. Many of the refugees were members of the bourgeois or land owner classes, which were mercilessly persecuted by Communist China. Others escaped the famine caused by the Great Leap Forward and the fearful period of the Cultural Revolution. The point is, many of the people in Hong Kong have a deep grudge against the Communist Party of China, as their own families have suffered greatly at the hands of China’s current rulers. They may not necessarily be pro-democracy, but they are definitely anti-Communist.

This is combined with a more delicate social history. Many of the people who fled to Hong Kong have found their way to a better way of life and prosperity after leaving their homes. There is a feeling of vindication, and definitely superiority, towards China. While the Mainland languished in the Cultural Revolution, Hong Kong boomed as a financial and economic hub. By the time China opened up its borders in 1978 under Deng Xiaoping’s economic reforms, Hong Kong was already a modern and cosmopolitan city. It is not even a secret that Hong Kongers widely feel they are superior to mainlanders, deeming mainlanders uncouth and uncivilized. For a long time, economic reality reflected much the same. This changed, however, in the past decade, when China’s unprecedented economic rise has placed it higher on the economic spectrum than Hong Kong. While Hong Kong enjoyed consistent economic growth since rejoining China in 1997, the growth rate is much slower than in the mainland. While in the late 90′s and 2000′s China’s economy boomed at double digit growth rates, Hong Kong’s economy grew at a relatively modest 4-5% range. This gap in growth rate has shifted economic realities. Now many mainlanders north of the border enjoy much more wealth and a higher standard of living than many middle class members of Hong Kong. However, the attitude of superiority of Hong Kongers towards mainlanders has not changed; and this has caused much resentment.

Further, the policy differences between Hong Kong and the mainland have exerted a lot of pressure on Hong Kong’s social fabric. Since Hong Kong’s laws are different than in the mainland, and usually much more transparent with a more or less independent judiciary, it is considered essentially a ‘foreign’ land in terms of investments. Thus many wealthy mainlanders see fit to invest in Hong Kong real estate, just as they would buy real estate in hot foreign markets like Vancouver or Australia, as a secure way to park their money. This has driven up prices in the most densely populated place in the world, dashing the dreams of home ownership for many middle class Hong Kongers. Undoubtedly this reality has caused significant resentment among Hong Kong’s populace. Secondly, because Hong Kong citizens enjoy a special status in the context of the People’s Republic of China, Hong Kong citizenship is deemed highly desirable. Many mainland pregnant women have essentially snuck past the border to give birth in Hong Kong, making their offspring Hong Kong citizens. This has caused undue stress on Hong Kong’s hospitals to handle women going through labour, and have created resentment as well. Further, Hong Kong is a place where foreign products are widely available; and things like baby formula are highly desirable for mainland Chinese (context: about 6 years ago there was a so-called ‘tainted milk’ scandal in China where bad baby formula caused death and serious injury or mental impairment for over 40,000 babies, thus scaring people off domestic brands). This has created shortage in Hong Kong.

My point is, the current turmoil is not as simple as a bunch of freedom-minded people fighting for rights and freedoms. It is a continuation of a long history of mistrust and hatred towards China’s ruling party, and continued economic tensions between the mainland and Hong Kong.

My thoughts on what makes a good thesis problem

The single most important decision of a PHD student in (pure) mathematics is undoubtedly the choice of research in their thesis work. Usually to get a PHD, one must prove at least one new result. We will refer to the achievement of this situation as ‘solving a problem’. Thus, we may adapt the ‘problem solver’ (see here) view that a PHD is centered around solving a thesis problem.

I have made the following comments in person to many people, but I thought I would record them here as well.

When selecting a thesis problem, there are many factors to be considered, some of them quite deleterious. Firstly, mathematics is, contrary to popular belief, a social endeavor. Mathematicians do not work in isolation. As the recent controversy involving Shinichi Mochizuki and his purported proof of the abc-conjecture has shown, a problem is not solved and a result not proven until there is consensus among the mathematical community that it is. Therefore, progress or results that are not engaged with the mathematical community basically do not exist; just like the old paradigm involving trees falling in the woods. Thus one must ensure that their work is in sync with the current mathematical culture. One should therefore not choose a problem that is so far off in the fringes that few, if anybody, is aware of its existence and fewer still have any vested interest in whether it is resolved or not.

However, one should not pick something that is too hot or attractive, relative to its difficulty. Perhaps the best example of this would be the bounded gaps between primes problem. Prior to May 2013, the problem was considered intractable, and few people dedicated any amount of time to solving it. However when Yitang Zhang announced that he had proved that there exist infinitely many pairs of consecutive primes that differ by no more than 70 million, he sent shock waves around the mathematical world. Soon there was a flurry of results improving upon Zhang’s work in various ways. It would have been an extraordinarily bad idea to choose any results directly related to Zhang’s work as a thesis problem. There were literally dozens of top level experts around the world working on this topic, and the probability that your result will be scooped is very high. Thus, one must pick a problem that is either not a very obvious one to ask but is nonetheless interesting, or one that is interesting but not so interesting that it will attract the attention of many experts.

The final, and perhaps most subtle point, is that one should not pick a problem that is conducive to an ad-hoc solution that does not generalize. The best example of this is perhaps the so-called ‘elementary’ proof of the prime number theorem. In this case, while it was extraordinary that the prime number theorem, originally proved using arguments from complex analysis, could be proved in an elementary way, the proof fell drastically short of expectations. In particular, it was widely expected that an elementary proof of the prime number theorem would shed light on the distribution of primes and perhaps even pave the way to proving the Riemann hypothesis. The elementary proof of the prime number theorem did no such thing and to this day the technique remains restricted to only being able to prove the prime number theorem. One does not want a thesis problem like this. Instead, ideally during the course of solving one’s thesis problem, one discovers that the same techniques and machinery can be applied to a plethora of other problems and thus pump out a consistent stream of papers after and establish a solid research program. Whether or not this would be the case is extremely difficulty to predict before one actually attempts to solve the problem seriously.

Usually as a new PHD student who has limited understanding of your subject area and have limited perspective on the landscape of your research domain, it is extremely important to find an advisor who does have the right expertise and perspective. Even then it is a very delicate process to select a thesis problem which you would be expected to work on for several years.

Some statistics for hearthstone

This took a bit longer than I would care to admit, but I have finally computed the expected gain of stars per game. The answer depends a little bit on information available and interpretation.

Let p denote the probability of you winning a game, which is considered to be constant. If you are on a win streak, meaning you’ve won the previous two games, then the expected winning of your next game is 2p - 1(1-p) = 3p-1. The probability that you’ve won your previous two games is p^2, so this case contributes p^2(3p-1) to the total expected value. Otherwise, the expected winning is p - (1-p) = 2p-1. The probability of this is 1 - p^2, so the contribution for this case is (1-p^2)(2p-1). Summing, we obtain that the total expected value of the gain of stars is

3p^3 - p^2 + 2p - 1 - 2p^3 + p^2 = p^3 + 2p - 1.

Thus, if you win half the time (so that p = 1/2), you should expect to gain roughly one star every 8 games or so.

Another Hearthstone related problem, which I worked out with my officemate, is to ask what is the probability of you getting the card you need on turn 1 assuming you are going first and that you are willing to discard all other cards in your initial draw in order to get the card that you want. First, the probability that the card you need will appear in the initial draw of three cards is

\displaystyle \frac{\binom{2}{1} \binom{28}{2} + \binom{2}{2} \binom{28}{1}}{\binom{30}{3}}.

If you did not get either copy of the card that you need, then you may discard all three cards and try again, knowing that the three cards you tossed cannot come back. In this case, the probability of you getting the card you need is the product of the probability of you not getting the card you want in the initial draw and the probability of getting at least one copy of the card that you need in the second draw.

\displaystyle \frac{\binom{28}{3}}{\binom{30}{3}} \cdot \frac{\binom{2}{1} \binom{25}{2} + \binom{2}{2} \binom{25}{1}}{\binom{27}{3}} .

Adding these, we get some pretty neat cancelations and end up with the simple expression of p = 1/5.

However, we have not yet accounted for the random card that you top deck after your initial draw on turn 1. The only remaining case that needs to be considered is when you failed to get the card you need after tossing all of your cards on the initial draw. In this case, the probability of getting the card you need is

\displaystyle \frac{\binom{27}{3}}{\binom{30}{3}} \cdot \frac{\binom{25}{3}}{\binom{27}{3}} \cdot \frac{2}{27}

which is about 0.041963. Adding, the total probability is about 0.241963, or slightly less than one in four.