December 2021 – A Point of View.

Stierlitz The Spy. St. Petersburg 2021, problem 10.4.

So, who is Stierlitz? He was a Soviet spy, who worked undercover as a senior German officer during WW2 in Hitllers’s Germany. There was a russian television series “Seventeen Moments of Spring”, aired before the collapse of the Berlin wall, which portrayed the deeds of Stierlitz. This was a popular movie in Bulgaria in those days behind the Iron Curtain, when films were rare. I remember watching some TV series as a child.
So, about the problem. A typical Russian one. The more techniques you know the worse. The first thing that occurred to me upon seeing it was the probabilistic approach. Unfortunately, I didn’t manage it that way. Let me first present the problem. I used the translation given in [1]

Problem (10.4, St. Petersburg 2021) Stierlitz wants to send an encryption to the Center, which is a string containing $100$ characters, each a “dot” or a “dash”. The instruction he received from the Center the day before about conspiracy reads:
i) when transmitting encryption over the radio, exactly $49$ characters should be replaced with their opposites;
ii) the location of the “wrong” characters is decided by the transmitting side and the Center is not informed of it.
Prove that Stierlitz can send $10$ encryptions, each time choosing some $49$ characters to flip, such that when the Center receives these $10$ ciphers, it may unambiguously restore the original code.

A possible probabilistic approach.

The problem can be reworded. Let $B$ be the space of all binary strings of length $100$ and consider the Hamming metric $d(\cdot, \cdot)$ . That is, for any $x,y\in B$ we denote as $d(x,y)$ the number of bits in which $x$ and $y$ differ. Denote by $S(x,r)$ the sphere with center $x$ and radius $r$ , that is, $\displaystyle S(x,r):= \{z\in B : d(x,z)=r\}.$ The problem claims that for any $x\in B$ there exist ten points (strings) $x_1,x_2,\dots,x_{10}\in B$ such that $\displaystyle \bigcap_{i=1}^{10}S(x_i,10)=x.$
It’s enough to show that there exist $10$ spheres that intersect at exactly one point. If this point is not $x$ but, say, $y$ we can “translate” the spheres by flipping the bits of their centers at the positions where $y$ differes from $x.$ A standard setup is to choose randomly and independently ten points $x_i\in B$ and investigate the expected number of points of their intersection. I did some calculations, and as it turns out this number is quite large.

Solution.

We substitute dot and dash by o and 1. Suppose the string Stielitz wants to transmit consists of $100$ zeroes $\underbrace{0\,0\dots 0}_{100 \text{ times}}.$ If it is something else just flip appropriately some zeroes to ones and vice versa in the following lines. The first two strings Stierlitz transmits are

$1.\quad\underbrace{0\,0\dots 0}_{49 \text{ zeroes}}\,\underbrace{1\,1\dots 1}_{49\text{ ones}}\,0\,0$

$2. \quad\underbrace{1\,1\dots 1}_{49 \text{ ones}}\,\underbrace{0\,0\dots 0}_{49\text{ zeroes}}\,0\,0$

Note that this reveals to the Center the last two characters, in this particular case $0\,0$ . Indeed, let $s_1$ and $s_2$ be the two strings obtained by the above ones by truncating the last two characters and $s_0$ be the Stierlitz’s original one without the last two bits . Thus, $s_0,s_1,s_2$ consist of $98$ characters and $s_1,s_2$ differ at each position. It means that one of them differs from $s_0$ in at least $49$ bits, hence the last two bits of the original string cannot differ from the corresponding bits of the first two encodings. The next two strings Stierlitz sends are

$3.\quad\underbrace{0\,0\dots 0}_{47 }\,\underbrace{1\,1\dots 1}_{47}\,0\,0\,0\,0\,1\,1$

$4. \quad\underbrace{1\,1\dots 1}_{47 }\,\underbrace{0\,0\dots 0}_{47}\,0\,0\,0\,0\,1\,1$

The Center already knows that the real last two characters are $0\,0$ , hence the rest of the strings must differ from the original at exactly $47$ positions. The same argument as above yields the $4$ characters following the first $94$ ones coincide with the original. Thus, the Center knows the last $2+4=6$ symbols. Stierlitz proceeds the same way, every pair of encodings reveals the another $2^k, k=1,2,\dots$ characters. The ninth and tenth strings are

$9.\quad\underbrace{0\,0\dots 0}_{19 }\,\underbrace{1\,1\dots 1}_{19}\,\underbrace{\,0\,0\dots 0}_{32}\,\underbrace{1\,1\dots,1}_{30}$

$10.\quad\underbrace{1\,1\dots 1}_{19 }\,\underbrace{0\,0\dots 0}_{19}\,\underbrace{\,0\,0\dots 0}_{32}\,\underbrace{1\,1\dots,1}_{30}$

