MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2005 Miklós Schweitzer
2005 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(12)
6
1
Hide problems
eigenvalue inequality
S
U
2
(
C
)
=
{
(
z
w
−
w
ˉ
z
ˉ
)
:
z
,
w
∈
C
,
z
z
ˉ
+
w
w
ˉ
=
1
}
SU_2(\mathbb{C})=\left\{\begin{pmatrix} z & w \\ -\bar{w} & \bar{z} \end{pmatrix} : z,w\in\mathbb{C} , z\bar{z}+w\bar{w}=1\right\}
S
U
2
(
C
)
=
{
(
z
−
w
ˉ
w
z
ˉ
)
:
z
,
w
∈
C
,
z
z
ˉ
+
w
w
ˉ
=
1
}
A and B are 2 elements of the above matrix group and have eigenvalues
e
i
θ
1
e^{i\theta_1}
e
i
θ
1
,
e
−
i
θ
1
e^{-i\theta_1}
e
−
i
θ
1
and
e
i
θ
2
e^{i\theta_2}
e
i
θ
2
,
e
−
i
θ
2
e^{-i\theta_2}
e
−
i
θ
2
respectively, where
0
≤
θ
i
≤
π
0\leq\theta_i\leq\pi
0
≤
θ
i
≤
π
. Prove that if AB has eigenvalue
e
i
θ
3
e^{i\theta_3}
e
i
θ
3
, then
θ
3
\theta_3
θ
3
satisfies the inequality
∣
θ
1
−
θ
2
∣
≤
θ
3
≤
min
{
θ
1
+
θ
2
,
2
π
−
(
θ
1
+
θ
2
)
}
|\theta_1-\theta_2|\leq\theta_3\leq \min\{\theta_1+\theta_2 , 2\pi-(\theta_1+\theta_2)\}
∣
θ
1
−
θ
2
∣
≤
θ
3
≤
min
{
θ
1
+
θ
2
,
2
π
−
(
θ
1
+
θ
2
)}
7
1
Hide problems
symmetric, biadditive function
Let
t
∈
R
t\in R
t
∈
R
. Prove that
∃
A
:
R
×
R
→
R
\exists A:R \times R \to R
∃
A
:
R
×
R
→
R
such that A is a symmetric, biadditive, nonzero function and
A
(
t
x
,
x
)
=
0
∀
x
∈
R
A(tx,x)=0 \,\forall x\in R
A
(
t
x
,
x
)
=
0
∀
x
∈
R
iff t is transcendental or (t is algebraic and t,-t are conjugates over
Q
\mathbb{Q}
Q
).
12
1
Hide problems
probability inequalities
Let
x
1
,
x
2
,
⋯
,
x
n
x_1,x_2,\cdots,x_n
x
1
,
x
2
,
⋯
,
x
n
be iid rv.
S
n
=
∑
x
k
S_n=\sum x_k
S
n
=
∑
x
k
(a) let
P
(
∣
x
1
∣
≤
1
)
=
1
P(|x_1|\leq 1)=1
P
(
∣
x
1
∣
≤
1
)
=
1
,
E
[
x
1
]
=
0
E[x_1]=0
E
[
x
1
]
=
0
,
E
[
x
1
2
]
=
σ
2
>
0
E[x_1^2]=\sigma^2>0
E
[
x
1
2
]
=
σ
2
>
0
Prove that
∃
C
>
0
\exists C>0
∃
C
>
0
,
∀
u
≥
2
n
σ
2
\forall u\geq 2n\sigma^2
∀
u
≥
2
n
σ
2
P
(
S
n
≥
u
)
≤
e
−
C
u
log
(
u
/
n
σ
2
)
P(S_n\geq u)\leq e^{-C u \log(u/n\sigma^2)}
P
(
S
n
≥
u
)
≤
e
−
C
u
l
o
g
(
u
/
n
σ
2
)
(b) let
P
(
x
1
=
1
)
=
P
(
x
1
=
−
1
)
=
σ
2
/
2
P(x_1=1)=P(x_1=-1)=\sigma^2/2
P
(
x
1
=
1
)
=
P
(
x
1
=
−
1
)
=
σ
2
/2
,
P
(
x
1
=
0
)
=
1
−
σ
2
P(x_1=0)=1-\sigma^2
P
(
x
1
=
0
)
=
1
−
σ
2
Prove that
∃
B
1
<
1
,
B
2
>
1
,
B
3
>
0
\exists B_1<1,B_2>1,B_3>0
∃
B
1
<
1
,
B
2
>
1
,
B
3
>
0
,
∀
u
≥
1
,
B
1
n
≥
u
≥
B
2
n
σ
2
\forall u\geq1, B_1 n\geq u\geq B_2 n\sigma^2
∀
u
≥
1
,
B
1
n
≥
u
≥
B
2
n
σ
2
P
(
S
n
≥
u
)
>
e
−
B
3
u
log
(
u
/
n
σ
2
)
P(S_n\geq u)>e^{-B_3 u \log(u/n\sigma^2)}
P
(
S
n
≥
u
)
>
e
−
B
3
u
l
o
g
(
u
/
n
σ
2
)
11
1
Hide problems
bilinear form
Let
E
:
R
n
\
{
0
}
→
R
+
E: R^n \backslash \{0\} \to R^+
E
:
R
n
\
{
0
}
→
R
+
be a infinitely differentiable, quadratic positive homogeneous (that is, for any λ>0 and
p
∈
R
n
\
{
0
}
p \in R^n \backslash \{0\}
p
∈
R
n
\
{
0
}
,
E
(
λ
p
)
=
λ
2
E
(
p
)
E (\lambda p) = \lambda^2 E (p)
E
(
λ
p
)
=
λ
2
E
(
p
)
). Prove that if the second derivative of
E
′
′
(
p
)
:
R
n
×
R
n
→
R
E''(p): R^n \times R^n \to R
E
′′
(
p
)
:
R
n
×
R
n
→
R
is a non-degenerate bilinear form at any point
p
∈
R
n
\
{
0
}
p \in R^n \backslash \{0\}
p
∈
R
n
\
{
0
}
, then
E
′
′
(
p
)
E''(p)
E
′′
(
p
)
(
p
∈
R
n
\
{
0
}
p \in R^n \backslash \{0\}
p
∈
R
n
\
{
0
}
) is positive definite.
9
1
Hide problems
rational function
prove that if
r
n
r_n
r
n
is a rational function whose numerator and denominator have at most degrees
n
n
n
, then
∣
∣
r
n
∣
∣
1
/
2
+
∥
1
r
n
∥
2
≥
1
2
n
−
1
||r_n||_{1/2}+\left\|\frac{1}{r_n}\right\|_2\geq\frac{1}{2^{n-1}}
∣∣
r
n
∣
∣
1/2
+
r
n
1
2
≥
2
n
−
1
1
where
∣
∣
⋅
∣
∣
a
||\cdot||_a
∣∣
⋅
∣
∣
a
denotes the supremum over a circle of radius
a
a
a
around the origin.
8
1
Hide problems
functional equation
Determine all continuous, strictly monotone functions
ϕ
:
R
+
→
R
\phi : \mathbb{R}^+\to\mathbb{R}
ϕ
:
R
+
→
R
such that
F
(
x
,
y
)
=
ϕ
−
1
(
x
ϕ
(
x
)
+
y
ϕ
(
y
)
x
+
y
)
+
ϕ
−
1
(
y
ϕ
(
x
)
+
x
ϕ
(
y
)
x
+
y
)
F(x,y)=\phi^{-1} \left(\frac{x\phi(x)+y\phi(y)}{x+y}\right) + \phi^{-1} \left(\frac{y\phi(x)+x\phi(y)}{x+y}\right)
F
(
x
,
y
)
=
ϕ
−
1
(
x
+
y
x
ϕ
(
x
)
+
y
ϕ
(
y
)
)
+
ϕ
−
1
(
x
+
y
y
ϕ
(
x
)
+
x
ϕ
(
y
)
)
is homogeneous of degree 1, ie
F
(
t
x
,
t
y
)
=
t
F
(
x
,
y
)
,
∀
x
,
y
,
t
∈
R
+
F(tx,ty)=tF(x,y) , \forall x,y,t\in\mathbb{R}^+
F
(
t
x
,
t
y
)
=
tF
(
x
,
y
)
,
∀
x
,
y
,
t
∈
R
+
F(x,y)=F(y,x) and F(x,x)=2x
5
1
Hide problems
non-archimedean field
Let
G
L
(
n
,
K
)
GL(n, K)
G
L
(
n
,
K
)
be a linear group over the field K with a topology induced by a non-Archimedean absolute value of the field K. Prove that if the matrix
M
∈
G
L
(
n
,
K
)
M \in GL (n, K)
M
∈
G
L
(
n
,
K
)
is contained by some compact subgroup of
G
L
(
n
,
K
)
GL(n, K)
G
L
(
n
,
K
)
, then all eigenvalues of M have absolute value 1.
10
1
Hide problems
5 vectors in 3d space
Given 5 nonzero vectors in three-dimensional Euclidean space, prove that the sum of their pairwise angles is at most
6
π
6\pi
6
π
.
4
1
Hide problems
countable free group
Let F be a countable free group and let
F
=
H
1
>
H
2
>
H
3
>
⋯
F = H_1> H_2> H_3> \cdots
F
=
H
1
>
H
2
>
H
3
>
⋯
be a descending chain of finite index subgroups of group F. Suppose that
∩
H
i
\cap H_i
∩
H
i
does not contain any nontrivial normal subgroups of F. Prove that there exist
g
i
∈
F
g_i\in F
g
i
∈
F
for which the conjugated subgroups
H
i
g
i
H_i^{g_i}
H
i
g
i
also form a chain, and
∩
H
i
g
i
=
{
1
}
\cap H_i^{g_i}=\{1\}
∩
H
i
g
i
=
{
1
}
.Nielsen-Schreier Theorem might be useful.
1
1
Hide problems
graph theory
Let [n] be the set {1, 2,. . . , n}.For any
a
,
b
∈
N
a, b \in N
a
,
b
∈
N
, denote
G
(
a
,
b
)
G (a, b)
G
(
a
,
b
)
by a graph (not directed) defined by the following rule: the vertices have the form (i, f), where
i
∈
[
a
]
i \in [a]
i
∈
[
a
]
, and
f
:
[
a
]
→
f: [a] \to
f
:
[
a
]
→
. A vertex (i, f) and a vertex (j, g) are connected if
i
≠
j
i \neq j
i
=
j
, and
f
(
k
)
≠
g
(
k
)
f (k) \neq g (k)
f
(
k
)
=
g
(
k
)
holds exactly for k strictly between i and j. Prove that for any
c
∈
N
c \in N
c
∈
N
there is
a
,
b
∈
N
a, b \in N
a
,
b
∈
N
such that the vertices of G (a, b) cannot be well-colored with
c
c
c
colors.
3
1
Hide problems
diophantine eqn
Let
α
≤
22
\alpha\leq 22
α
≤
22
be non-negative integer. For which
α
\alpha
α
does the equation
8
x
23
−
5
α
y
23
=
1
8x^{23}-5^{\alpha}y^{23}=1
8
x
23
−
5
α
y
23
=
1
have the most integer solutions (x,y)? What can we say about
α
≥
23
\alpha\geq 23
α
≥
23
?I believe the eqn has solutions only when
α
=
0
\alpha=0
α
=
0
. taking modulo 47,
α
≡
9
,
17
(
m
o
d
23
)
\alpha\equiv 9,17\pmod{23}
α
≡
9
,
17
(
mod
23
)
or (
23
∣
α
23|\alpha
23∣
α
and
47
∣
x
47|x
47∣
x
). taking modulo 139 and 277 eliminates the
α
≡
9
,
17
(
m
o
d
23
)
\alpha\equiv 9,17\pmod{23}
α
≡
9
,
17
(
mod
23
)
cases. 139=23*6+1 , 277=23*12+1
2
1
Hide problems
Periodic sequence Related to Golden Ratio
Let
(
a
n
)
n
≥
1
(a_{n})_{n \ge 1}
(
a
n
)
n
≥
1
be a sequence of integers satisfying the inequality
0
≤
a
n
−
1
+
1
−
5
2
a
n
+
a
n
+
1
<
1
0\le a_{n-1}+\frac{1-\sqrt{5}}{2}a_{n}+a_{n+1} <1
0
≤
a
n
−
1
+
2
1
−
5
a
n
+
a
n
+
1
<
1
for all
n
≥
2
n \ge 2
n
≥
2
. Prove that the sequence
(
a
n
)
(a_{n})
(
a
n
)
is periodic.Any Hints or Sols for this hard problem?? :help: