MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2018 Miklós Schweitzer
2018 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(11)
11
1
Hide problems
Parallelizable manifolds
We call an
m
m
m
-dimensional smooth manifold parallelizable if it admits
m
m
m
smooth tangent vector fields that are linearly independent at all points. Show that if
M
M
M
is a closed orientable
2
n
2n
2
n
-dimensional smooth manifold of Euler characteristic
0
0
0
that has an immersion into a parallelizable smooth
(
2
n
+
1
)
(2n+1)
(
2
n
+
1
)
-dimensional manifold
N
N
N
, then
M
M
M
is itself parallelizable.
10
1
Hide problems
Covering common points
In 3-dimensional hyperbolic space, we are given a plane
P
P
P
and four distinct straight lines: the lines
a
1
a_1
a
1
and
a
2
a_2
a
2
are perpendicular to
P
P
P
; while the lines
r
1
r_1
r
1
and
r
2
r_2
r
2
do not intersect
P
P
P
, and their distances from
P
P
P
are equal. Denote by
S
i
S_i
S
i
the surface of revolution obtained by rotating
r
i
r_i
r
i
around
a
i
a_i
a
i
. Show that the common points of
S
1
S_1
S
1
and
S
2
S_2
S
2
can be covered by two planes.
9
1
Hide problems
Sequence of derivatives converges pointwise
Let
f
:
C
→
C
f:\mathbb{C} \to \mathbb{C}
f
:
C
→
C
be an entire function, and suppose that the sequence
f
(
n
)
f^{(n)}
f
(
n
)
of derivatives converges pointwise. Prove that
f
(
n
)
(
z
)
→
C
e
z
f^{(n)}(z)\to Ce^z
f
(
n
)
(
z
)
→
C
e
z
pointwise for a suitable complex number
C
C
C
.
8
1
Hide problems
Does there exist a function
Does there exist a piecewise linear, continuous, surjective mapping
f
:
[
0
,
1
]
→
[
0
,
1
]
f: [0,1]\to [0,1]
f
:
[
0
,
1
]
→
[
0
,
1
]
such that
f
(
0
)
=
f
(
1
)
=
0
f(0)=f(1)=0
f
(
0
)
=
f
(
1
)
=
0
, and for all positive integer
n
n
n
,
2.000
1
(
n
−
10
)
<
P
n
(
f
)
<
2.999
9
(
n
+
10
)
2.0001^{(n-10)} <P_n(f)<2.9999^{(n+10)}
2.000
1
(
n
−
10
)
<
P
n
(
f
)
<
2.999
9
(
n
+
10
)
holds, where
P
n
(
f
)
P_n(f)
P
n
(
f
)
is the number of points
x
x
x
such that
f
(
…
f
⏟
n
(
x
)
…
)
=
x
\underbrace{f(\dotsc f}_n(x)\dotsc )=x
n
f
(
…
f
(
x
)
…
)
=
x
?
7
1
Hide problems
Binary function from {0,1}^n
Describe all functions
f
:
{
0
,
1
}
n
→
{
0
,
1
}
f: \{ 0,1\}^n \to \{ 0,1\}
f
:
{
0
,
1
}
n
→
{
0
,
1
}
which satisfy the equation \begin{align*} & f(f(a_{11},a_{12},\dotsc ,a_{1n}),f(a_{21},a_{22},\dotsc ,a_{2n}),\dotsc ,f(a_{n1},a_{n2},\dotsc ,a_{nn}))\\ & = f(f(a_{11},a_{21},\dotsc ,a_{n1}),f(a_{12},a_{22},\dotsc ,a_{n2}),\dotsc ,f(a_{1n},a_{2n},\dotsc ,a_{nn}))\end{align*} for arbitrary
a
i
j
∈
{
0
,
1
}
a_{ij}\in \{ 0,1\}
a
ij
∈
{
0
,
1
}
where
i
,
j
∈
{
1
,
2
,
…
,
n
}
.
i,j\in \{1,2,\dotsc ,n\}.
i
,
j
∈
{
1
,
2
,
…
,
n
}
.
6
1
Hide problems
Modulo 13
Prove that if
a
a
a
is an integer and
d
d
d
is a positive divisor of the number
a
4
+
a
3
+
2
a
2
−
4
a
+
3
a^4+a^3+2a^2-4a+3
a
4
+
a
3
+
2
a
2
−
4
a
+
3
, then
d
d
d
is a fourth power modulo
13
13
13
.
5
1
Hide problems
Sum of highest prime power divisors
For every positive integer
n
n
n
, define
f
(
n
)
=
∑
p
∣
n
p
k
p
,
f(n)=\sum_{p\mid n}{p^{k_p}},
f
(
n
)
=
p
∣
n
∑
p
k
p
,
where the sum is taken over all positive prime divisors
p
p
p
of
n
n
n
, and
k
p
k_p
k
p
is the unique integer satisfying
p
k
p
⩽
n
<
p
k
p
+
1
.
p^{k_p}\leqslant n<p^{k_p+1}.
p
k
p
⩽
n
<
p
k
p
+
1
.
Find
lim sup
n
→
∞
f
(
n
)
log
log
n
n
log
n
.
\limsup_{n\to \infty} \frac{f(n)\log \log n}{n\log n} .
n
→
∞
lim
sup
n
lo
g
n
f
(
n
)
lo
g
lo
g
n
.
4
1
Hide problems
Three-colorable set
Let
P
P
P
be a finite set of points in the plane. Assume that the distance between any two points is an integer. Prove that
P
P
P
can be colored by three colors such that the distance between any two points of the same color is an even number.
3
1
Hide problems
Well groomed matrix
We call an
n
×
n
n\times n
n
×
n
matrix well groomed if it only contains elements
0
0
0
and
1
1
1
, and it does not contain the submatrix
(
1
0
0
1
)
.
\begin{pmatrix} 1& 0\\ 0 & 1 \end{pmatrix}.
(
1
0
0
1
)
.
Show that there exists a constant
c
>
0
c>0
c
>
0
such that every well groomed,
n
×
n
n\times n
n
×
n
matrix contains a submatrix of size at least
c
n
×
c
n
cn\times cn
c
n
×
c
n
such that all of the elements of the submatrix are equal. (A well groomed matrix may contain the submatrix
(
0
1
1
0
)
.
\begin{pmatrix} 0& 1\\ 1 & 0 \end{pmatrix}.
(
0
1
1
0
)
.
)
2
1
Hide problems
Really neat sets
A family
F
\mathcal{F}
F
of sets is called really neat if for any
A
,
B
∈
F
A,B\in \mathcal{F}
A
,
B
∈
F
, there is a set
C
∈
F
C\in \mathcal{F}
C
∈
F
such that
A
∪
B
=
A
∪
C
=
B
∪
C
A\cup B = A\cup C=B\cup C
A
∪
B
=
A
∪
C
=
B
∪
C
. Let
f
(
n
)
=
min
{
max
A
∈
F
∣
A
∣
:
F
is really neat and
∣
∪
F
∣
=
n
}
.
f(n)=\min \left\{ \max_{A\in \mathcal{F}} |A| \colon \mathcal{F} \text{ is really neat and } |\cup \mathcal{F}| =n\right\} .
f
(
n
)
=
min
{
A
∈
F
max
∣
A
∣
:
F
is really neat and
∣
∪
F
∣
=
n
}
.
Prove that the sequence
f
(
n
)
/
n
f(n)/n
f
(
n
)
/
n
converges and find its limit.
1
1
Hide problems
Chromatic number is countable
Let
S
⊂
R
S\subset \mathbb{R}
S
⊂
R
be a closed set and
f
:
R
2
n
→
R
f:\mathbb{R}^{2n}\to \mathbb{R}
f
:
R
2
n
→
R
be a continuous function. Define a graph
G
G
G
as follows: Let
x
x
x
be a vertex of
G
G
G
iff
x
∈
R
n
x\in \mathbb{R}^{n}
x
∈
R
n
and
f
(
x
,
x
)
∉
S
f(x,x)\not\in S
f
(
x
,
x
)
∈
S
, then connect the vertices
x
x
x
and
y
y
y
by an edge in
G
G
G
iff
f
(
x
,
y
)
∈
S
f(x,y)\in S
f
(
x
,
y
)
∈
S
or
f
(
y
,
x
)
∈
S
f(y,x)\in S
f
(
y
,
x
)
∈
S
. Show that the chromatic number of
G
G
G
is countable.