MathDB
Problems
Contests
Undergraduate contests
Alibaba Global Math Competition
2021 Alibaba Global Math Competition
2021 Alibaba Global Math Competition
Part of
Alibaba Global Math Competition
Subcontests
(20)
20
1
Hide problems
Structure of commutative subalgebra of endomorphism ring
Let
M
=
⨁
i
∈
Z
C
e
i
M=\bigoplus_{i \in \mathbb{Z}} \mathbb{C}e_i
M
=
⨁
i
∈
Z
C
e
i
be an infinite dimensional
C
\mathbb{C}
C
-vector space, and let
End
(
M
)
\text{End}(M)
End
(
M
)
denote the
C
\mathbb{C}
C
-algebra of
C
\mathbb{C}
C
-linear endomorphisms of
M
M
M
. Let
A
A
A
and
B
B
B
be two commuting elements in
End
(
M
)
\text{End}(M)
End
(
M
)
satisfying the following condition: there exist integers
m
≤
n
<
0
<
p
≤
q
m \le n<0<p \le q
m
≤
n
<
0
<
p
≤
q
satisfying
gd
(
−
m
,
p
)
=
gcd
(
−
n
,
q
)
=
1
\text{gd}(-m,p)=\text{gcd}(-n,q)=1
gd
(
−
m
,
p
)
=
gcd
(
−
n
,
q
)
=
1
, and such that for every
j
∈
Z
j \in \mathbb{Z}
j
∈
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
⊂
End
(
M
)
R \subset \text{End}(M)
R
⊂
End
(
M
)
be the
C
\mathbb{C}
C
-subalgebra generated by
A
A
A
and
B
B
B
. Note that
R
R
R
is commutative and
M
M
M
can be regarded as an
R
R
R
-module.(a) Show that
R
R
R
is an integral domain and is isomorphic to
R
≅
C
[
x
,
y
]
/
f
(
x
,
y
)
R \cong \mathbb{C}[x,y]/f(x,y)
R
≅
C
[
x
,
y
]
/
f
(
x
,
y
)
, where
f
(
x
,
y
)
f(x,y)
f
(
x
,
y
)
is a non-zero polynomial such that
f
(
A
,
B
)
=
0
f(A,B)=0
f
(
A
,
B
)
=
0
.(b) Let
K
K
K
be the fractional field of
R
R
R
. Show that
M
⊗
R
K
M \otimes_R K
M
⊗
R
K
is a
1
1
1
-dimensional vector space over
K
K
K
.
19
1
Hide problems
For which p,q is this nested radical a sum of roots of unity?
Find all real numbers of the form
2021
+
a
q
p
\sqrt[p]{2021+\sqrt[q]{a}}
p
2021
+
q
a
that can be expressed as a linear combination of roots of unity with rational coefficients, where
p
p
p
and
q
q
q
are (possible the same) prime numbers, and
a
>
1
a>1
a
>
1
is an integer, which is not a
q
q
q
-th power.
18
1
Hide problems
Isotropic vectors of perfect symmetric bilinear form over Z/p^nZ
Let
p
p
p
be an odd prime number, and let
m
≥
0
m \ge 0
m
≥
0
and
N
≥
1
N \ge 1
N
≥
1
be integers. Let
Λ
\Lambda
Λ
be a free
Z
/
p
N
Z
\mathbb{Z}/p^N\mathbb{Z}
Z
/
p
N
Z
-module of rank
2
m
+
1
2m+1
2
m
+
1
, equipped with a perfect symmetric
Z
/
p
N
Z
\mathbb{Z}/p^N\mathbb{Z}
Z
/
p
N
Z
-bilinear form
(
,
)
:
Λ
×
Λ
→
Z
/
p
N
Z
.
(\, ,\,): \Lambda \times \Lambda \to \mathbb{Z}/p^N\mathbb{Z}.
(
,
)
:
Λ
×
Λ
→
Z
/
p
N
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
∈
Λ
:
(
x
,
x
)
=
0
}
,
\{x \in \Lambda: (x,x)=0\},
{
x
∈
Λ
:
(
x
,
x
)
=
0
}
,
expressed in terms of
p
,
m
,
N
p,m,N
p
,
m
,
N
.
17
1
Hide problems
Shift-invariant basis for polynomials over F_p
Let
p
p
p
be a prime number and let
F
p
\mathbb{F}_p
F
p
be the finite field with
p
p
p
elements. Consider an automorphism
τ
\tau
τ
of the polynomial ring
F
p
[
x
]
\mathbb{F}_p[x]
F
p
[
x
]
given by
τ
(
f
)
(
x
)
=
f
(
x
+
1
)
.
\tau(f)(x)=f(x+1).
τ
(
f
)
(
x
)
=
f
(
x
+
1
)
.
Let
R
R
R
denote the subring of
F
p
[
x
]
\mathbb{F}_p[x]
F
p
[
x
]
consisting of those polynomials
f
f
f
with
τ
(
f
)
=
f
\tau(f)=f
τ
(
f
)
=
f
. Find a polynomial
g
∈
F
p
[
x
]
g \in \mathbb{F}_p[x]
g
∈
F
p
[
x
]
such that
F
p
[
x
]
\mathbb{F}_p[x]
F
p
[
x
]
is a free module over
R
R
R
with basis
g
,
τ
(
g
)
,
…
,
τ
p
−
1
(
g
)
g,\tau(g),\dots,\tau^{p-1}(g)
g
,
τ
(
g
)
,
…
,
τ
p
−
1
(
g
)
.
16
1
Hide problems
Subgroups with same size of invariant sets under all representations
Let
G
G
G
be a finite group, and let
H
1
,
H
2
⊂
G
H_1, H_2 \subset G
H
1
,
H
2
⊂
G
be two subgroups. Suppose that for any representation of
G
G
G
on a finite-dimensional complex vector space
V
V
V
, one has that
dim
V
H
1
=
dim
V
H
2
,
\text{dim} V^{H_1}=\text{dim} V^{H_2},
dim
V
H
1
=
dim
V
H
2
,
where
V
H
i
V^{H_i}
V
H
i
is the subspace of
H
i
H_i
H
i
-invariant vectors in
V
V
V
(
i
=
1
,
2
i=1,2
i
=
1
,
2
). Prove that
Z
(
G
)
∩
H
1
=
Z
(
G
)
∩
H
2
.
Z(G) \cap H_1=Z(G) \cap H_2.
Z
(
G
)
∩
H
1
=
Z
(
G
)
∩
H
2
.
Here
Z
(
G
)
Z(G)
Z
(
G
)
denotes the center of
G
G
G
.
15
1
Hide problems
Positivity of integral on manifold with bound on Ricci tensor
Let
(
M
,
g
)
(M,g)
(
M
,
g
)
be an
n
n
n
-dimensional complete Riemannian manifold with
n
≥
2
n \ge 2
n
≥
2
. Suppose
M
M
M
is connected and
Ric
≥
(
n
−
1
)
g
\text{Ric} \ge (n-1)g
Ric
≥
(
n
−
1
)
g
, where
Ric
\text{Ric}
Ric
is the Ricci tensor of
(
M
,
g
)
(M,g)
(
M
,
g
)
. Denote by
d
g
\text{d}g
d
g
the Riemannian measure of
(
M
,
g
)
(M,g)
(
M
,
g
)
and by
d
(
x
,
y
)
d(x,y)
d
(
x
,
y
)
the geodesic distance between
x
x
x
and
y
y
y
. Prove that
∫
M
×
M
cos
d
(
x
,
y
)
d
g
(
x
)
d
g
(
y
)
≥
0.
\int_{M \times M} \cos d(x,y) \text{d}g(x)\text{d}g(y) \ge 0.
∫
M
×
M
cos
d
(
x
,
y
)
d
g
(
x
)
d
g
(
y
)
≥
0.
Moreover, equality holds if and only if
(
M
,
g
)
(M,g)
(
M
,
g
)
is isometric to the unit round sphere
S
n
S^n
S
n
.
14
1
Hide problems
Lower bound on injectivity radius of graph
Let
f
f
f
be a smooth function on
R
n
\mathbb{R}^n
R
n
, denote by
G
f
=
{
(
x
,
f
(
x
)
)
∈
R
n
+
1
:
x
∈
R
n
}
G_f=\{(x,f(x)) \in \mathbb{R}^{n+1}: x \in \mathbb{R}^n\}
G
f
=
{(
x
,
f
(
x
))
∈
R
n
+
1
:
x
∈
R
n
}
. Let
g
g
g
be the restriction of the Euclidean metric on
G
f
G_f
G
f
.(1) Prove that
g
g
g
is a complete metric.(2) If there exists
Λ
>
0
\Lambda>0
Λ
>
0
, such that
−
Λ
I
n
≤
Hess
(
f
)
≤
Λ
I
n
-\Lambda I_n \le \text{Hess}(f) \le \Lambda I_n
−
Λ
I
n
≤
Hess
(
f
)
≤
Λ
I
n
, where
I
n
I_n
I
n
is the unit matrix of order
n
n
n
, and
Hess
8
f
)
\text{Hess}8f)
Hess
8
f
)
is the Hessian matrix of
f
f
f
, then the injectivity radius of
(
G
f
,
g
)
(G_f,g)
(
G
f
,
g
)
is at least
π
2
Λ
\frac{\pi}{2\Lambda}
2Λ
π
.
13
1
Hide problems
Regular submanifold usually has no Lie group structure
Let
M
n
=
{
(
u
,
v
)
∈
S
n
×
S
n
:
u
⋅
v
=
0
}
M_n=\{(u,v) \in S^n \times S^n: u \cdot v=0\}
M
n
=
{(
u
,
v
)
∈
S
n
×
S
n
:
u
⋅
v
=
0
}
, where
n
≥
2
n \ge 2
n
≥
2
, and
u
⋅
v
u \cdot v
u
⋅
v
is the Euclidean inner product of
u
u
u
and
v
v
v
. Suppose that the topology of
M
n
M_n
M
n
is induces from
S
n
×
S
n
S^n \times S^n
S
n
×
S
n
.(1) Prove that
M
n
M_n
M
n
is a connected regular submanifold of
S
n
×
S
n
S^n \times S^n
S
n
×
S
n
.(2)
M
n
M_n
M
n
is Lie Group if and only if
n
=
2
n=2
n
=
2
.
12
1
Hide problems
Smooth map can not avoid fixed points for all large n
Let
A
=
(
a
i
j
)
A=(a_{ij})
A
=
(
a
ij
)
be a
5
×
5
5 \times 5
5
×
5
matrix with
a
i
j
=
min
{
i
,
j
}
a_{ij}=\min\{i,j\}
a
ij
=
min
{
i
,
j
}
. Suppose
f
:
R
5
→
R
5
f:\mathbb{R}^5 \to \mathbb{R}^5
f
:
R
5
→
R
5
is a smooth map such that
f
(
Σ
)
⊂
Σ
f(\Sigma) \subset \Sigma
f
(
Σ
)
⊂
Σ
, where
Σ
=
{
x
∈
R
5
:
x
A
x
T
=
1
}
\Sigma=\{x \in \mathbb{R}^5: xAx^T=1\}
Σ
=
{
x
∈
R
5
:
x
A
x
T
=
1
}
. Denote by
f
(
n
)
f^{(n)}
f
(
n
)
te
n
n
n
-th iterate of
f
f
f
. Prove that there does not exist
N
≥
1
N \ge 1
N
≥
1
such that
inf
x
∈
Σ
∥
f
(
n
)
(
x
)
−
x
∥
>
0
,
∀
n
≥
N
.
\inf_{x \in \Sigma} \| f^{(n)}(x)-x\|>0, \forall n \ge N.
x
∈
Σ
in
f
∥
f
(
n
)
(
x
)
−
x
∥
>
0
,
∀
n
≥
N
.
11
1
Hide problems
Order of homology group of boundary is a square
Let
M
M
M
be a compact orientable
2
n
2n
2
n
-manifold with boundary, where
n
≥
2
n \ge 2
n
≥
2
. Suppose that
H
0
(
M
;
Q
)
≅
Q
H_0(M;\mathbb{Q}) \cong \mathbb{Q}
H
0
(
M
;
Q
)
≅
Q
and
H
i
(
M
;
Q
)
=
0
H_i(M;\mathbb{Q})=0
H
i
(
M
;
Q
)
=
0
for
i
>
0
i>0
i
>
0
. Prove that the order of
H
n
−
1
(
∂
M
;
Z
)
H_{n-1}(\partial M; \mathbb{Z})
H
n
−
1
(
∂
M
;
Z
)
is a square number.
10
1
Hide problems
Union of not almost identical boxes must have large volume
In
R
3
\mathbb{R}^3
R
3
, for a rectangular box
Δ
\Delta
Δ
, let
10
Δ
10\Delta
10Δ
be the box with the same center as
Δ
\Delta
Δ
but dilated by
10
10
10
. For example, if
Δ
\Delta
Δ
is an
1
×
1
×
10
1 \times 1 \times 10
1
×
1
×
10
box (hence with Lebesgue measure
10
10
10
), then
10
Δ
10\Delta
10Δ
is the
10
×
10
×
100
10 \times 10 \times 100
10
×
10
×
100
box with the same center and orientation as
Δ
\Delta
Δ
.\medskipIf two rectangular boxes
Δ
1
\Delta_1
Δ
1
and
Δ
2
\Delta_2
Δ
2
satisfy
Δ
1
⊂
10
Δ
2
\Delta_1 \subset 10\Delta_2
Δ
1
⊂
10
Δ
2
and
Δ
2
⊂
10
Δ
1
\Delta_2 \subset 10 \Delta_1
Δ
2
⊂
10
Δ
1
, we say that they are almost identical.Find the largest real number
a
a
a
such that the following holds for some
C
=
C
(
a
)
>
0
C=C(a)>0
C
=
C
(
a
)
>
0
:For every positive integer
N
N
N
and every collection
S
S
S
of
1
×
1
×
N
1 \times 1 \times N
1
×
1
×
N
boxes in
R
3
\mathbb{R}^3
R
3
, assuming that (i)
∣
S
∣
=
N
\vert S\vert=N
∣
S
∣
=
N
, (ii) every pair of boxes
(
Δ
1
,
Δ
2
)
(\Delta_1,\Delta_2)
(
Δ
1
,
Δ
2
)
taken from
S
S
S
are not almost identical, and (iii) the long edge of each box in
S
S
S
forms an angle
π
4
\frac{\pi}{4}
4
π
against the
x
y
xy
x
y
-plane. Then the volume
∣
⋃
Δ
∈
S
Δ
∣
≥
C
N
a
.
\left\vert \bigcup_{\Delta \in S} \Delta\right\vert \ge CN^a.
Δ
∈
S
⋃
Δ
≥
C
N
a
.
9
1
Hide problems
Inequality for solution of boundary value problem
Let
ε
\varepsilon
ε
be positive constant and
u
u
u
satisfies that
{
(
∂
t
−
ε
∂
x
2
−
∂
y
2
)
u
=
0
,
(
t
,
x
,
y
)
∈
R
+
×
R
×
R
+
,
∂
y
u
∣
y
=
0
=
∂
x
h
,
u
∣
t
=
0
=
0.
\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}
⎩
⎨
⎧
(
∂
t
−
ε
∂
x
2
−
∂
y
2
)
u
=
0
,
∂
y
u
∣
y
=
0
=
∂
x
h
,
u
∣
t
=
0
=
0.
(
t
,
x
,
y
)
∈
R
+
×
R
×
R
+
,
Here
h
(
t
,
x
)
h(t,x)
h
(
t
,
x
)
is a smooth Schwartz function. Define the operator
e
a
⟨
D
⟩
e^{a\langle D\rangle}
e
a
⟨
D
⟩
\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
F
x
\mathcal{F}_x
F
x
stands for the Fourier transform in
x
x
x
. Show that
∫
0
T
∥
e
(
1
−
s
)
⟨
D
⟩
u
∥
L
x
,
y
2
2
d
s
≤
C
∫
0
T
∥
e
(
1
−
s
)
⟨
D
⟩
h
∥
H
x
1
4
2
d
s
\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
∫
0
T
∥
e
(
1
−
s
)
⟨
D
⟩
u
∥
L
x
,
y
2
2
d
s
≤
C
∫
0
T
∥
e
(
1
−
s
)
⟨
D
⟩
h
∥
H
x
4
1
2
d
s
with constant
C
C
C
independent of
ε
,
T
\varepsilon, T
ε
,
T
and
h
h
h
.
8
1
Hide problems
Bound between mean value and extremal value of holomorphic function
Let
f
(
z
)
f(z)
f
(
z
)
be a holomorphic function in
{
∣
z
∣
≤
R
}
\{\vert z\vert \le R\}
{
∣
z
∣
≤
R
}
(
0
<
R
<
∞
0<R<\infty
0
<
R
<
∞
). 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
7
1
Hide problems
Equicontinuity forces convergence in H^s-space.
A subset
Q
⊂
H
s
(
R
)
Q \subset H^s(\mathbb{R})
Q
⊂
H
s
(
R
)
is said to be equicontinuous if for any
ε
>
0
\varepsilon>0
ε
>
0
,
∃
δ
>
0
\exists \delta>0
∃
δ
>
0
such that \|f(x+h)-f(x)\|_{H^s}<\varepsilon, \forall \vert h\vert<\delta, f \in Q. Fix
r
<
s
r<s
r
<
s
, given a bounded sequence of functions
f
n
∈
H
s
(
R
f_n \in H^s(\mathbb{R}
f
n
∈
H
s
(
R
. If
f
n
f_n
f
n
converges in
H
r
(
R
)
H^r(\mathbb{R})
H
r
(
R
)
and equicontinuous in
H
s
(
R
)
H^s(\mathbb{R})
H
s
(
R
)
, show that it also converges in
H
s
(
R
)
H^s(\mathbb{R})
H
s
(
R
)
.
6
2
Hide problems
AGMC 2021 Prelim Q6
When a company releases a new social media software, the marketing development of the company researches and analyses the characteristics of the customer group apart from paying attention to the active customer depending on the change of the time. We use
n
(
t
,
x
)
n(t, x)
n
(
t
,
x
)
to express the customer density (which will be abbreviated as density). Here
t
t
t
is the time and
x
x
x
is the time of the customer spent on the social media software. In the instant time
t
t
t
, for
0
<
x
1
<
x
2
0<x_1<x_2
0
<
x
1
<
x
2
, the number of customers of spending time between
x
1
x_1
x
1
and
x
2
x_2
x
2
is
∫
x
1
x
2
n
(
t
,
x
)
d
x
\int_{x_1}^{x_2}n(t,x)dx
∫
x
1
x
2
n
(
t
,
x
)
d
x
. We assume the density
n
(
t
,
x
)
n(t,x)
n
(
t
,
x
)
depends on the time and the following factors: Assumption 1. When the customer keeps using that social media software, their time spent on social media increases linearly. Assumption 2. During the time that the customer uses the social media software, they may stop using it. We assumption the speed of stopping using it
d
(
x
)
>
0
d(x)>0
d
(
x
)
>
0
only depends on
x
x
x
. Assumption 3. There are two sources of new customer. (i) The promotion from the company: A function of time that expresses the increase of number of people in a time unit, expressed by
c
(
t
)
c(t)
c
(
t
)
. (ii) The promotion from previous customer: Previous customer actively promotes this social media software to their colleagues and friends actively. The speed of promoting sucessfully depends on
x
x
x
, denoted as
b
(
x
)
b(x)
b
(
x
)
. Assume if in an instant time, denoted as
t
=
0
t=0
t
=
0
, the density function is known and
n
(
0
,
x
)
=
n
0
(
x
)
n(0,x)=n_0(x)
n
(
0
,
x
)
=
n
0
(
x
)
. We can derive. The change of time
n
(
t
,
x
)
n(t,x)
n
(
t
,
x
)
can satisfy the equation:
{
∂
∂
t
n
(
t
,
x
)
+
∂
∂
x
n
(
t
,
x
)
+
d
(
x
)
n
(
t
,
x
)
=
0
,
t
≥
0
,
x
≥
0
N
(
t
)
:
=
n
(
t
,
x
=
0
)
=
c
(
t
)
+
∫
0
∞
b
(
y
)
n
(
t
,
y
)
d
y
\begin{cases} \frac{\partial}{\partial t}n(t,x)+\frac{\partial}{\partial x}n(t,x)+d(x)n(t,x)=0, t\ge 0, x\ge 0 \\ N(t):=n(t,x=0)=c(t)+\int_{0}^{\infty}b(y)n(t,y)dy \end{cases}\,
{
∂
t
∂
n
(
t
,
x
)
+
∂
x
∂
n
(
t
,
x
)
+
d
(
x
)
n
(
t
,
x
)
=
0
,
t
≥
0
,
x
≥
0
N
(
t
)
:=
n
(
t
,
x
=
0
)
=
c
(
t
)
+
∫
0
∞
b
(
y
)
n
(
t
,
y
)
d
y
where
N
(
t
)
N(t)
N
(
t
)
iis the speed of the increase of new customers. We assume
b
,
d
∈
L
−
∞
(
0
,
∞
)
b, d \in L^\infty_-(0, \infty)
b
,
d
∈
L
−
∞
(
0
,
∞
)
.
b
(
x
)
b(x)
b
(
x
)
and
d
(
x
)
d(x)
d
(
x
)
is bounded in essence. The following, we first make a simplified assumption:
c
(
t
)
≡
0
c(t)\equiv 0
c
(
t
)
≡
0
, i.e. the increase of new customer depends only on the promotion of previous customer. (a) According to assumption 1 and 2, formally derive the PDE that
n
(
t
,
x
)
n(t, x)
n
(
t
,
x
)
satisfies in the two simtaneous equation above. You are required to show the assumption of model and the relationship between the Maths expression. Furthermore, according to assumption 3, explain the definition and meaning of
N
(
t
)
N(t)
N
(
t
)
in the simtaneous equation above. (b) We want to research the relationship of the speed of the increase of the new customers
N
(
t
)
N(t)
N
(
t
)
and the speed of promoting sucessfully
b
(
x
)
b(x)
b
(
x
)
. Derive an equation that
N
(
t
)
N(t)
N
(
t
)
satisfies in terms of
N
(
t
)
,
n
0
(
x
)
,
b
(
x
)
,
d
(
x
)
N(t), n_0(x), b(x), d(x)
N
(
t
)
,
n
0
(
x
)
,
b
(
x
)
,
d
(
x
)
only and does not include
n
(
t
,
x
)
n(t, x)
n
(
t
,
x
)
. Prove that
N
(
t
)
N(t)
N
(
t
)
satifies the estimation
∣
N
(
t
)
∣
≤
∣
∣
b
∣
∣
∞
e
∣
∣
b
∣
∣
∞
t
∫
0
∞
∣
n
0
(
x
)
∣
d
x
|N(t)|\le ||b||_\infty e^{||b||_\infty t}\int_{0}^{\infty}|n_0(x)|dx
∣
N
(
t
)
∣
≤
∣∣
b
∣
∣
∞
e
∣∣
b
∣
∣
∞
t
∫
0
∞
∣
n
0
(
x
)
∣
d
x
, where
∣
∣
⋅
∣
∣
∞
||\cdot||_\infty
∣∣
⋅
∣
∣
∞
is the norm of
L
∞
L^\infty
L
∞
. (c) Finally, we want to research, after sufficiently long time, what trend of number density function
n
(
t
,
x
)
n(t, x)
n
(
t
,
x
)
\frac{d} has. As the total number of customers may keep increasing so it is not comfortable for us to research the number density function
n
(
t
,
x
)
n(t, x)
n
(
t
,
x
)
. We should try to find a density function which is renormalized. Hence, we first assume there is one only solution
(
λ
0
,
φ
(
x
)
)
(\lambda_0,\varphi(x))
(
λ
0
,
φ
(
x
))
of the following eigenvalue problem:
{
φ
′
(
x
)
+
(
λ
0
+
d
(
x
)
)
φ
(
x
)
=
0
,
x
≥
0
φ
(
x
)
>
0
,
φ
(
0
)
=
∫
0
∞
b
(
x
)
φ
(
x
)
d
x
=
1
\begin{cases} \varphi'(x)+(\lambda_0+d(x))\varphi(x)=0, x\ge 0 \\ \varphi(x)>0,\varphi(0)=\int_{0}^{\infty}b(x)\varphi(x)dx=1 \end{cases}\,
{
φ
′
(
x
)
+
(
λ
0
+
d
(
x
))
φ
(
x
)
=
0
,
x
≥
0
φ
(
x
)
>
0
,
φ
(
0
)
=
∫
0
∞
b
(
x
)
φ
(
x
)
d
x
=
1
and its dual problem has only solution
ψ
(
x
)
\psi(x)
ψ
(
x
)
:
{
−
φ
′
(
x
)
+
(
λ
0
+
d
(
x
)
)
ψ
(
x
)
=
ψ
(
0
)
b
(
x
)
,
x
≥
0
ψ
(
x
)
>
0
,
∫
0
∞
ψ
(
x
)
φ
(
x
)
d
x
=
1
\begin{cases} -\varphi'(x)+(\lambda_0+d(x))\psi(x)=\psi(0)b(x), x\ge 0 \\ \psi(x)>0,\int_{0}^{\infty}\psi(x)\varphi(x)dx=1 \end{cases}\,
{
−
φ
′
(
x
)
+
(
λ
0
+
d
(
x
))
ψ
(
x
)
=
ψ
(
0
)
b
(
x
)
,
x
≥
0
ψ
(
x
)
>
0
,
∫
0
∞
ψ
(
x
)
φ
(
x
)
d
x
=
1
Prove that for any convex function
H
:
R
+
→
R
+
H:\mathbb{R}^+\to \mathbb{R}^+
H
:
R
+
→
R
+
which satisfies
H
(
0
)
=
0
H(0)=0
H
(
0
)
=
0
. We have
d
d
x
∫
0
∞
ψ
(
x
)
φ
(
x
)
H
(
n
~
(
t
,
x
)
φ
(
x
)
)
d
x
≤
0
,
∀
t
≥
0
\frac{d}{dx}\int_{0}^{\infty}\psi(x)\varphi(x)H(\frac{\tilde{n}(t,x)}{\varphi(x)})dx\le 0, \forall t\ge 0
d
x
d
∫
0
∞
ψ
(
x
)
φ
(
x
)
H
(
φ
(
x
)
n
~
(
t
,
x
)
)
d
x
≤
0
,
∀
t
≥
0
. Furthermore, prove that
∫
0
∞
ψ
(
x
)
n
(
t
,
x
)
d
x
=
e
λ
0
t
∫
0
∞
ψ
(
x
)
n
0
(
x
)
d
x
\int_{0}^{\infty}\psi(x)n(t,x)dx=e^{\lambda_0t}\int_{0}^{\infty}\psi(x)n_0(x)dx
∫
0
∞
ψ
(
x
)
n
(
t
,
x
)
d
x
=
e
λ
0
t
∫
0
∞
ψ
(
x
)
n
0
(
x
)
d
x
To simplify the proof, the contribution of boundary terms in
∞
\infty
∞
is negligible.
Locally bounded function with strange integral inequality
Let
M
(
t
)
M(t)
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
C_{a,b}
C
a
,
b
, from
[
0
,
∞
)
[0,\infty)
[
0
,
∞
)
to
[
0
,
∞
)
[0,\infty)
[
0
,
∞
)
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.
5
2
Hide problems
AGMC 2021 Prelim Q5
For the complex-valued function
f
(
x
)
f(x)
f
(
x
)
which is continuous and absolutely integrable on
R
\mathbb{R}
R
, define the function
(
S
f
)
(
x
)
(Sf)(x)
(
S
f
)
(
x
)
on
R
\mathbb{R}
R
:
(
S
f
)
(
x
)
=
∫
−
∞
+
∞
e
2
π
i
u
x
f
(
u
)
d
u
(Sf)(x)=\int_{-\infty}^{+\infty}e^{2\pi iux}f(u)du
(
S
f
)
(
x
)
=
∫
−
∞
+
∞
e
2
πi
ux
f
(
u
)
d
u
. (a) Find the expression for
S
(
1
1
+
x
2
)
S(\frac{1}{1+x^2})
S
(
1
+
x
2
1
)
and
S
(
1
(
1
+
x
2
)
2
)
S(\frac{1}{(1+x^2)^2})
S
(
(
1
+
x
2
)
2
1
)
. (b) For any integer
k
k
k
, let
f
k
(
x
)
=
(
1
+
x
2
)
−
1
−
k
f_k(x)=(1+x^2)^{-1-k}
f
k
(
x
)
=
(
1
+
x
2
)
−
1
−
k
. Assume
k
≥
1
k\geq 1
k
≥
1
, find constant
c
1
c_1
c
1
,
c
2
c_2
c
2
such that the function
y
=
(
S
f
k
)
(
x
)
y=(Sf_k)(x)
y
=
(
S
f
k
)
(
x
)
satisfies the ODE with second order:
x
y
′
′
+
c
1
y
′
+
c
2
x
y
=
0
xy''+c_1y'+c_2xy=0
x
y
′′
+
c
1
y
′
+
c
2
x
y
=
0
.
Points with unit distance almost on a sphere
Suppose that
A
A
A
is a finite subset of
R
d
\mathbb{R}^d
R
d
such that(a) every three distinct points in
A
A
A
contain two points that are exactly at unit distance apart, and(b) the Euclidean norm of every point
v
v
v
in
A
A
A
satisfies
1
2
−
1
2
∣
A
∣
≤
∥
v
∥
≤
1
2
+
1
2
∣
A
∣
.
\sqrt{\frac{1}{2}-\frac{1}{2\vert A\vert}} \le \|v\| \le \sqrt{\frac{1}{2}+\frac{1}{2\vert A\vert}}.
2
1
−
2∣
A
∣
1
≤
∥
v
∥
≤
2
1
+
2∣
A
∣
1
.
Prove that the cardinality of
A
A
A
is at most
2
d
+
4
2d+4
2
d
+
4
.
4
2
Hide problems
AGMC 2021 Prelim Q4
Let
n
n
n
be a positive integer. For any positive integer
k
k
k
, let
0
k
=
d
i
a
g
{
0
,
.
.
.
,
0
⏟
k
}
0_k=diag\{\underbrace{0, ...,0}_{k}\}
0
k
=
d
ia
g
{
k
0
,
...
,
0
}
be a
k
×
k
k \times k
k
×
k
zero matrix. Let
Y
=
(
0
n
A
A
t
0
n
+
1
)
Y=\begin{pmatrix} 0_n & A \\ A^t & 0_{n+1} \end{pmatrix}
Y
=
(
0
n
A
t
A
0
n
+
1
)
be a
(
2
n
+
1
)
×
(
2
n
+
1
)
(2n+1) \times (2n+1)
(
2
n
+
1
)
×
(
2
n
+
1
)
where
A
=
(
x
i
,
j
)
1
≤
i
≤
n
,
1
≤
j
≤
n
+
1
A=(x_{i, j})_{1\leq i \leq n, 1\leq j \leq n+1}
A
=
(
x
i
,
j
)
1
≤
i
≤
n
,
1
≤
j
≤
n
+
1
is a
n
×
(
n
+
1
)
n \times (n+1)
n
×
(
n
+
1
)
real matrix. Let
A
T
A^T
A
T
be transpose matrix of
A
A
A
i.e.
(
n
+
1
)
×
n
(n+1) \times n
(
n
+
1
)
×
n
matrix, the element of
(
j
,
i
)
(j, i)
(
j
,
i
)
is
x
i
,
j
x_{i, j}
x
i
,
j
. (a) Let complex number
λ
\lambda
λ
be an eigenvalue of
k
×
k
k \times k
k
×
k
matrix
X
X
X
. If there exists nonzero column vectors
v
=
(
x
1
,
.
.
.
,
x
k
)
t
v=(x_1, ..., x_k)^t
v
=
(
x
1
,
...
,
x
k
)
t
such that
X
v
=
λ
v
Xv=\lambda v
X
v
=
λ
v
. Prove that 0 is the eigenvalue of
Y
Y
Y
and the other eigenvalues of
Y
Y
Y
can be expressed as a form of
±
λ
\pm \sqrt{\lambda}
±
λ
where nonnegative real number
λ
\lambda
λ
is the eigenvalue of
A
A
t
AA^t
A
A
t
. (b) Let
n
=
3
n=3
n
=
3
and
a
1
a_1
a
1
,
a
2
a_2
a
2
,
a
3
a_3
a
3
,
a
4
a_4
a
4
are
4
4
4
distinct positive real numbers. Let
a
=
∑
1
≤
i
≤
4
a
i
2
a=\sqrt[]{\sum_{1\leq i \leq 4}^{}a^{2}_{i}}
a
=
∑
1
≤
i
≤
4
a
i
2
and
x
i
,
j
=
a
i
δ
i
,
j
+
a
j
δ
4
,
j
−
1
a
2
(
a
i
2
+
a
4
2
)
a
j
x_{i,j}=a_i\delta_{i,j}+a_j\delta_{4,j}-\frac{1}{a^2}(a^2_{i}+a^2_{4})a_j
x
i
,
j
=
a
i
δ
i
,
j
+
a
j
δ
4
,
j
−
a
2
1
(
a
i
2
+
a
4
2
)
a
j
where
1
≤
i
≤
3
,
1
≤
j
≤
4
1\leq i \leq 3, 1\leq j \leq 4
1
≤
i
≤
3
,
1
≤
j
≤
4
,
δ
i
,
j
=
{
1
if
i
=
j
0
if
i
≠
j
\delta_{i, j}= \begin{cases} 1 \text{ if } i=j\\ 0 \text{ if } i\neq j\\ \end{cases}\,
δ
i
,
j
=
{
1
if
i
=
j
0
if
i
=
j
. Prove that
Y
Y
Y
has 7 distinct eigenvalue.
Operations on maps on random variables
Let
(
Ω
,
A
,
P
)
(\Omega, \mathcal{A},\mathbb{P})
(
Ω
,
A
,
P
)
be a standard probability space, and
X
\mathcal{X}
X
be the set of all bounded random variables. For
t
>
0
t>0
t
>
0
, defined the mapping
R
t
R_t
R
t
by R_t(X)=t\log \mathbb{E}[\exp(X/t)], X \in \mathcal{X}, and for
t
∈
(
0
,
1
)
t \in (0,1)
t
∈
(
0
,
1
)
define the mapping
Q
t
Q_t
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
:
X
→
[
−
∞
,
∞
)
f,g:\mathcal{X} \to [-\infty,\infty)
f
,
g
:
X
→
[
−
∞
,
∞
)
, 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
t,s>0
t
,
s
>
0
,
R
t
□
R
s
=
R
t
+
s
.
R_t \square R_s=R_{t+s}.
R
t
□
R
s
=
R
t
+
s
.
(b) Show that, for
t
,
s
>
0
t,s>0
t
,
s
>
0
with
t
+
s
<
1
t+s<1
t
+
s
<
1
,
Q
t
□
Q
s
=
Q
t
+
s
.
Q_t \square Q_s=Q_{t+s}.
Q
t
□
Q
s
=
Q
t
+
s
.
3
2
Hide problems
AGMC 2021 Prelim Q3
Last year, Master Cheung is famous for multi-rotation. This year, he comes to DAMO to make noodles for sweeping monk. One day, software engineer Xiao Li talks with Master Cheung about his job. Xiao Li mainly researches and designs the algorithm to adjust the paramter of different kinds of products. These paramters can normally be obtainly by minimising loss function
f
f
f
on
R
n
\mathbb{R}^n
R
n
. In the recent project of Xiao Li, this loss function is obtained by other topics. For safety consideration and technique reasons, this topic makes Xiao Li difficult to find the interal details of the function. They only provide a port to calculate the value of
f
(
x
)
f(\text x)
f
(
x
)
for any
x
∈
R
n
\text x\in\mathbb{R}^n
x
∈
R
n
. Therefore, Xiao Li must only use the value of the function to minimise
f
f
f
. Also, every times calculating the value of
f
f
f
will use a lot of calculating resources. It is good to know that the dimension
n
n
n
is not very high (around
10
10
10
). Also, colleague who provides the function tells Xiao Li to assume
f
f
f
is smooth first. This problem reminds Master Cheung of his antique radio. If you want to hear a programme from the radio, you need to turn the knob of the radio carefully. At the same time, you need to pay attention to the quality of the radio received, until the quality is the best. In this process, no one knows the relationship between the angle of turning the knob and the quality of the radio received. Master Cheung and Xiao Li realizes that minimising
f
f
f
is same as adjusting the machine with multiple knobs: Assume every weight of
x
\text x
x
is controlled by a knob.
f
(
x
)
f(\text x)
f
(
x
)
is a certain performance of the machine. We only need to adjust every knobs again and again and observes the value of
f
f
f
in the same time. Maybe there is hope to find the best
x
\text x
x
. As a result, two people suggest an iteration algorithm (named Automated Forward/Backward Tuning,
AFBT
\text{AFBT}
AFBT
, to minimise
f
f
f
. In
k
k
k
-th iteration, the algorithm adjusts the individual weight of
x
k
\text{x}_k
x
k
to
2
n
2n
2
n
points
{
x
k
±
t
k
e
i
:
i
=
1
,
.
.
.
,
n
}
\{\text x_k\pm t_k\text e^i:i=1,...,n\}
{
x
k
±
t
k
e
i
:
i
=
1
,
...
,
n
}
, where
t
k
t_k
t
k
is the step size; then, make
y
k
y_k
y
k
be the smallest one among the value of the function of thosse points. Then check if
y
k
\text y_k
y
k
sufficiently makes
f
f
f
decrease; then, take
x
k
+
1
=
y
k
\text x_{k+1}=\text y_k
x
k
+
1
=
y
k
, then make the step size doubled. Otherwise, make
x
k
+
1
=
x
k
\text x_{k+1}=\text x_k
x
k
+
1
=
x
k
and makes the step size decrease in half. In the algorithm,
e
i
\text e^i
e
i
is the
i
i
i
-th coordinate vector in
R
n
\mathbb{R}^n
R
n
. The weight of
i
i
i
-th is
1
1
1
. Others are
0
0
0
;
1
(
⋅
)
\mathbf{1}(\cdot)
1
(
⋅
)
is indicator function. If
f
(
x
k
)
−
f
(
y
k
)
f(\text x_k)-f(\text y_k)
f
(
x
k
)
−
f
(
y
k
)
is at least the square of
t
k
t_k
t
k
, then take the value of
1
(
f
(
k
)
−
f
(
y
k
)
≥
t
k
2
)
\mathbf{1}(f(\text k)-f(y_k)\ge t^2_k)
1
(
f
(
k
)
−
f
(
y
k
)
≥
t
k
2
)
as
1
1
1
. Otherwise, take it as
0
0
0
.
AFBT
\text{AFBT}
AFBT
algorithm Input
x
0
∈
R
n
\text{x}_0\in \mathbb{R}^n
x
0
∈
R
n
,
t
0
>
0
t_0>0
t
0
>
0
. For
k
=
0
,
1
,
2
,
.
.
.
k=0, 1, 2, ...
k
=
0
,
1
,
2
,
...
, perform the following loop: 1: #Calculate loss function. 2:
s
k
:
=
1
[
f
(
x
k
)
−
f
(
y
k
)
≥
t
k
2
]
s_k:=\mathbb{1}[f(\text{x}_k)-f(\text{y}_k)\ge t^2_k]
s
k
:=
1
[
f
(
x
k
)
−
f
(
y
k
)
≥
t
k
2
]
#Is it sufficiently decreasing? Yes:
s
k
=
1
s_k=1
s
k
=
1
; No:
s
k
=
0
s_k=0
s
k
=
0
. 3:
x
k
+
1
:
=
(
1
−
s
k
)
x
k
+
s
k
y
k
\text{x}_{k+1}:=(1-s_k)\text{x}_k+s_k\text{y}_k
x
k
+
1
:=
(
1
−
s
k
)
x
k
+
s
k
y
k
#Update the point of iteration. 4:
t
k
+
1
:
=
2
2
S
k
−
1
t
k
t_{k+1}:=2^{2S_k-1}t_k
t
k
+
1
:=
2
2
S
k
−
1
t
k
#Update step size.
s
k
=
1
s_k=1
s
k
=
1
: Step size doubles;
s
k
=
0
s_k=0
s
k
=
0
: Step size decreases by half.Now, we made assumption to the loss function
f
:
R
n
→
R
f:\mathbb{R}^n\to \mathbb{R}
f
:
R
n
→
R
. Assumption 1. Let
f
f
f
be a convex function. For any
x
,
y
∈
R
n
\text{x}, \text{y}\in \mathbb{R}^n
x
,
y
∈
R
n
and
α
∈
[
0
,
1
]
\alpha \in [0, 1]
α
∈
[
0
,
1
]
, we have
f
(
(
1
−
α
)
x
+
y
)
≤
(
1
−
α
)
f
(
x
)
+
α
f
(
y
)
f((1-\alpha)\text{x}+\text{y})\le (1-\alpha)f(\text{x})+\alpha f(\text{y})
f
((
1
−
α
)
x
+
y
)
≤
(
1
−
α
)
f
(
x
)
+
α
f
(
y
)
. Assumption 2.
f
f
f
is differentiable on
R
n
\mathbb{R}^n
R
n
and
∇
f
\nabla f
∇
f
is L-Lipschitz continuous on
R
n
\mathbb{R}^n
R
n
. Assumption 3. The level set of
f
f
f
is bounded. For any
λ
∈
R
\lambda\in\mathbb{R}
λ
∈
R
, set
{
x
∈
R
n
:
f
(
x
)
≤
λ
}
\{\text x\in \mathbb{R}^n:f(\text x)\le \lambda\}
{
x
∈
R
n
:
f
(
x
)
≤
λ
}
is all bounded. Based on assumption 1 and 2, we can prove that
⟨
∇
f
(
x
)
,
y
−
x
⟩
≤
f
(
y
)
−
f
(
x
)
≤
⟨
∇
f
(
x
)
,
y
−
x
⟩
+
L
2
∣
∣
x
−
y
∣
∣
2
\left\langle \nabla f(\text x),\text y-\text x \right\rangle \le f(\text y)-f(\text x)\le \left\langle \nabla f(\text x),\text y-\text x\right\rangle+\frac{L}{2}||\text x-\text y||^2
⟨
∇
f
(
x
)
,
y
−
x
⟩
≤
f
(
y
)
−
f
(
x
)
≤
⟨
∇
f
(
x
)
,
y
−
x
⟩
+
2
L
∣∣
x
−
y
∣
∣
2
You can refer to any convex analysis textbook for more properties of convex function. Prove that under the assumption 1-3, for
A
F
B
T
AFBT
A
FBT
,
lim
k
→
∞
f
(
x
k
)
=
f
∗
\lim_{k \to \infty}f(\text{x}_k)=f^*
lim
k
→
∞
f
(
x
k
)
=
f
∗
Binary matrices without certain submatrices
Given positive integers
k
≥
2
k \ge 2
k
≥
2
and
m
m
m
sufficiently large. Let
F
m
\mathcal{F}_m
F
m
be the infinite family of all the (not necessarily square) binary matrices which contain exactly
m
m
m
1's. Denote by
f
(
m
)
f(m)
f
(
m
)
the maximum integer
L
L
L
such that for every matrix
A
∈
F
m
A \in \mathcal{F}_m
A
∈
F
m
, there always exists a binary matrix
B
B
B
of the same dimension such that (1)
B
B
B
has at least
L
L
L
1-entries; (2) every entry of
B
B
B
is less or equal to the corresponding entry of
A
A
A
; (3)
B
B
B
does not contain any
k
×
k
k \times k
k
×
k
all-1 submatrix. Show the equality
lim
m
→
∞
ln
f
(
m
)
ln
m
=
k
k
+
1
.
\lim_{m \to \infty} \frac{\ln f(m)}{\ln m}=\frac{k}{k+1}.
m
→
∞
lim
ln
m
ln
f
(
m
)
=
k
+
1
k
.
2
2
Hide problems
AGMC 2021 Prelim Q2
The winners of first AGMC in 2019 gifts the person in charge of the organiser, which is a polyhedron formed by
60
60
60
congruent triangles. From the photo, we can see that this polyhedron formed by
60
60
60
quadrilateral spaces. (Note: You can find the photo in 3.4 of https://files.alicdn.com/tpsservice/18c5c7b31a7074edc58abb48175ae4c3.pdf?spm=a1zmmc.index.0.0.51c0719dNAbw3C&file=18c5c7b31a7074edc58abb48175ae4c3.pdf) A quadrilateral space is the plane figures that we fold the figures following the diagonal on a
n
n
n
sides on a plane (i.e. form an appropriate dihedral angle in where the chosen diagonal is). "Two figure spaces are congruent" means they can coincide completely by isometric transform in
R
3
\mathbb{R}^3
R
3
. A polyhedron is the bounded space region, whose boundary is formed by the common edge of finite polygon. (a) We know that
2021
=
43
×
47
2021=43\times 47
2021
=
43
×
47
. Does there exist a polyhedron, whose surface can be formed by
43
43
43
congruent
47
47
47
-gon? (b) Prove your answer in (a) with logical explanation.
Probability in a graph is independent of root
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
p
p
and operates otherwise. (All of these stochastic events are mutually independent, and
0
≤
p
≤
1
0 \le p \le 1
0
≤
p
≤
1
.) There is a root serve, denoted by
r
r
r
. We call the network operational, if all serves can reach
r
r
r
using only operating channels. Note that we do not require
r
r
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
r
r
. (In other words, for any two distinct root servers
r
1
r_1
r
1
and
r
2
r_2
r
2
, the operational probability is the same.)
1
2
Hide problems
AGMC 2021 Prelim Q1
In a virtually-made world, each citizen, which is assumed to be a point (i.e. without area) and labelled as
1
,
2
,
.
.
.
1, 2, ...
1
,
2
,
...
. To fight against a pandemic, these citizens are required to get vaccinated. After they get vaccinated, they need to be observed for a period of time. Now assume the location that the citizens get observe is a circumference with radius
1
4
\frac{1}{4}
4
1
on the plane. For the safety reason, it is required for distance between
m
m
m
-th citizen and
n
n
n
-th citizen
d
m
,
n
d_{m, n}
d
m
,
n
satisfying the following:
(
m
+
n
)
d
m
,
n
≥
1
(m+n)d_{m, n}\geq 1
(
m
+
n
)
d
m
,
n
≥
1
Here what we consider is the distance on the circumference i.e. the arc length of minor arc formed by two points. Then (a) Choose one of the following which fits the situation in reality. A. The location for observation can mostly have
8
8
8
citizens. B. The location for observation can have the upper limit on the number of citizens which is larger than
8
8
8
. C. The location for observation can have any number of citizens. (b) Prove your answer in (a).
Expected length of a dance party
In a dance party initially there are
20
20
20
girls and
22
22
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?