The Center already knows the last $2+4+8+16=30$ characters, hence the first $70$ symbols of these two strings differ at exactly $19$ bits from the original one. So, the Center reveals additional $32$ bits and knows the last $62$ ones, in our case all zeroes . Now, look at transmitted string #1. We see that it differs from the bits already known at $49$ positions. That is, no other differences can occur, hence the first $38$ bits of the original are exactly as in the string #1, in our case $38$ zeroes. The center knows the whole original string.

References.
[1] AoPS thread of this problem.

Traps in the Probabilistic Method. Part 4.

Here I try to present another examples on the topic I’ve previously discussed (the links are at the end). In many cases, the probabilistic approach is a powerful weapon. Yet, a lot of students overplay trying to solve a problem by using the probabilistic method when actually it’s easier and simpler to provide a combinatorial proof. Here is a concrete problem, given at some national mathematical olympiad.

Problem (Taiwan NMO 2006). There are $n$ safes and $n$ keys. Each key can open only one safe, and each safe can be opened by only one key. We place randomly one key into each safe. Then, $n-k$ safes, $0\le k\le n,$ are randomly chosen, and then locked. What is the probability that we can open all the safes with the $k$ keys in the two remaining $k$ safes? (Once a safe is opened, the key inside the safe can be used to open another safe.)

A solid but not creative way to deal with this problem is by calculating the number of certain permutations. See [1] for some proofs like that. Here are two creative “solutions” from the same thread that try to avoid calculations by using some probabilistic tricks. Both produce the right answer, but are not valid, although the idea is valuable. The last section presents a pure combinatorial solution that is not based on calculations.

The probability of opening all the safes is the probability that the key used to open the last safe was “useless”. This is exactly the probability that there is a key from the first $k$ safes in the last safe. So it is $\displaystyle \frac{k}{n}.$
an user wrote it in a popular forum.

It looks OK at first reading. If it’s possible to open all the safes then the key inside the last one must open one of the initially opened safes. But, which is the last safe? It’s not uniquely defined in case the configuration allows all safes to be opened – generally there are many variants to open all the safes. Of course, we can make a convention about the order the safes are opened and thus the last opened safe be fully determined. But there is another issue. Which is the “last safe” in case we cannot open all the safes? And another one. Why should the probability of a certain key being in the last safe be equidistributed? So, this argument is based upon some intuition, but has many flaws.
As I said, this example is from a tread in AoPS forum [1] and later the same guy tried to elaborate the argument. Here it is.

I’m indeed considering a random “last safe”. Exact definition is:let $\tau$ be a stopping time – the time when we cannot open more safes (all safes are open or we have no more keys). $T = \tau\wedge (n - 1)$ is also a stopping time. The “last safe” is the safe not opened at $T$ with minimal possible number. Let $M_{t}$ be proportion of not opened safes at time $t$ containing keys from the first $k$ safes. $M_{t}$ is a martingale. $T$ – bounded stopping time. $E(M_{T}) = E(M_{0}) = \frac {k}{n}$ by the optional stopping time theorem. And $E(M_{T})$ is the probability we have been searching (the probability of opening all safes is exactly the probability that the last safe contains the key from the first $k$ safes).

The desire to make it valid went even further and exactly the same argument was boosted by some stochastic theory tools as martingales, Doob’s theorem, etc. This way, the issue about which was the last box was cleared, but it posed another ones. Why should $M_T$ be martingale. Or, even if $\mathbb{E}[M_T]=\frac{k}{n}$ why does it imply the probability of the last safe to contain a key from a safe initially opened is $\frac{k}{n}$ ?
I am convinced, in this particular case, using probabilistic ideas makes it more difficult. This is a pure combinatorial problem. Nevertheless, the first argument quoted has an idea that I tried to save.

A pure combinatorial solution.

Let’s first formalize the statement. We have the set $S_n$ of all permutations of $n$ elements and $k\le n$ is a natural number. For any $\sigma\in S_n$ consider the set

$\displaystyle K_{\sigma}:=\bigcup_{i=1}^{\infty}\sigma^i\left( \{1,2,\dots,k\}\right).$

