## 欺诈猜数游戏（下）

5 (this post is made with love)

## Crazy Telescoping

In mathematics, a telescoping series is a series whose partial sums eventually only have a fixed number of terms after cancellation. I learnt this technique when I was doing maths olympiad. However until last year I learnt this buzz word ‘telescoping’ since I received my education in China and we call it ‘the method of differences’.

Anyway, yesterday, I was helping Po-Shen Loh to proctor this Annual Virginia Regional Mathematics Contest at CMU. Unfortunately, I did not take my breakfast. All I could digest are the seven problems. And even worse, I got stuck by the last problem which is the following.

Find $$\sum_{n=1}^\infty\frac{n}{(2^n+2^{-n})^2}+\frac{(-1)^nn}{(2^n-2^{-n})^2}.$$

It turns out that the punch line is, as you might have expected, telescoping. But it is just a bit crazy.

There is Pleasure sure, In being Mad, which none but Madmen know!

John Dryden’s “The Spanish Friar”

First consider the first term, $$\frac{1}{(2^1+2^{-1})^2}+\frac{-1}{(2^1-2^{-1})^2}=\frac{-2\times 2}{(2^2-2^{-2})^2}.$$ Then take look at the second term, $$\frac{2}{(2^2+2^{-2})^2}+\frac{2}{(2^2-2^{-2})^2}.$$ Aha, the sum of the first two terms becomes $$\frac{2}{(2^2+2^{-2})^2}+\frac{-2}{(2^2-2^{-2})^2}=\frac{-4\times 2}{(2^4-2^{-4})^2}$$ which again will interact nicely with the 4th term (not the 3rd term). After all, the sum of the 1st, 2nd, 4th, 8th, …, $$n=(2^m)$$th  terms is $$\frac{-4n}{(2^{2n}-2^{-2n})^2}$$. Note that this goes to zero.

But this only handles the terms indexed by 2’s power. Naturally, the next thing to look at is the sum of the 3rd, 6th, 12th, 24th, …, $$n=(3\times 2^m)$$th terms, which amazingly turns out have the telescoping phenomena again and is equal to $$\frac{-4n}{(2^{2n}-2^{-2n})^2}.$$ Again, the this goes to zero.

We claim that starting with an odd index, say $$(2l+1)$$, the partial sum of the $$(2l+1), 2(2l+1), \ldots, 2^m(2l+1), \ldots$$‘th terms goes to zero.

For people who is willing to suffer a bit more for rigorousness, the argument for the previous claim can be easily formalized by the method of differences. The key fact we have been exploiting above is the following identity.

$$\frac{2n}{(2^{2n}+2^{-2n})^2}+\frac{2n}{(2^{2n}-2^{-2n})^2} = \frac{4n}{(2^{2n}-2^{-2n})^2}-\frac{8n}{(2^{4n}-2^{-4n})^2}$$

The last bit of the ingredient is the absolute summability of the original sequence which implies that changing the order of summation does not affect the result. Hence the sum in total is $$0$$.

5 (this post is made with love)

## The Ultimate Prisoner Puzzle

People like prisoner puzzles. Here is the hardest one I have ever seen. I heard it from Prof. Boris Bukh on the social hour of Maths Department couple of weeks ago, whom heard it on a maths conference. Since recently I am quite into Cryptography, especially setting up communication protocols, I would like to log the puzzle in my blog.

The storyline is like The Shawshank Redemption. You are locked into one of the cells in the jail. Unfortunately, you do not know how many prisoners there are in the jail. You do not even know whether you are the only one! The evil-hearted yet mathematically inclined warden wants to play a game with you. The rules are as follows.

1. On the first day, you can write up a communication protocol. The warden will make identical photocopies of your protocol and distribute them among other prisoners.
2. During the following days, everyday, each prisoner will be given one black card and one white card, and they should turn in one of them to the warden according to your protocol. The rest of the cards will be discarded. The warden would line up all prisoners in a circle in his mind and imagine each of them passes his or her chosen card to the next person clockwise. After going through all this in his mind, he will redistribute the cards to the prisoners accordingly. Notice, the warden could line up the people by any order he likes. Moreover, the orders could probably differ from day to day.
3. One day, you should call for a stop and immediately tell the number of prisoners in this jail. All prisoners including yourself will be released if you got the number correct.

Remember, the evil-hearted warden knows every detail of your protocol. So all odds are always against you.

The following is the solution I came up.

Denote the number of prisoners as $$p$$. First of all, we want to draft the protocol so that all prisoners know an upper bound of $$p$$, denoted as $$P$$. Before we say anything about the protocol, let us take a look at the significance of knowing such an upper bound.

