Categories

## 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 $\mathrm{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 \mathrm{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 \mathrm{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 \mathrm{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 \mathrm{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$.

Categories

## 欺诈猜数游戏（上）

“欺诈猜数游戏”在两个玩家甲和乙之间进行， 游戏依赖于两个甲和乙都知道的正整数$k$$n$

1. $n\geq 2^k$，则乙可保证获胜；
2. 对所有充分大的整数$k$，存在整数$n\geq 1.99^k$，使得乙无法保证获胜。

Categories

## Excerpt from Kunen

People living in $M$ cannot construct a $G$ which is $P$-generic over $M$. They may believe on faith that there exists a being to whom their universe, $M$, is countable. Such a being will have a generic $G$ and an $f_G=\cup G$. The people in $M$ do not know what $G$ and $f_G$ are but they have names for them, $\Gamma$ and $\Phi$. They may also read the preceding few paragraphs and thus figure out certain properties of $G$ and $f_G$

I could only say that Paul Cohen’s idea on the Continuum Hypothesis is amazing. And I am quite curious about his religious belief.

Categories

This semester, I am assigned as a grader for 21-355 Principle of Mathematical Analysis I since I did really bad in the iTA test last year and ended up in the category 3 which doesn’t allow me to hold any recitation for undergraduate students. Anyway, I need to find some fun in the given situation. That’s my principle for life.

The textbook for the course is Rudin’s book, one of the most classic introductory books in analysis. As I need to grade several problems from the exercises part, I read through the first chapter and kept in mind what results students can use in their proofs. But quickly, I was stuck at the point where students started to use things like, if $a=b$, then $ac=bc$ or if $a=b$ then $a+c=b+c$.

Then I questioned myself, how can I use the axioms given in Rudin’s book to justify those arguments? I know I was being nerdy at that time, but it turned out that those field axioms tell us nothing about the interplay between the equality and the two operators, namely addition and multiplication. Moreover, in the proof for some basic properties of field Rudin took those arguments as granted.

One might say “It is obvious, isn’t it?”. But my response is “No.”. In first order logic with equality, those arguments actually used the axioms of equality.

To exaggerate a little bit, how does maths scare a lot of people? I can imagine a scenario that someone is looking up a solution using this kind of ‘tricks’ and get depressed since he didn’t think of such an apparent way of solving the problem.

But in fact, that’s not this guy’s fault, it’s the deficiency hidden in maths education. In my opinion, there are no magic in mathematics, but axioms and rules that people use them unconsciously. So maths educators, especially for those in a primary level, should pay more attention to these obvious issues. Sometimes, one really need to emphasis the trivial things at the beginning level.

Categories

## Mathematical Abbreviations

Here is a short list of mathematical abbreviations which troubled me the first time I graded students’ papers. You should be familiar with these words if you have used English as your first language in mathematics for years. But for students who has no experience of writing maths in English, this list might help.

Categories

## 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. A student who is copied by others is considered cheating as much as the student who copied him or her.
• Handholding. Some 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 contact. 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
Categories

Categories

## 井田问题

Matrix67 致敬，我也来写点科普文章。

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

Categories

Categories

## Hall's Theorem

In 1935, the mathematician Philip Hall discovered a criteria of a perfect matching on a bipartite graph, known as Hall’s theorem, aka marriage theorem.

Considering two sets of vertices, denoted as $A=\{a_1, \cdots, a_m\}$ and $B=\{b_1, \cdots, b_n\}$. Edges are connected between $a_i$ and $b_j$ for some pairs of $(i, j)$. Here, we admit multiple edges between two vertices. This graph, named as $G$, is called a bipartite graph. One may think the bipartite graph as a model of a marriage system. Taken set $A$ and set $B$ as boys and girls, an edge between a boy and a girl tells that they might be a couple. A natural question arises that whether there exists a perfect matching, that is, every boy can find his girl without conflicting with other boys. Put formally, a perfect matching is an injective map from $A$ to $B$ which induces a subgraph of $G$.

Hall’s theorem asserted that there is a perfect matching in above bipartite graph $G$ if and on if for every subsets $S$ of $A$, the cardinal number of $S$(number of the members in a set) does not exceed the number of the neighbors of $S$. Here, the neighbors of $S$ are all vertices in $B$ which are connected with one vertex in $S$.

The necessary condition apparently holds. On the other hand, the proof of the sufficient part is a little bit tricky. Challenge yourself with this problem.

Now we represent several applications of Hall’s theorem.

• Let $A=(a_{ij})$ be a matrix of order $n$ with nonnegative integers as entries, such that every row and column of $A$ has sum $l$. Then $A$ is the sum of $l$ permutation matrices.
• Suppose all vertices of a directed graph $G$ have the same in-degrees and out-degrees of $l$, a fixed positive integer. Thus the graph can be separated as $l$ groups of circles. Every vertex appears exactly once in each group, and each edge appears in only one circle.
• (Birkhoff-von Neumann theorem) A doubly stochastic matrix, is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Assertion: every doubly stochastic matrix is mere a convex combination of permutation matrices.

The first two questions are equivalent with each other if one noticed the relation between a graph and its adjacent matrix. In addition, in the first problem, we construct a bipartite graph $G$ consisting of $2n$ vertices, $u_1, \cdots, u_n$ and $v_1, \cdots, v_n$ and $a_{ij}$ edges between each pair of vertices $u_i$ and $v_j$. It can be easily verified that this graph meets the condition required in Hall’s theorem through contradictory argument. Thus we get a perfect matching in this graph, which conversely represent a permutation matrix. After Eliminating the perfect matching in this graph, it become to the situation of $l-1$ in-degrees and out-degrees. This allows us to use mathematical induction on the parameter $l$.

If the entries of the matrix are all rational in the third problem, the result is reduced to the first problem. Still, we shall cover the gap between rational numbers and reals. Denote all permutation matrix as $M_1, \cdots, M_{n!}$. For each matrix $(a_{ij})$ meets the requirement that the sum of each row or each column is 1, one can approach it by $(a_{ij}^n)$ with rational entries which is also doubly stochastic. Thus we can decompose the rational matrix $(a_{ij}^n)$ into a convex combination of permutation matrices with rational coefficient $c_k^n$, where $k \in \{1, \cdots, n!\}$. By finding convergent subsequence in each $(c_k^n)_{n=1}^\infty$, one can require that all these subsequences are convergent for the same indices, and they converge to a limit $c_k$. After all, the original matrix $(a_{ij})$ can be expressed as a convex combination of permutation matrices with coefficients $c_k$.