ALIBABA 2021

In a dance party initially there are $20$ girls and $22$ boys in the pool and infinitely many more girls and boys waiting outside. In each round, a participant is picked uniformly at random; if a girl is picked, then she invites a boy from the pool to dance and then both of them elave the party after the dance; while if a boy is picked, then he invites a girl and a boy from the waiting line and dance together. The three of them all stay after the dance. The party is over when there are only (two) boys left in the pool.

(a) What is the probability that the party never ends?

(b) Now the organizer of this party decides to reverse the rule, namely that if a girl is picked, then she invites a boy and a girl from the waiting line to dance and the three stay after the dance; while if a boy is picked, he invites a girl from the pool to dance and both leave after the dance. Still the party is over when there are only (two) boys left in the pool. What is the expected number of rounds until the party ends?

Consider a computer network consisting of servers and bi-directional communication channels among them. Unfortunately, not all channels operate. Each direction of each channel fails with probability $p$ and operates otherwise. (All of these stochastic events are mutually independent, and $0 \le p \le 1$ .) There is a root serve, denoted by $r$ . We call the network operational, if all serves can reach $r$ using only operating channels. Note that we do not require $r$ to be able to reach any servers.

Show that the probability of the network to be operational does not depend on the choice of $r$ . (In other words, for any two distinct root servers $r_1$ and $r_2$ , the operational probability is the same.)

Given positive integers $k \ge 2$ and $m$ sufficiently large. Let $\mathcal{F}_m$ be the infinite family of all the (not necessarily square) binary matrices which contain exactly $m$ 1's. Denote by $f(m)$ the maximum integer $L$ such that for every matrix $A \in \mathcal{F}_m$ , there always exists a binary matrix $B$ of the same dimension such that (1) $B$ has at least $L$ 1-entries; (2) every entry of $B$ is less or equal to the corresponding entry of $A$ ; (3) $B$ does not contain any $k \times k$ all-1 submatrix. Show the equality $$\lim_{m \to \infty} \frac{\ln f(m)}{\ln m}=\frac{k}{k+1}.$$

Let $(\Omega, \mathcal{A},\mathbb{P})$ be a standard probability space, and $\mathcal{X}$ be the set of all bounded random variables. For $t>0$ , defined the mapping $R_t$ by $$R_t(X)=t\log \mathbb{E}[\exp(X/t)], X \in \mathcal{X},$$ and for $t \in (0,1)$ define the mapping $Q_t$ by $$Q_t(X)=\inf\{x \in \mathbb{R}: \mathbb{P}(X>x) \le t\}, X \in \mathcal{X}.$$ For two mappings $f,g:\mathcal{X} \to [-\infty,\infty)$ , defined the operator $\square$ by $$f\square g(X)=\inf\{f(Y)+g(X-Y): Y \in \mathcal{X}\}, X \in \mathcal{X}.$$ (a) Show that, for $t,s>0$ , $$R_t \square R_s=R_{t+s}.$$ (b) Show that, for $t,s>0$ with $t+s<1$ , $$Q_t \square Q_s=Q_{t+s}.$$

Suppose that $A$ is a finite subset of $\mathbb{R}^d$ such that

(a) every three distinct points in $A$ contain two points that are exactly at unit distance apart, and

(b) the Euclidean norm of every point $v$ in $A$ satisfies $$\sqrt{\frac{1}{2}-\frac{1}{2\vert A\vert}} \le \|v\| \le \sqrt{\frac{1}{2}+\frac{1}{2\vert A\vert}}.$$ Prove that the cardinality of $A$ is at most $2d+4$ .

Let $M(t)$ be measurable and locally bounded function, that is, $$M(t) \le C_{a,b}, \forall 0 \le a \le t \le b<\infty$$ with some constant $C_{a,b}$ , from $[0,\infty)$ to $[0,\infty)$ such that $$M(t) \le 1+\int_0^t M(t-s)(1+t)^{-1}s^{-1/2} ds, \forall t \ge 0.$$ Show that $$M(t) \le 10+2\sqrt{5}, \forall t \ge 0.$$