That is, for every $j\in\{1,2,\dots,k\}$ we start iterating applying $\sigma$ on $j$ and after finite number of steps we get to $K_{\sigma}$ that consists of all elements of the cycles that the numbers $1,2,\dots,k$ take part in. We have numbered the safes as $1,2,\dots,n$ and interpret $\sigma(j)$ as the safe that is unlocked by the key in the $j$ -th safe. Let us call the permutation $\sigma$ good if $K_{\sigma}=\{1,2,\dots,n\}$ . Apparently, with the interpretation given, $\sigma$ is a good permutation only if all the safes can be opened if we magically unlock the firs $k$ of them. So, we are looking for the portion of good permutations. In order to do it, we construct an “encoding” of each permutation $\sigma\in S_n$ . We start writing (left to right) $\sigma(1),\sigma(\sigma(1)),\dots, \sigma^{r_1}(1)=1.$ Then we choose the minimum number $j$ among $1,2,\dots,k$ not yet written, and write $\sigma(j),\sigma(\sigma(j)),\dots,\sigma^{r_2}(j)=j.$ We do the same till all numbers among $1,2,\dots,k$ are written. If there is still a natural number less or equal to $n$ that is not written, we choose the minimum one, say $j,$ and write $\sigma(j),\sigma(\sigma(j)),\dots,\sigma^{r_2}(j)=j.$ We again do the same till all numbers $1,2,\dots,n$ are written. The written string (it is a “permutation” in the usual sense) will represent the permutation $\sigma.$ It is easy to see that given that string, we can recover $\sigma.$ The first time the number $1$ is encountered indicates where the cycle generated by $1$ ends. Then, let $j, j\in [1..n]$ be the smaller number that has not yet occurred. We proceed to check the rest of the written numbers till we see $j.$ Thus, we discern the cycle that is generated by $j.$ Doing it till the string ends, we recover $\sigma.$ It means there is a bijection between the permutations and the “encodings”. But any “encoding” in fact is a “permutation” of the numbers $1,2,\dots,n$ . Note that we can unlock all the safes only when the “encoding” ends with a number among $1,2,\dots,k.$ Clearly the number of those “permutations” is $\frac{k}{n}\left|S_n \right|.$
Simpler. Clearer. Pure combinatorics.

Traps in the … part 1.
Traps in the … part 2.
Traps in the … part 3.

References.
[1] https://artofproblemsolving.com/community/c6t309f6h80325_safes_and_keys

Independent Sets in a Tree. USA TSTST 2021, p5.

Suppose, we are given a graph, which is a tree, and want to find an independent set of maximum vertices. That is, the maximum number of vertices, no two of them connected. There are many algorithms to do it. If I am not mistaken, the number of operations needed is linear with respect to the number of vertices. So, it’s easy to make a program and compute it, but it’s not so easy to find some general characterization of this maximum independent set. An interesting question arises. What is the maximum number of vertices $s$ an independent set could consists of, among all trees with $n$ vertices. It is an easy question, since obviously $s\le n-1$ and $s=n-1$ can be achieved in a tree with a root and $n-1$ leaves. This example of a tree has too many leaves, so let us fix the number of leaves that $T$ can have, to be exactly $k, k<n.$ It’s not a trivial question anymore. As we will see, in this case $s\le (n+k-1)/2.$ Moreover, if $s=(n+k-1)/2$ we can give some information about the structure of $T.$ I knew nothing about this fact, so it was curious to see the following problem given at the 2021 US team selection for team selection test (yeah, they have something like that). I think, this problem was a good choice.

Problem (USA TSTST 2021, p5). Let $T$ be a tree on $n$ vertices with exactly $k$ leaves. Suppose that there exists a subset of at least $\displaystyle \frac{n+k-1}{2}$ vertices of $T$ , no two of which are adjacent. Show that the longest path in $T$ contains an even number of edges.

Some motivation.

After trying a couple of thing, I think the right approach is to fix an independent set $S$ of, say, $s$ vertices and try to span a tree on it with $n$ vertices and $k$ leaves complying with $s\ge (n+k-1)/2,$ that is, $n\le 2s-k+1,$ see fig 1. Color the vertices of $S$ with blue and the other vertices – with black. We can choose a root $O$ of $T$ that is black. Apparently, the neighboring vertices of any blue vertex are all black. Trying to make some $1-1$ mapping between blue and black vertices, and having in mind the given restriction, we arrive to some observation about the structure of $T.$

**Fig. 1**. An independent set of $s$ vertices (blue ones)

Solution.

Let $S$ be a set of independent vertices in $T$ with $s:=|S|\ge \displaystyle \frac{n+k-1}{2}.$ Thus, we have

$\displaystyle n\le 2s-k+1\qquad (1)$

