MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2016 Miklós Schweitzer
2016 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(10)
5
1
Hide problems
Iterates in [n,n+1) with given upper density
Does there exist a piecewise linear continuous function
f
:
R
→
R
f:\mathbb{R}\to \mathbb{R}
f
:
R
→
R
such that for any two-way infinite sequence
a
n
∈
[
0
,
1
]
a_n\in[0,1]
a
n
∈
[
0
,
1
]
,
n
∈
Z
n\in\mathbb{Z}
n
∈
Z
, there exists an
x
∈
R
x\in\mathbb{R}
x
∈
R
with
lim sup
K
→
∞
#
{
k
≤
K
:
k
∈
N
,
f
k
(
x
)
∈
[
n
,
n
+
1
)
}
K
=
a
n
\limsup_{K\to \infty} \frac{\#\{k\le K\,:\, k\in\mathbb{N},f^k(x)\in[n,n+1)\}}{K}=a_n
K
→
∞
lim
sup
K
#
{
k
≤
K
:
k
∈
N
,
f
k
(
x
)
∈
[
n
,
n
+
1
)}
=
a
n
for all
n
∈
Z
n\in\mathbb{Z}
n
∈
Z
, where
f
k
=
f
∘
f
∘
⋯
∘
f
f^k=f\circ f\circ \dots\circ f
f
k
=
f
∘
f
∘
⋯
∘
f
stands for the
k
k
k
-fold iterate of
f
f
f
?
8
1
Hide problems
Noncongruent similar rectangle tiling
For which integers
n
>
1
n>1
n
>
1
does there exist a rectangle that can be subdivided into
n
n
n
pairwise noncongruent rectangles similar to the original rectangle?
4
1
Hide problems
a(n+m) <= a(n)+a(m)+f(n+m) with f(x)=x/log(x)
Prove that there exists a sequence
a
(
1
)
,
a
(
2
)
,
…
,
a
(
n
)
,
…
a(1),a(2),\dots,a(n),\dots
a
(
1
)
,
a
(
2
)
,
…
,
a
(
n
)
,
…
of real numbers such that
a
(
n
+
m
)
≤
a
(
n
)
+
a
(
m
)
+
n
+
m
log
(
n
+
m
)
a(n+m)\le a(n)+a(m)+\frac{n+m}{\log (n+m)}
a
(
n
+
m
)
≤
a
(
n
)
+
a
(
m
)
+
lo
g
(
n
+
m
)
n
+
m
for all integers
m
,
n
≥
1
m,n\ge 1
m
,
n
≥
1
, and such that the set
{
a
(
n
)
/
n
:
n
≥
1
}
\{a(n)/n:n\ge 1\}
{
a
(
n
)
/
n
:
n
≥
1
}
is everywhere dense on the real line.Remark. A theorem of de Bruijn and Erdős states that if the inequality above holds with
f
(
n
+
m
)
f(n + m)
f
(
n
+
m
)
in place of the last term on the right-hand side, where
f
(
n
)
≥
0
f(n)\ge 0
f
(
n
)
≥
0
is nondecreasing and
∑
n
=
2
∞
f
(
n
)
/
n
2
<
∞
\sum_{n=2}^\infty f(n)/n^2<\infty
∑
n
=
2
∞
f
(
n
)
/
n
2
<
∞
, then
a
(
n
)
/
n
a(n)/n
a
(
n
)
/
n
converges or tends to
(
−
∞
)
(-\infty)
(
−
∞
)
.
3
1
Hide problems
Hensel's lemma for polynomial rings
Prove that for any polynomial
P
P
P
with real coefficients, and for any positive integer
n
n
n
, there exists a polynomial
Q
Q
Q
with real coefficients such that
P
(
x
)
2
+
Q
(
x
)
2
P(x)^2 +Q(x)^2
P
(
x
)
2
+
Q
(
x
)
2
is divisible by
(
1
+
x
2
)
n
(1+x^2)^n
(
1
+
x
2
)
n
.
2
1
Hide problems
Connected spanning subgraphs map to points on a line
Let
K
=
(
V
,
E
)
K=(V,E)
K
=
(
V
,
E
)
be a finite, simple, complete graph. Let
d
d
d
be a positive integer. Let
ϕ
:
E
→
R
d
\phi:E\to \mathbb{R}^d
ϕ
:
E
→
R
d
be a map from the edge set to Euclidean space, such that the preimage of any point in the range defines a connected graph on the entire vertex set
V
V
V
, and the points assigned to the edges of any triangle in
K
K
K
are collinear. Show that the range of
ϕ
\phi
ϕ
is contained in a line.
1
1
Hide problems
Completely multiplicative, partial sum ax+O(1)
For which complex numbers
α
\alpha
α
does there exist a completely multiplicative, complex-valued arithmetic function
f
f
f
such that
∑
n
<
x
f
(
n
)
=
α
x
+
O
(
1
)
?
\sum_{n<x}f(n)=\alpha x+O(1)\,\,?
n
<
x
∑
f
(
n
)
=
αx
+
O
(
1
)
?
9
1
Hide problems
Expectation of probability on simplex at least 1/(d+2)
For
p
0
,
…
,
p
d
∈
R
d
p_0,\dots,p_d\in\mathbb{R}^d
p
0
,
…
,
p
d
∈
R
d
, let
S
(
p
0
,
…
,
p
d
)
=
{
α
0
p
0
+
⋯
+
α
d
p
d
:
α
i
≤
1
,
∑
i
=
0
d
α
i
=
1
}
.
S(p_0,\dots,p_d)=\left\{ \alpha_0p_0+\dots+\alpha_dp_d : \alpha_i\le 1, \sum_{i=0}^d \alpha_i =1 \right\}.
S
(
p
0
,
…
,
p
d
)
=
{
α
0
p
0
+
⋯
+
α
d
p
d
:
α
i
≤
1
,
i
=
0
∑
d
α
i
=
1
}
.
Let
π
\pi
π
be an arbitrary probability distribution on
R
d
\mathbb{R}^d
R
d
, and choose
p
0
,
…
,
p
d
p_0,\dots,p_d
p
0
,
…
,
p
d
independently with distribution
π
\pi
π
. Prove that the expectation of
π
(
S
(
p
0
,
…
,
p
d
)
)
\pi(S(p_0,\dots,p_d))
π
(
S
(
p
0
,
…
,
p
d
))
is at least
1
/
(
d
+
2
)
1/(d+2)
1/
(
d
+
2
)
.
10
1
Hide problems
Maximal expectation of distance on 2-sphere
Let
X
X
X
and
Y
Y
Y
be independent, identically distributed random points on the unit sphere in
R
3
\mathbb{R}^3
R
3
. For which distribution of
X
X
X
will the expectation of the (Euclidean) distance of
X
X
X
and
Y
Y
Y
be maximal?
6
1
Hide problems
F(s)/Gamma(s) bounded on Re(s)>0
Let
Γ
(
s
)
\Gamma(s)
Γ
(
s
)
denote Euler's gamma function. Construct an even entire function
F
(
s
)
F(s)
F
(
s
)
that does not vanish everywhere, for which the quotient
F
(
s
)
/
Γ
(
s
)
F(s)/\Gamma(s)
F
(
s
)
/Γ
(
s
)
is bounded on the right halfplane
{
ℜ
(
s
)
>
0
}
\{\Re(s)>0\}
{
ℜ
(
s
)
>
0
}
.
7
1
Hide problems
Unit sphere bundle equivalent to CP^{r-1}
Show that the unit sphere bundle of the
r
r
r
-fold direct sum of the tautological (universal) complex line bundle over the space
C
P
∞
\mathbb{C}P^{\infty}
C
P
∞
is homotopically equivalent to
C
P
r
−
1
\mathbb{C}P^{r-1}
C
P
r
−
1
.