MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
1997 Miklós Schweitzer
1997 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(10)
10
1
Hide problems
random walk on hypercube
Assign independent standard normally distributed random variables to the vertices of an n-dimensional cube. Say one vertex is greater than another if the assigned number is greater. Define a random walk on the vertices according to the following rules: a) the starting point is chosen from all the vertices with equal probability, b) during our journey, if we reach a vertex such that there are adjacent vertices which have higher values, we choose the next vertex with equal probability, c) if there is none, we stop. Prove that
∀
ε
>
0
∃
K
∀
n
>
1
\forall\varepsilon>0 \,\exists K\, \forall n>1
∀
ε
>
0
∃
K
∀
n
>
1
P
(
λ
>
K
log
n
)
<
ε
P(\lambda> K \log n) <\varepsilon
P
(
λ
>
K
lo
g
n
)
<
ε
where
λ
\lambda
λ
is the number of steps of the random walk.
9
1
Hide problems
riemannian manifold
Let ( M , g ) be a Riemannian manifold. Extend the metric tensor g to the set of tangents TM with the following specification: if
a
,
b
∈
T
v
T
M
(
v
∈
T
p
M
)
a,b\in T_v TM \, (v\in T_p M)
a
,
b
∈
T
v
TM
(
v
∈
T
p
M
)
, then
g
~
v
(
a
,
b
)
:
=
g
p
(
α
˙
(
0
)
,
β
˙
(
0
)
)
+
g
p
(
D
α
X
(
0
)
,
D
β
Y
(
0
)
)
\tilde g_v (a, b): = g_p (\dot {\alpha} (0), \dot {\beta} (0) ) + g_p (D _ {\alpha} X(0) , D_{\beta} Y(0) )
g
~
v
(
a
,
b
)
:=
g
p
(
α
˙
(
0
)
,
β
˙
(
0
))
+
g
p
(
D
α
X
(
0
)
,
D
β
Y
(
0
))
where
α
,
β
\alpha, \beta
α
,
β
are curves in M such that
α
(
0
)
=
β
(
0
)
=
p
\alpha(0) = \beta(0) = p
α
(
0
)
=
β
(
0
)
=
p
. X and Y are vector fields along
α
,
β
\alpha,\beta
α
,
β
respectively, with the condition
X
˙
(
0
)
=
a
,
Y
˙
(
0
)
=
b
\dot X (0) = a,\dot Y(0) = b
X
˙
(
0
)
=
a
,
Y
˙
(
0
)
=
b
.
D
α
D _{\alpha}
D
α
and
D
β
D _{\beta}
D
β
are the operators of the covariant derivative along the corresponding curves according to the Levi-Civita connection. Is the eigenfunction from the Riemannian manifold (M,g) to the Riemannian manifold
(
T
M
,
g
~
)
(TM, \tilde g)
(
TM
,
g
~
)
harmonic?
5
1
Hide problems
area of disjoint circles in a square
Let
a
1
>
a
2
>
a
3
>
⋯
a_1>a_2>a_3>\cdots
a
1
>
a
2
>
a
3
>
⋯
be a sequence of real numbers which converges to 0. We put circles of radius
a
1
a_1
a
1
into a unit square until no more can fit. (A previously laid circle must not be moved.) Then we put circles of radius
a
2
a_2
a
2
in the remaining space until no more can fit, continuing the process for
a
3
a_3
a
3
,... What can the area covered by the circles be?a similar problem involving circles in a square: https://artofproblemsolving.com/community/c7h1979044
8
1
Hide problems
analysis
Let H be an infinite dimensional, separable, complex Hilbert space and denote
B
(
H
)
\cal B (\cal H)
B
(
H
)
the
H
\cal H
H
-algebra of its bounded linear operators. Consider the algebras
l
∞
(
N
,
B
(
H
)
)
=
l_{\infty} ({\Bbb N}, \cal B (\cal H) ) =
l
∞
(
N
,
B
(
H
))
=
{
(
a
n
)
∣
A
n
∈
B
(
H
)
\{ (a_n) | A_n \in\cal B (\cal H)
{(
a
n
)
∣
A
n
∈
B
(
H
)
(
n
∈
N
)
,
sup
n
∣
∣
A
n
∣
∣
<
∞
}
(n \in {\Bbb N}), \sup_n ||A_n|| <\infty \}
(
n
∈
N
)
,
sup
n
∣∣
A
n
∣∣
<
∞
}
C
(
β
N
,
B
(
H
)
)
C(\beta {\Bbb N}, \cal B (\cal H) )
C
(
β
N
,
B
(
H
))
=
{
f
:
β
N
→
B
(
H
)
∣
\{ f: \beta {\Bbb N} \to \cal B (\cal H)|
{
f
:
β
N
→
B
(
H
)
∣
f is continuous
}
\}
}
with pointwise operations and supremum norm. Show that these C*-algebras are not isometrically isomorphic. (Here,
β
N
\beta {\Bbb N}
β
N
denotes the Stone-Cech compactification of the set of natural numbers.)
7
1
Hide problems
function decomposition
Let G be an abelian group,
0
≤
ε
<
1
0\leq\varepsilon<1
0
≤
ε
<
1
and
f
:
G
→
R
n
f : G\to\Bbb R^n
f
:
G
→
R
n
a function that satisfies the inequality.
∣
∣
f
(
x
+
y
)
−
f
(
x
)
−
f
(
y
)
∣
∣
≤
ε
∣
∣
f
(
y
)
∣
∣
(
x
,
y
)
∈
G
2
||f(x+y)-f(x)-f(y)|| \leq \varepsilon ||f (y)|| \qquad (x, y)\in G^2
∣∣
f
(
x
+
y
)
−
f
(
x
)
−
f
(
y
)
∣∣
≤
ε
∣∣
f
(
y
)
∣∣
(
x
,
y
)
∈
G
2
Prove that there is an additive function
A
:
G
→
R
n
A : G\to \Bbb R^n
A
:
G
→
R
n
and a continuous function
φ
:
A
(
G
)
→
R
n
\varphi : A (G) \to\Bbb R^n
φ
:
A
(
G
)
→
R
n
such that
f
=
φ
∘
A
f = \varphi\circ A
f
=
φ
∘
A
.
6
1
Hide problems
infinite family of functions
Let
κ
\kappa
κ
be an infinite cardinality and let A , B be sets of cardinality
κ
\kappa
κ
. Construct a family
F
\cal F
F
of functions
f
:
A
→
B
f : A \to B
f
:
A
→
B
with cardinality
2
κ
2^\kappa
2
κ
such that for all functions
f
1
,
⋯
,
f
n
∈
F
f_1,\cdots, f_n \in\cal F
f
1
,
⋯
,
f
n
∈
F
and for all
b
1
,
.
.
.
,
b
n
∈
B
b_1 , ..., b_n \in B
b
1
,
...
,
b
n
∈
B
, there exist
a
∈
A
a\in A
a
∈
A
such that
f
1
(
a
)
=
b
1
,
⋯
,
f
n
(
a
)
=
b
n
f_1(a) = b_1,\cdots, f_n(a) = b_n
f
1
(
a
)
=
b
1
,
⋯
,
f
n
(
a
)
=
b
n
.
3
1
Hide problems
polynomial
Denote
f
n
(
X
)
∈
Z
[
X
]
f_n(X) \in \Bbb Z [X]
f
n
(
X
)
∈
Z
[
X
]
the polynomial
Π
j
=
1
n
(
X
+
j
−
1
)
\Pi_{j=1}^n ( X + j -1)
Π
j
=
1
n
(
X
+
j
−
1
)
. Show that if the numbers
α
\alpha
α
and
β
\beta
β
satisfy
f
1997
′
(
α
)
=
f
1999
′
(
β
)
=
0
f'_{1997} (\alpha) = f'_{1999} (\beta) = 0
f
1997
′
(
α
)
=
f
1999
′
(
β
)
=
0
, then
f
1997
(
α
)
≠
f
1999
(
β
)
f_{1997} (\alpha ) \neq f_{1999} (\beta)
f
1997
(
α
)
=
f
1999
(
β
)
.
4
1
Hide problems
binary matrix
An elementary change in a 0-1 matrix is a change in an element and with it all its horizontal, vertical, and diagonal neighbors (0 to 1 or 1 to 0). Can any 1791 x 1791 0-1 matrix be transformed into a zero matrix with elementary changes?
2
1
Hide problems
divergent series
Let A = {1,4,6, ...} be a set of natural numbers n for which n is the product of an even number of primes and n+1 is the product of an odd number of primes (taking into account the multiplicity of prime powers). Prove that the series of the reciprocals of the elements of A is divergent. In other words,
A
=
{
n
∣
λ
(
n
)
=
1
A=\{n|\lambda(n)=1
A
=
{
n
∣
λ
(
n
)
=
1
and
λ
(
n
+
1
)
=
−
1
}
\lambda(n+1)=-1\}
λ
(
n
+
1
)
=
−
1
}
, where
λ
\lambda
λ
is the liouville lambda function.
1
1
Hide problems
edge and endpoints same color
Define a class of graphs
G
k
G_k
G
k
for each positive integer k as follows. A graph G = ( V , E ) is an element of
G
k
G_k
G
k
if and only if there exists an edge coloring
ψ
:
E
→
[
k
]
=
{
1
,
2
,
.
.
.
,
k
}
\psi: E\to [ k ] = \{1,2, ..., k\}
ψ
:
E
→
[
k
]
=
{
1
,
2
,
...
,
k
}
such that for all vertex coloring
ϕ
:
V
→
[
k
]
\phi: V\to [ k ]
ϕ
:
V
→
[
k
]
there exist an edge e = { x , y } such that
ϕ
(
x
)
=
ϕ
(
y
)
=
ψ
(
e
)
\phi ( x ) = \phi( y ) = \psi( e )
ϕ
(
x
)
=
ϕ
(
y
)
=
ψ
(
e
)
. Prove that there exist
c
1
<
c
2
c_1< c_2
c
1
<
c
2
positive constants with the following two properties: (i) each graph in
G
k
G_k
G
k
has at least
c
1
k
2
c_1 k^2
c
1
k
2
vertices; (ii) there is a graph in
G
k
G_k
G
k
which has at most
c
2
k
2
c_2 k^2
c
2
k
2
vertices.