MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2011 Miklós Schweitzer
2011 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(10)
10
1
Hide problems
sequence of random variables
Let
X
0
,
ξ
i
,
j
,
ϵ
k
X_0, \xi_{i, j}, \epsilon_k
X
0
,
ξ
i
,
j
,
ϵ
k
(i, j, k ∈ N) be independent, non-negative integer random variables. Suppose that
ξ
i
,
j
\xi_{i, j}
ξ
i
,
j
(i, j ∈ N) have the same distribution,
ϵ
k
\epsilon_k
ϵ
k
(k ∈ N) also have the same distribution.
E
(
ξ
1
,
1
)
=
1
\mathbb{E}(\xi_{1,1})=1
E
(
ξ
1
,
1
)
=
1
,
E
(
X
0
l
)
<
∞
\mathbb{E}(X_0^l)<\infty
E
(
X
0
l
)
<
∞
,
E
(
ξ
1
,
1
l
)
<
∞
\mathbb{E}(\xi_{1,1}^l)<\infty
E
(
ξ
1
,
1
l
)
<
∞
,
E
(
ϵ
1
l
)
<
∞
\mathbb{E}(\epsilon_1^l)<\infty
E
(
ϵ
1
l
)
<
∞
for some
l
∈
N
l\in\mathbb{N}
l
∈
N
Consider the random variable
X
n
:
=
ϵ
n
+
∑
j
=
1
X
n
−
1
ξ
n
,
j
X_n := \epsilon_n + \sum_{j=1}^{X_{n-1}} \xi_{n,j}
X
n
:=
ϵ
n
+
∑
j
=
1
X
n
−
1
ξ
n
,
j
(n ∈ N) , where
∑
j
=
1
0
ξ
n
,
j
:
=
0
\sum_{j=1}^0 \xi_{n,j} :=0
∑
j
=
1
0
ξ
n
,
j
:=
0
Introduce the sequence
M
n
:
=
X
n
−
X
n
−
1
−
E
(
ϵ
n
)
M_n := X_n-X_{n-1}-\mathbb{E}(\epsilon_n)
M
n
:=
X
n
−
X
n
−
1
−
E
(
ϵ
n
)
(n ∈ N) Prove that there is a polynomial P of degree
≤
l
/
2
\leq l/2
≤
l
/2
such that
E
(
M
n
l
)
=
P
l
(
n
)
\mathbb{E}(M_n^l) = P_l(n)
E
(
M
n
l
)
=
P
l
(
n
)
(n ∈ N).
5
1
Hide problems
linear algebra
Let n, k be positive integers. Let
f
a
(
x
)
:
=
∣
∣
x
−
a
∣
∣
2
n
f_a(x) := ||x - a||^{2n}
f
a
(
x
)
:=
∣∣
x
−
a
∣
∣
2
n
, where the vectors
x
=
(
x
1
,
.
.
.
,
x
k
)
,
a
∈
R
k
x = (x_1, ..., x_k) , a\in R^k
x
=
(
x
1
,
...
,
x
k
)
,
a
∈
R
k
, and ||·|| is the Euclidean norm. Let the vector space
Q
n
,
k
Q_{n, k}
Q
n
,
k
be generated by the functions
f
a
f_a
f
a
(
a
∈
R
k
a\in R^k
a
∈
R
k
). What is the largest integer N for which
Q
n
,
k
Q_{n, k}
Q
n
,
k
contains all polynomials of
x
1
,
.
.
.
,
x
k
x_1, ..., x_k
x
1
,
...
,
x
k
whose total degree is at most N?
1
1
Hide problems
borel sets
Let
F
1
,
F
2
,
.
.
.
F_1, F_2, ...
F
1
,
F
2
,
...
be Borel-measurable sets on the plane whose union is the whole plane. Prove that there is a natural number n and circle S for which the set
S
∩
F
n
S \cap F_n
S
∩
F
n
is dense in S. Also show that the statement is not necessarily true if we omit the condition for the measurability of sets
F
j
F_j
F
j
.
8
1
Hide problems
real analysis
Given a nonzero real number
a
≤
1
/
e
a\leq 1/e
a
≤
1/
e
, let
z
1
,
.
.
.
,
z
n
∈
C
z_1, ..., z_n \in C
z
1
,
...
,
z
n
∈
C
be non-real numbers for which
z
e
z
+
a
=
0
ze^z + a = 0
z
e
z
+
a
=
0
holds, and let
c
1
,
.
.
.
,
c
n
∈
C
c_1, ..., c_n \in C
c
1
,
...
,
c
n
∈
C
be arbitrary. Show that the function
f
(
x
)
=
R
e
(
∑
j
=
1
n
c
j
e
z
j
x
)
f(x)=Re(\sum_{j=1}^n c_j e^{z_j x})
f
(
x
)
=
R
e
(
∑
j
=
1
n
c
j
e
z
j
x
)
(
x
∈
R
x \in R
x
∈
R
) has a zero in every closed interval of length 1.
9
1
Hide problems
differential equation
Let
x
:
[
0
,
∞
)
→
R
x: [0, \infty) \to\Bbb R
x
:
[
0
,
∞
)
→
R
be a differentiable function. Prove that if for all t>1
x
′
(
t
)
=
−
x
3
(
t
)
+
t
−
1
t
x
3
(
t
−
1
)
x'(t)=-x^3(t)+\frac{t-1}{t}x^3(t-1)
x
′
(
t
)
=
−
x
3
(
t
)
+
t
t
−
1
x
3
(
t
−
1
)
then
lim
t
→
∞
x
(
t
)
=
0
\lim_{t\to\infty} x(t) = 0
lim
t
→
∞
x
(
t
)
=
0
7
1
Hide problems
sequence
prove that for any sequence of nonnegative numbers
(
a
n
)
(a_n)
(
a
n
)
,
lim inf
n
→
∞
(
n
2
(
4
a
n
(
1
−
a
n
−
1
)
−
1
)
)
≤
1
4
\liminf_{n\to\infty} (n^2(4a_n(1-a_{n-1})-1))\leq\frac{1}{4}
n
→
∞
lim
inf
(
n
2
(
4
a
n
(
1
−
a
n
−
1
)
−
1
))
≤
4
1
6
1
Hide problems
convex sets in euclidean space
Let
C
1
,
.
.
.
,
C
d
C_1, ..., C_d
C
1
,
...
,
C
d
be compact and connected sets in
R
d
R^d
R
d
, and suppose that each convex hull of
C
i
C_i
C
i
contains the origin. Prove that for every i there is a
c
i
∈
C
i
c_i \in C_i
c
i
∈
C
i
for which the origin is contained in the convex hull of the points
c
1
,
.
.
.
,
c
d
c_1, ..., c_d
c
1
,
...
,
c
d
.
4
1
Hide problems
surjective homomorphisms
Let G, H be two finite groups, and let
φ
,
ψ
:
G
→
H
\varphi, \psi: G \to H
φ
,
ψ
:
G
→
H
be two surjective but non-injective homomorphisms. Prove that there exists an element of G that is not the identity element of G but whose images under
φ
\varphi
φ
and
ψ
\psi
ψ
are the same.
3
1
Hide problems
hyperplane covering
In
R
d
R^d
R
d
, all
n
d
n^d
n
d
points of an n × n × ··· × n cube grid are contained in 2n - 3 hyperplanes. Prove that n (
n
≥
3
n\geq3
n
≥
3
) hyperplanes can be chosen from these so that they contain all points of the grid.
2
1
Hide problems
monochromatic connected subgraph
Suppose that the minimum degree δ(G) of a simple graph G with n vertices is at least 3n / 4. Prove that in any 2-coloring of the edges of G , there is a connected subgraph with at least δ(G) +1 points, all edges of which are of the same color.