A subset $Q \subset H^s(\mathbb{R})$ is said to be equicontinuous if for any $\varepsilon>0$ , $\exists \delta>0$ such that $$\|f(x+h)-f(x)\|_{H^s}<\varepsilon, \forall \vert h\vert<\delta, f \in Q.$$ Fix $r<s$ , given a bounded sequence of functions $f_n \in H^s(\mathbb{R}$ . If $f_n$ converges in $H^r(\mathbb{R})$ and equicontinuous in $H^s(\mathbb{R})$ , show that it also converges in $H^s(\mathbb{R})$ .

Let $f(z)$ be a holomorphic function in $\{\vert z\vert \le R\}$ ( $0<R<\infty$ ). Define $$M(r,f)=\max_{\vert z\vert=r} \vert f(z)\vert, A(r,f)=\max_{\vert z\vert=r} \text{Re}\{f(z)\}.$$ Show that $$M(r,f) \le \frac{2r}{R-r}A(R,f)+\frac{R+r}{R-r} \vert f(0)\vert, \forall 0 \le r<R.$$

Let $\varepsilon$ be positive constant and $u$ satisfies that $$\begin{cases} (\partial_t-\varepsilon\partial_x^2-\partial_y^2)u=0, & (t,x,y) \in \mathbb{R}_+ \times \mathbb{R} \times \mathbb{R}_+, \partial_y u\vert_{y=0}=\partial_x h, &u\vert_{t=0}=0. & \end{cases}$$ Here $h(t,x)$ is a smooth Schwartz function. Define the operator $e^{a\langle D\rangle}$ $$\mathcal{F}_x(e^{a\langle D\rangle} f)(k)=e^{a\langle k\rangle} \mathcal{F}_x(f)(k), \langle k\rangle=1+\vert k\vert,$$ where $\mathcal{F}_x$ stands for the Fourier transform in $x$ . Show that $$\int_0^T \|e^{(1-s)\langle D\rangle} u\|_{L_{x,y}^2}^2 ds \le C \int_0^T \|e^{(1-s)\langle D\rangle} h\|_{H_x^{\frac{1}{4}}}^2 ds$$ with constant $C$ independent of $\varepsilon, T$ and $h$ .

In $\mathbb{R}^3$ , for a rectangular box $\Delta$ , let $10\Delta$ be the box with the same center as $\Delta$ but dilated by $10$ . For example, if $\Delta$ is an $1 \times 1 \times 10$ box (hence with Lebesgue measure $10$ ), then $10\Delta$ is the $10 \times 10 \times 100$ box with the same center and orientation as $\Delta$ .

\medskip

If two rectangular boxes $\Delta_1$ and $\Delta_2$ satisfy $\Delta_1 \subset 10\Delta_2$ and $\Delta_2 \subset 10 \Delta_1$ , we say that they are almost identical.

Find the largest real number $a$ such that the following holds for some $C=C(a)>0$ :

For every positive integer $N$ and every collection $S$ of $1 \times 1 \times N$ boxes in $\mathbb{R}^3$ , assuming that (i) $\vert S\vert=N$ , (ii) every pair of boxes $(\Delta_1,\Delta_2)$ taken from $S$ are not almost identical, and (iii) the long edge of each box in $S$ forms an angle $\frac{\pi}{4}$ against the $xy$ -plane. Then the volume $$\left\vert \bigcup_{\Delta \in S} \Delta\right\vert \ge CN^a.$$

Let $M$ be a compact orientable $2n$ -manifold with boundary, where $n \ge 2$ . Suppose that $H_0(M;\mathbb{Q}) \cong \mathbb{Q}$ and $H_i(M;\mathbb{Q})=0$ for $i>0$ . Prove that the order of $H_{n-1}(\partial M; \mathbb{Z})$ is a square number.

Let $A=(a_{ij})$ be a $5 \times 5$ matrix with $a_{ij}=\min\{i,j\}$ . Suppose $f:\mathbb{R}^5 \to \mathbb{R}^5$ is a smooth map such that $f(\Sigma) \subset \Sigma$ , where $\Sigma=\{x \in \mathbb{R}^5: xAx^T=1\}$ . Denote by $f^{(n)}$ te $n$ -th iterate of $f$ . Prove that there does not exist $N \ge 1$ such that $$\inf_{x \in \Sigma} \| f^{(n)}(x)-x\|>0, \forall n \ge N.$$

Let $M_n=\{(u,v) \in S^n \times S^n: u \cdot v=0\}$ , where $n \ge 2$ , and $u \cdot v$ is the Euclidean inner product of $u$ and $v$ . Suppose that the topology of $M_n$ is induces from $S^n \times S^n$ .

(1) Prove that $M_n$ is a connected regular submanifold of $S^n \times S^n$ .

(2) $M_n$ is Lie Group if and only if $n=2$ .

Let $f$ be a smooth function on $\mathbb{R}^n$ , denote by $G_f=\{(x,f(x)) \in \mathbb{R}^{n+1}: x \in \mathbb{R}^n\}$ . Let $g$ be the restriction of the Euclidean metric on $G_f$ .

(1) Prove that $g$ is a complete metric.

(2) If there exists $\Lambda>0$ , such that $-\Lambda I_n \le \text{Hess}(f) \le \Lambda I_n$ , where $I_n$ is the unit matrix of order $n$ , and $\text{Hess}8f)$ is the Hessian matrix of $f$ , then the injectivity radius of $(G_f,g)$ is at least $\frac{\pi}{2\Lambda}$ .

