欺诈猜数游戏(下)

上次的日志,先重复一下谜题:

欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 \(k\) 和 \(n\)。游戏开始时,甲先选定两个整数 \(x\) 和 \(N\),其中 \(1\leq x\leq N\)。甲告诉乙 \(N\) 的值,但对 \(x\) 守口如瓶。乙试图通过提问来获得与 \(x\) 相关的信息:每次提问,乙任选一个由若干正整数组成的集合\(S\)(可以重复使用之前提问中使用过的集合),问甲“\(x\)是否属于\(S\)?”。乙可以提任意数量的问题。每次提问之后,甲立刻回答是或否,甲可以说谎话,但在任意连续 \(k+1\) 次回答中至少有一次回答是真话。

在乙问完所有想问的问题之后,乙必须指出一个至多包含n个正整数的集合\(X\),若\(x\)属于\(X\),则乙获胜;否则甲获胜。证明:对所有充分大的整数\(k\),存在整数\(n\geq 1.99^k\),使得乙无法保证获胜。

为了解决第二个问题,需要从甲的角度考虑问题,每一次回答问题后,使得乙无法缩小 \(x\) 范围。

为此我们考虑贪心策略:甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点:如果乙每次提问都问“\(x\) 是不是 \(1\) 呢?”那甲如果每次只顾眼前利益,应当回答“不是。”但经过 \(k+1\) 轮之后,甲就能轻松排除 \(1\),从而缩小 \(x\) 的范围。

于是甲的策略必须是一种折中的策略,既要顾及眼前的利益,又不能放弃长期的利益。我们设定 \(N=n+1\)。

于是甲在觉得到底要选择乙提出的集合或是其补集前,对 \(1\) 到 \(n+1\) 中每个数都进行打分。甲对 \(i\) 的打分是 \(a^{m_i}\),其中\(a = 1.999\) 而 \(m_i\) 满足 \(i\) 在最近连续 \(m_i\) 次选择的集合中都不出现。根据每个元素的打分,甲在 \(S\) 和 \(S^c\) 中选择会使得之后整个集合总分较低的那个集合。

为了让证明成立,设定 \(n = (2-a)a^{k+1} – 1\)。下面,我们通过归纳法证明每一次所有元素的总分不超过 \(a^{k+1}\)。根据打分规则,最开始总分是 \(n = (2-a)a^{k+1}-1 < a^{k+1}\),命题显然那成立。假设目前的总分是 \(y = \sum_{i=1}^{n+1} a^{m_i}\),乙给出集合 \(S\),如果甲选 \(S\),则总和变为 \(y_1 = \sum_{i\in S}1 + \sum_{i\notin S}a^{m_i+1}\),如果甲选 \(S^c\),则总和变为 \(y_2 = \sum_{i\notin S}1 + \sum_{i\in S}a^{m_i+1}\)。由于甲会选择使得总和变得更小的那个策略,于是他回答后总和至多为 \(\frac{1}{2}(y_1 + y_2) = \frac{1}{2}(ay+n+1)\)。由于 \(y < a^{k+1}\),总和小于 \(\frac{1}{2}(a\cdot a^{k+1}+(2-a)a^{k+1}) = a^{k+1}\)。命题成立!

如果 \(i\) 连续 \(k+1\) 次没有被甲选中,则其得分已经为 \(a^{k+1}\)。这不可能,因为总分总是小于 \(a^{k+1}\)。也就是说在这样的策略下乙无法缩小 \(x\) 的可能范围。证毕!

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[3]{x}, \sqrt[4]{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 ABCD$中,$latex E,F$依次是边$latex BC$上的两个三等分点,$latex G,H$依次是边$latex AD$上两个三等分点,求证$latex S_{ABCD}=3S_{EFHG}$。

三分田地

这道题目立即让我联想起了张景中院士的一本科普书,上课的时候我记不得这本书的名字了,后来回去搜索了一下,叫《新概念几何》。我的爸妈一般不给我买书(可能是因为买过两套四大名著我都不看的关系吧),记忆中他们还给我买过的书只有《十万个为什么(小学版)》和《新概念几何》了。

在《新概念几何》中提到过一个问题,叫做井田问题:传说从前的农民要分地的话,没有很精准的丈量工具,也不懂几何或是微积分,所以都采取一些近似的方法。有一天,村里的九户人家发现了一块四边形的田地,他们打算平分这块田。于是他们通过脚步丈量四条边后,将四边都三等分后,如下图将田分为了九块。

井田问题

很明显,这块田地没有被九等分。但会不会像之前的“三分田地”问题一样,有类似的结论呢?很自然的一个猜测是最中间的土地面积是总面积的九分之一。其数学表述如下:

四边形$latex ABCD$中,$latex E,F$依次是边$latex BC$上的两个三等分点,$latex G,H$依次是边$latex AD$上两个三等分点,$latex I,J$依次是边$latex AB$上的两个三等分点,$latex K,L$依次是边$latex DC$上两个三等分点,求证$latex S_{ABCD}=9S_{MNOP}$。

由于整个问题犹如在一块田中写一个井字,井田问题由此得来。

记得当时上课的时候,由于是即兴想到这个问题,双核同时运转,只顾着把故事编得生动一些,没腾出脑子去想解答,所以留下这个问题让小朋友自己回家思考了……

实际上,建立在之前的三分田地的结论上,这个问题是很容易解决的:

由之前的结论,红色四边形$latex IJLK$的面积是整个面积的三分之一。假设我们能再证明$latex M,P$和$latex N,O$分别是$latex IK, JL$的三等分点,那再次利用三分田地的结论,我们就能证明红黑相交的部分$latex MPNO$的面积是红色四边形$latex IJLK$的三分之一,也就是原四边形的九分之一了。

最后我们证明$latex M,P$和$latex N,O$确实分别是$latex IK, JL$的三等分点,为此我们只证明$latex M$是$latex IK$的三等分点。

为了能看得更清楚,我们考虑与需要证明的结论有关的部分。

辅助图

由定比分点公式,我们有关于面积的等式:

$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}$.

于是$latex KM = 2IM$,就证明了需要的结论。

通过类似的论证,读者还能将井田问题中的三等分替换为五等分、七等分甚至任意$latex 2n+1$等分。进行类似的面积划分后,最中间那块的面积便是$latex (2n+1)^2$分之一了。

0 (be the first to like this)