MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2021 Miklós Schweitzer
2021 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(10)
10
1
Hide problems
Asymptote of a conditional probability in a coin toss
Consider a coin with a head toss probability
p
p
p
where
0
<
p
<
1
0 <p <1
0
<
p
<
1
is fixed. Toss the coin several times, the tosses should be independent of each other. Denote by
A
i
A_i
A
i
the event that of the
i
i
i
-th,
(
i
+
1
)
(i + 1)
(
i
+
1
)
-th,
…
\ldots
…
, the
(
i
+
m
−
1
)
(i+m-1)
(
i
+
m
−
1
)
-th throws, exactly
T
T
T
is the tail. For
T
=
1
T = 1
T
=
1
, calculate the conditional probability
P
(
A
2
ˉ
A
3
ˉ
⋯
A
m
ˉ
∣
A
1
)
\mathbb{P}(\bar{A_2} \bar{A_3} \cdots \bar{A_m} | A_1)
P
(
A
2
ˉ
A
3
ˉ
⋯
A
m
ˉ
∣
A
1
)
, and for
T
=
2
T = 2
T
=
2
, prove that
P
(
A
2
ˉ
A
3
ˉ
⋯
A
m
ˉ
∣
A
1
)
\mathbb{P}(\bar{A_2} \bar{A_3} \cdots \bar{A_m} | A_1)
P
(
A
2
ˉ
A
3
ˉ
⋯
A
m
ˉ
∣
A
1
)
has approximation in the form
a
+
b
m
+
O
(
p
m
)
a+ \tfrac{b}{m} + \mathcal{O}(p^m)
a
+
m
b
+
O
(
p
m
)
as
m
→
∞
m \to \infty
m
→
∞
.
8
1
Hide problems
Metric connection on Riemannian manifold
Prove that for a
2
2
2
-dimensional Riemannian manifold there is a metric linear connection with zero curvature if and only if the Gaussian curvature of the Riemannian manifold can be written as the divergence of a vector field.
6
1
Hide problems
Fourier series convergent/divergent simultaneously
Let
f
f
f
and
g
g
g
be
2
π
2 \pi
2
π
-periodic integrable functions such that in some neighborhood of
0
0
0
,
g
(
x
)
=
f
(
a
x
)
g(x) = f(ax)
g
(
x
)
=
f
(
a
x
)
with some
a
≠
0
a \neq 0
a
=
0
. Prove that the Fourier series of
f
f
f
and
g
g
g
are simultaneously convergent or divergent at
0
0
0
.
1
1
Hide problems
Non-negative linear combinations cover Z^n
Let
n
,
m
∈
N
n, m \in \mathbb{N}
n
,
m
∈
N
;
a
1
,
…
,
a
m
∈
Z
n
a_1,\ldots, a_m \in \mathbb{Z}^n
a
1
,
…
,
a
m
∈
Z
n
. Show that nonnegative integer linear combinations of these vectors give exactly the whole
Z
n
\mathbb{Z}^n
Z
n
lattice, if
m
≥
n
m \ge n
m
≥
n
and the following two statements are satisfied:[*] The vectors do not fall into the half-space of
R
n
\mathbb{R}^n
R
n
containing the origin (i.e. they do not fall on the same side of an
n
−
1
n-1
n
−
1
dimensional subspace), [*] the largest common divisor (not pairwise, but together) of
n
×
n
n \times n
n
×
n
minor determinants of the matrix
(
a
1
,
…
,
a
m
)
(a_1,\ldots, a_m)
(
a
1
,
…
,
a
m
)
(which is of size
m
×
n
m \times n
m
×
n
and the
i
i
i
-th column is
a
i
a_i
a
i
as a column vector) is
1
1
1
.
7
1
Hide problems
On bounding the weighted sum over unit circle, binary XOR related
If the binary representations of the positive integers
k
k
k
and
n
n
n
are
k
=
∑
i
=
0
∞
k
i
2
i
k = \sum_{i=0}^{\infty} k_i 2^i
k
=
∑
i
=
0
∞
k
i
2
i
and
n
=
∑
i
=
0
∞
n
i
2
i
n = \sum_{i=0}^{\infty} n_i 2^i
n
=
∑
i
=
0
∞
n
i
2
i
, then the logical sum of these numbers is
k
⊕
n
=
∑
i
=
0
∞
∣
k
i
−
n
i
∣
2
i
.
k \oplus n =\sum_{i=0}^{\infty} |k_i-n_i|2^i.
k
⊕
n
=
i
=
0
∑
∞
∣
k
i
−
n
i
∣
2
i
.
Let
N
N
N
be an arbitrary positive integer and
(
c
k
)
k
∈
N
(c_k)_{k \in \mathbb{N}}
(
c
k
)
k
∈
N
be a sequence of complex numbers such that for all
k
∈
N
k \in \mathbb{N}
k
∈
N
,
∣
c
k
∣
≤
1
|c_k| \le 1
∣
c
k
∣
≤
1
. Prove that there exist positive constants
C
C
C
and
δ
\delta
δ
such that
∫
[
−
π
,
π
]
×
[
−
π
,
π
]
sup
n
<
N
,
n
∈
N
1
N
∣
∑
k
=
1
n
c
k
e
i
(
k
x
+
(
k
⊕
n
)
y
)
∣
d
(
x
,
y
)
≤
C
⋅
N
−
δ
\int_{[-\pi,\pi] \times [-\pi, \pi]} \sup_{n<N, n \in \mathbb{N}} \frac{1}{N} \Big| \sum_{k=1}^{n} c_k e^{i(kx+(k \oplus n) y)} \Big| \mathrm d(x,y) \le C \cdot N^{-\delta}
∫
[
−
π
,
π
]
×
[
−
π
,
π
]
n
<
N
,
n
∈
N
sup
N
1
k
=
1
∑
n
c
k
e
i
(
k
x
+
(
k
⊕
n
)
y
)
d
(
x
,
y
)
≤
C
⋅
N
−
δ
holds.
9
1
Hide problems
An estimate on probability of picking the same subset
For a given natural number
n
n
n
, two players randomly (uniformly distributed) select a common number
0
≤
j
≤
n
0 \le j \le n
0
≤
j
≤
n
, and then each of them independently randomly selects a subset of
{
1
,
2
,
⋯
,
n
}
\{1,2, \cdots, n \}
{
1
,
2
,
⋯
,
n
}
with
j
j
j
elements. Let
p
n
p_n
p
n
be the probability that the same set was chosen. Prove that \sum_{k=1}^{n} p_k = 2 \log{n} + 2 \gamma - 1 + o(1), (n \to \infty), where
γ
\gamma
γ
is the Euler constant.
5
1
Hide problems
Iteration of f converges almost everywhere
Let
f
(
x
)
=
1
+
cos
(
2
π
x
)
2
f(x)=\frac{1+\cos(2 \pi x)}{2}
f
(
x
)
=
2
1
+
c
o
s
(
2
π
x
)
, for
x
∈
R
x \in \mathbb{R}
x
∈
R
, and
f
n
=
f
∘
⋯
∘
f
⏟
n
f^n=\underbrace{ f \circ \cdots \circ f}_{n}
f
n
=
n
f
∘
⋯
∘
f
. Is it true that for Lebesgue almost every
x
x
x
,
lim
n
→
∞
f
n
(
x
)
=
1
\lim_{n \to \infty} f^n(x)=1
lim
n
→
∞
f
n
(
x
)
=
1
?
4
1
Hide problems
represent mean of AM and GM as weighted sum
Let
I
I
I
be a nonempty open subinterval of the set of positive real numbers. For which even
n
∈
N
n \in \mathbb{N}
n
∈
N
are there injective function
f
:
I
→
R
f: I \to \mathbb{R}
f
:
I
→
R
and positive function
p
:
I
→
R
p: I \to \mathbb{R}
p
:
I
→
R
, such that for all
x
1
,
…
,
x
n
∈
I
x_1 , \ldots , x_n \in I
x
1
,
…
,
x
n
∈
I
,
f
(
1
2
(
x
1
+
⋯
+
x
n
n
+
x
1
⋯
x
n
n
)
)
=
p
(
x
1
)
f
(
x
1
)
+
⋯
+
p
(
x
n
)
f
(
x
n
)
p
(
x
1
)
+
⋯
+
p
(
x
n
)
f \left( \frac{1}{2} \left( \frac{x_1+\cdots+x_n}{n}+\sqrt[n]{x_1 \cdots x_n} \right) \right)=\frac{p(x_1)f(x_1)+\cdots+p(x_n)f(x_n)}{p(x_1)+\cdots+p(x_n)}
f
(
2
1
(
n
x
1
+
⋯
+
x
n
+
n
x
1
⋯
x
n
)
)
=
p
(
x
1
)
+
⋯
+
p
(
x
n
)
p
(
x
1
)
f
(
x
1
)
+
⋯
+
p
(
x
n
)
f
(
x
n
)
holds?
3
1
Hide problems
Jensen-type condition implies continuous extension
Let
I
⊂
R
I \subset \mathbb{R}
I
⊂
R
be a nonempty open interval and let
f
:
I
∩
Q
→
R
f: I \cap \mathbb{Q} \to \mathbb{R}
f
:
I
∩
Q
→
R
be a function such that for all
x
,
y
∈
I
∩
Q
x, y \in I \cap \mathbb{Q}
x
,
y
∈
I
∩
Q
,
4
f
(
3
x
+
y
4
)
+
4
f
(
x
+
3
y
4
)
≤
f
(
x
)
+
6
f
(
x
+
y
2
)
+
f
(
y
)
.
4f\left(\frac{3x + y}{4}\right)+ 4f\left(\frac{x + 3y}{4}\right) \le f(x) + 6f\left(\frac{x + y}{2}\right)+ f(y).
4
f
(
4
3
x
+
y
)
+
4
f
(
4
x
+
3
y
)
≤
f
(
x
)
+
6
f
(
2
x
+
y
)
+
f
(
y
)
.
Show that
f
f
f
can be continuously extended to
I
I
I
.
2
1
Hide problems
Exponential and Factorial Diophantine Equation
Prove that the equation
2
x
+
5
y
−
3
1
z
=
n
!
2^x + 5^y - 31^z = n!
2
x
+
5
y
−
3
1
z
=
n
!
has only a finite number of non-negative integer solutions
x
,
y
,
z
,
n
x,y,z,n
x
,
y
,
z
,
n
.