If all prisoners know an upper bound $$P$$, then they can broadcast messages. To be precise, if one turns in a card of some color he chooses, say $$c$$. Everyone else should keep turning in white cards until he receives a black card, and then keep turning in black cards regardless of what cards are received. Then after $$P$$ days, all prisoners will receive the the cards of color $$c$$. (Think about why this is true.) Now everyone knows the color $$c$$. Hence they succeeded in broadcasting a single bit. If the protocol says something about coding messages by colors, one can broadcast any message to others. Note that prisoners might not know who has sent the messages.

Though direct message is hard to realize in this situation, broadcasting would be good enough for us to figure out $$p$$.

Now, let us see how prisoners cooperatively figure out an upper bound $$P$$. We call it the first stage.

In the first stage, all prisoners will be labeled as either visible or hidden. At the beginning, only I am labeled as visible, all the rest are labeled as hidden. We break down the following days into several phases. At the beginning of the $$k$$th phase, all prisoners know the upper bound of the current visible prisoners $$P_k$$. For instance, $$P_1=1$$. Now, all hidden people broadcast the a single bit of message telling the others there are hidden people. The broadcasting is done similarly, i.e., whoever receives the black card once should keep sending black cards. The broadcasting can be done within $$P_k$$ days because there are at most these many visible prisoners.

There are two possible turnouts. If no visible prisoner receives this message, then all prisoners are visible, and immediately all prisoners know $$P=P_k$$. Otherwise, on the next day, all visible prisoners turn in black cards. Whoever receives a black card changes his label to visible if it was hidden. The number of prisoners who change their labels is at most $$P_k$$. Thus we can use $$P_{k+1}=2P_k$$ in the $$k+1$$th phase as now there are at most $$P_k+P_k$$ visible prisoners. Since at least one prisoner changes his label in each phase, eventually, all prisoners will become visible. Hence this process will terminate at a certain phase and provides us an upper bound $$P$$.

After the first stage, comes the second stage.

In the second stage, we will partition prisoners by clans and try refining the clans as much as possible. During the second stage, each prisoner knows the total number of clans, the names of each clan and which clan he belongs to. At the beginning, I myself alone consists the first clan and the rest of prisoners consist the second clan. This initial set up is written into the protocol, so everyone knows it.

The following is how I refine the clans. I can broadcast a message that asks the members in a certain clans if any one has turned in a black card on a given day. Prisoners in this certain clan will broadcast a message of a single bit to indicate their answer. And then I broadcast a message that asks if any one in this clan has turned in a white card on that day. If both answers are ‘yes’, this means there are two people in this clan turned in different card on that given day. Then I will demand this clan to divide into two smaller clans according to the color of their cards turned in on that given day. I can also do the same thing to the cards they received on that given day as well.

So in the second phase, I can constantly refine the clans by asking questions clan by clan and day by day. Since the number of clans can not exceed $$P$$, this refining process will stop and the number of clans will stabilize. Moreover, once it stabilizes, prisoners in each clan will turn in the same cards and receive the same cards as well. Otherwise, some day I will interrogate the members in this clan and separate them into smaller clans.

Now we can assume the prisoners in each clans always turn in the same cards and receive the same cards. This is amazing!

Suppose $$c_i$$ is the number of prisoners in the $$i$$th clan $$C_i$$ for $$i=1,\ldots, n$$. Assume I am in $$C_1$$. Then $$c_1=1$$. Initially the values of all other $$c_i$$s are unknown. Our goal is to find out each $$c_i$$, though it is enough to find $$\sum_{i=1}^nc_i$$.

Notation: $$[n]$$ is the set of all naturals from $$1$$ to $$n$$. If $$I\subset [n]$$, $$c_I := \{c_i: i\in I\}$$ and $$span(c_I)$$ be the set of all linear combination of $$\{c_i: i\in I\}$$.

For $$r = 1,\ldots, n-1$$, we claim that for all $$r$$-element subset $$I\subset [n]$$ and $$i\in I$$, $$c_i$$ can be written as a linear combination of $$\{c_j: j\in[n]-I\}$$. In abbreviation we shall write $$c_i\in span(c_{[n]-I})$$. Note when we say ‘some variable can be written as a linear combination of other variables’, we mean all prisoners know this information. In other words, all prisoners keep track of these linear dependencies along the way. We will omit the details of how prisoners would share this information in the following proof and leave them to the readers.

Before we prove the claim, let us take a look at the consequence if what we claimed is true. When $$r=n-1$$, it means $$c_2, \ldots, c_n$$ can be written as a linear combination of $$c_1=1$$. Thus we know $$c_i$$ for all $$i\in[n]$$. Hence we know the total number of prisoners.

Now we prove the claim by induction on $$r$$. If $$r=1$$, we shall prove $$c_i\in span(c_{[n]-\{i\}})$$ for all $$i\in[n]$$. This is relatively easy. Let the prisoners in the clan $$C_i$$ send out black cards. Some of the other clans will receive those black cards. Thus $$c_i$$ is the sum of the size of those clans which receive the black cards.