Let $(M,g)$ be an $n$ -dimensional complete Riemannian manifold with $n \ge 2$ . Suppose $M$ is connected and $\text{Ric} \ge (n-1)g$ , where $\text{Ric}$ is the Ricci tensor of $(M,g)$ . Denote by $\text{d}g$ the Riemannian measure of $(M,g)$ and by $d(x,y)$ the geodesic distance between $x$ and $y$ . Prove that $$\int_{M \times M} \cos d(x,y) \text{d}g(x)\text{d}g(y) \ge 0.$$ Moreover, equality holds if and only if $(M,g)$ is isometric to the unit round sphere $S^n$ .

Let $G$ be a finite group, and let $H_1, H_2 \subset G$ be two subgroups. Suppose that for any representation of $G$ on a finite-dimensional complex vector space $V$ , one has that $$\text{dim} V^{H_1}=\text{dim} V^{H_2},$$ where $V^{H_i}$ is the subspace of $H_i$ -invariant vectors in $V$ ( $i=1,2$ ). Prove that $$Z(G) \cap H_1=Z(G) \cap H_2.$$ Here $Z(G)$ denotes the center of $G$ .

Let $p$ be a prime number and let $\mathbb{F}_p$ be the finite field with $p$ elements. Consider an automorphism $\tau$ of the polynomial ring $\mathbb{F}_p[x]$ given by $$\tau(f)(x)=f(x+1).$$ Let $R$ denote the subring of $\mathbb{F}_p[x]$ consisting of those polynomials $f$ with $\tau(f)=f$ . Find a polynomial $g \in \mathbb{F}_p[x]$ such that $\mathbb{F}_p[x]$ is a free module over $R$ with basis $g,\tau(g),\dots,\tau^{p-1}(g)$ .

Let $p$ be an odd prime number, and let $m \ge 0$ and $N \ge 1$ be integers. Let $\Lambda$ be a free $\mathbb{Z}/p^N\mathbb{Z}$ -module of rank $2m+1$ , equipped with a perfect symmetric $\mathbb{Z}/p^N\mathbb{Z}$ -bilinear form $$( ,\,): \Lambda \times \Lambda \to \mathbb{Z}/p^N\mathbb{Z}.$$ Here ``perfect'' means that the induced map $$\Lambda \to \text{Hom}_{\mathbb{Z}/p^N\mathbb{Z}}(\Lambda, \mathbb{Z}/p^N\mathbb{Z}), x \mapsto (x,\cdot)$$ is an isomorphism. Find the cardinality of the set $$\{x \in \Lambda: (x,x)=0\},$$ expressed in terms of $p,m,N$ .

Find all real numbers of the form $\sqrt[p]{2021+\sqrt[q]{a}}$ that can be expressed as a linear combination of roots of unity with rational coefficients, where $p$ and $q$ are (possible the same) prime numbers, and $a>1$ is an integer, which is not a $q$ -th power.

Let $M=\bigoplus_{i \in \mathbb{Z}} \mathbb{C}e_i$ be an infinite dimensional $\mathbb{C}$ -vector space, and let $\text{End}(M)$ denote the $\mathbb{C}$ -algebra of $\mathbb{C}$ -linear endomorphisms of $M$ . Let $A$ and $B$ be two commuting elements in $\text{End}(M)$ satisfying the following condition: there exist integers $m \le n<0<p \le q$ satisfying $\text{gd}(-m,p)=\text{gcd}(-n,q)=1$ , and such that for every $j \in \mathbb{Z}$ , one has $$Ae_j=\sum_{i=j+m}^{j+n} a_{i,j}e_i, \text{with } a_{i,j} \in \mathbb{C}, a_{j+m,j}a_{j+n,j} \ne 0,$$ $$Be_j=\sum_{i=j+p}^{j+q} b_{i,j}e_i, \text{with } b_{i,j} \in \mathbb{C}, b_{j+p,j}b_{j+q,j} \ne 0.$$ Let $R \subset \text{End}(M)$ be the $\mathbb{C}$ -subalgebra generated by $A$ and $B$ . Note that $R$ is commutative and $M$ can be regarded as an $R$ -module.

(a) Show that $R$ is an integral domain and is isomorphic to $R \cong \mathbb{C}[x,y]/f(x,y)$ , where $f(x,y)$ is a non-zero polynomial such that $f(A,B)=0$ .

(b) Let $K$ be the fractional field of $R$ . Show that $M \otimes_R K$ is a $1$ -dimensional vector space over $K$ .