Let’s thinks of it in the following way. We are given this set $S$ (see fig. 1, the blue dots) and want to reconstruct somehow $T$ so that $(1)$ holds.
It will be shown that the structure of $T$ complies to a certain rule, and moreover it’s impossible $(1)$ to be strict inequality, the only way is $n=2s-k+1.$ Let $O$ be a vertex of $T, O\notin S$ and $O$ is not a leaf of $T$ . Of course, we can choose a vertex like that, for example, take $v_1,v_2\in S$ ; there is a unique path that connects $v_1$ with $v_2$ and at least one vertex on this path is not in $S.$ Denote it by $O.$ We view on $T$ as a tree with a root $O.$ Having a root, we can compare the vertices. Let’s say a vertex $u\in V(T)$ is one level up a vertex $v\in V(T)$ if we can reach $u$ from $v$ by one hop off the root $O$ . Let $L$ be the set of leaves of $T$ . For each $v\in S\setminus L$ we choose a vertex $u=\mathrm{up}(v)$ which is one level up $v.$ For $v\in S\cap L$ we define $\mathrm{up}(v)=v.$ (fig.2)

Clearly, the sets $\{v,\mathrm{up}(v)\}, v\in S$ are disjoint. Using $(1)$ we prove two things.

$\text{i) } \quad \displaystyle \bigcup_{v\in S}\mathrm{up}(v)\cup S\cup \{O\}=V(T)$
$\displaystyle \text{ii) }\quad \text{All leaves of } T \text{ are in } S.$

Let $k_1:=\left|L\cap S\right|.$ So, $k_1\le k=|L|.$ Note that

$\displaystyle \left|\bigcup_{v\in S}\mathrm{up}(v) \cup S\cup\{O\}\right|=2\left| S\setminus L\right|+\left| S\cap L\right|+1=$
$\displaystyle =2(s-k_1)+k_1+1=2s-k_1+1.$

Using the given condition $(1)$ we get

$\displaystyle 2s-k_1+1 \le n \le 2s-k+1 \qquad(2)$

Since $k_1\le k$ it yields $k=k_1$ and $n=2s-k+1.$ That is, there are not other vertices of $T$ that are outside $\displaystyle \bigcup_{v\in S}\mathrm{up}(v)\cup S\cup \{O\}$ (which is exactly what i) says) and all leaves of $T$ are in $S$ (what ii) claims). So, if we color the vertices of $S$ with blue and the others in black, the structure of $T$ is like in the fig. 3.

Starting from $O$ , every black vertex can have several upper blue vertices but not a black one and every blue vertex can have only one vertex upper than it and it is a black one. Moreover, the leaves of $T$ are colored in blue. Thus, any path in $T$ consists of alternating black and blue vertices. Now, the longest path in $T$ connects some two leaves, hence it consists of even number of edges.

References.
[1] AoPS thread.

Playing Tennis Needs Math.

Suppose you are a tennis champion and are going to have a match against a rival opponent. There are two tennis federations which want to organize the competition, let call them $F1$ and $F2$ . Both have strange and slightly different conventions about how the tournament should go. According to the rules of the federations, the player who manages to score 10 points first wins. You serve first. When serving, you have a probability $p_1$ scoring a point and when your opponent serves this probability is $p_2.$ The first federation $F1$ wants the serves to alternate, but the second one proposes the serving guy to keep doing it until he loses a point, and then the other serves the next play.
You have to decide which federation to organize the tournament to increase your chances of winning. Prove that your decision doesn’t affect your chances of winning. They are the same under each of the schemes.

This problem was communicated to me by a friend. A very curious fact, that is not intuitive. Surprisingly (or not at all), the proof doesn’t use any calculations at all. This is one of the problems that a certain interpretation makes obvious. But, there is some difficulty of finding the right approach if you haven’t seen things like that.

Put $n$ instead of $10$ . We’ll show it doesn’t matter which convention is chosen. The probability that you win is the same. Suppose you play a slightly different game. Two players $A$ and $B$ have in dispose $2n-1$ tennis courts numbered as $1,2,\dots, 2n-1$ . The odd ones are black, the even – white. On the black courts serves $A$ , on the white ones – $B.$ They start playing on court number $1$ and each tennis court is used for exactly one play. The player who gets more points wins the whole game.
Suppose there are two different schemes of how the tennis courts are used.

First scheme. Every time $A$ wins, the players move to the first black court (with the lowest number) that has not yet been used. In case $B$ wins, they go to the first white unused court. If black (resp. white) courts get exhausted, the players continue on the remaining white (resp. black) courts.

Keep in mind that in case the courts colored in a given color run out, it means the game is over, that is, we already have a winner. Indeed, the players move to black (resp. white) court only when the player $A$ (resp. $B$ ) wins. That way, when there are no courts of some color left, one of the players has already got $n$ points. So, it doesn’t matter who will serve in the next games.

Second scheme. After every game they move to the next court.

Obviously, the result of the game does not depend on the scheme of using courts, because the player $A$ plays on black courts exactly $n$ times under both schemes. Moreover, it’s the same game as the original one in the sense that the probability of $A$ winning is the same.

References.
[1] AoPS Thread.