Suppose the claim is true for some $$r$$. Now we shall prove for every $$r+1$$-element subset $$I\subset [n]$$ and $$i\in I$$, $$c_i\in span(c_J)$$, where $$J=[n]-I$$.

Fix some $$i_0\in I$$. By the induction hypothesis, we know for all $$i\in I$$ with $$i\neq i_0$$, we have

$$c_i = \alpha_ic_{i_0}+\beta_i(c_J),$$

where $$\beta_i(c_J)\in span(c_J)$$.

This is also true for $$i=i_0$$. Because we may set $$\alpha_{i_0}=1$$ and $$\beta_{i_0}=0$$.

Let the index set $$I_+$$ be the set $$\{i\in I: \alpha_i > 0\}$$ and $$I_-=I-I^+$$. As $$i_0\in I_+$$, $$I_+$$ is non-empty.

Now we demand all clans indexed by $$I^+$$ send out black cards. Suppose the clans indexed by $$I_+’\subset I_+$$ who send out black cards receive white cards and the clans indexed by $$I_-‘\subset I_-$$ and $$J’\subset J$$ who send out white cards receive black cards. Hence we have the following equation.

$$\sum_{i\in I’_+}c_i = \sum_{i\in I’_-}c_i+\sum_{j\in J’}c_j$$

Hence

$$\sum_{i\in I’_+}\left(\alpha_ic_{i_0}+\beta_i(c_J)\right)=\sum_{i\in I’_-}\left(\alpha_ic_{i_0}+\beta_i(c_J)\right)+\sum_{j\in J’}c_j$$

The $$\alpha$$-coefficient on the left hand side is positive. Meanwhile it is nonpositive on the right hand side. Thus by the equation above we can solve for $$c_{i_0}$$ in terms of a linear combination of $$c_J$$. Hence we can write $$c_i$$ in terms of a linear combination of $$c_J$$ for all $$i\in I$$.

This finishes the proof.

2 (this post is made with love)

## How to say maths terms in English?

On Maths Presentation Workshop at Carnegie Mellon University, Professor Brandon was trying to to help us understand the undergrad in United States and improve our teaching skills. This was my first time knowing how to say maths terms in English. And I want to share with you some of the tips. Before I start, I would like to abbreviate some of the points that Prof. Brandon mentioned concerning teaching.

• Lousy background – American students have a lousy background in mathematics, but it doesn’t mean they are not smart. You will see students writing $$\frac{1}{a}+\frac{1}{b}+\frac{1}{a+b}$$ or $$\sqrt{a}+\sqrt{b}=\sqrt{a+b}$$, but it’s not their fault. Even their high school teachers would say ‘Well, it’s just a different way to do those calculations.’
• Cheat on homework – Student who is copied by others is considered cheating as the student who copied him or her.
• Handholding – Many US students do not know how to learn things. They need someone to guide them, for instance, how to use textbooks, how to prepare exams, etc.
• 2 tips on teaching skills – Keep eye contacting. Reword things and write it down.

Finally, here is the list that gives you some examples of spoken Maths.

Maths Terms How to say it?
$$\frac{1}{x^n}$$ 1 over x to the power of n
$$\sqrt{x}, \sqrt{x}$$ cube root of x, fourth root of x
$$\sin^{n}x$$ sine to the power of n of x
$$f\circ g$$ f composed with g
$$\lim_{x\rightarrow a}f(g(x))$$ limit as x approaches a of f of g of x
$$x\rightarrow \pi^{-}$$ x approaches pi from the left
$$\frac{d}{dx}f(x)$$ the derivative of f of x (with respect to x) or d over dx of f of x
$$\frac{\partial x}{\partial y}$$ del y over del x
$$\nabla, \Delta$$ gradient, Laplacian
$$\log_a(xy)$$ log (with respect to) base a of x times y
$$\ln x$$ natural log of x or ln of x
$$f(x)g(x)]_a^b$$ f of x times g of x evaluated from a to b
$$f(x,y), (a,b)$$ f of x comma y, a comma b
$$f'(x), f^{\prime\prime}(x), f^{\prime\prime\prime}(x)$$ f prime of x, f double prime of x, f triple prime of x
$$S_n, \cdots, f_x$$ s sub n, dot dot dot or etc, f sub x
99 (this post is made with love)

## 井田问题

Matrix67致敬，我也来写点科普文章。 三分田地 井田问题 辅助图

$latex S_{GKE} = \frac{2}{3}S_{GDE}+\frac{1}{3}S_{GCE}=2(\frac{2}{3}S_{GAE}+\frac{1}{3}S_{GBE})=2S_{GIE}$.

0 (be the first to like this)