MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2002 Miklós Schweitzer
2002 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(10)
10
1
Hide problems
Miklós Schweitzer 2002, Problem 10
Let
X
1
,
X
2
,
…
X_1, X_2, \ldots
X
1
,
X
2
,
…
be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let
a
n
a_n
a
n
denote the probability that
X
1
,
…
,
X
n
+
1
X_1,\ldots, X_{n+1}
X
1
,
…
,
X
n
+
1
are all different on the condition that
X
1
,
…
,
X
n
X_1,\ldots, X_n
X
1
,
…
,
X
n
are all different (
n
≥
1
n\ge 1
n
≥
1
). Show that (a)
a
n
a_n
a
n
is strictly decreasing and tends to
0
0
0
as
n
→
∞
n\to \infty
n
→
∞
; and (b) for any sequence
1
≤
f
(
1
)
≤
f
(
2
)
<
…
1\le f(1)\le f(2) < \ldots
1
≤
f
(
1
)
≤
f
(
2
)
<
…
of positive integers the joint distribution of
X
1
,
X
2
,
…
X_1, X_2, \ldots
X
1
,
X
2
,
…
can be chosen such that
lim sup
n
→
∞
a
f
(
n
)
a
n
=
1
\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1
n
→
∞
lim
sup
a
n
a
f
(
n
)
=
1
holds.
9
1
Hide problems
Miklós Schweitzer 2002, Problem 9
Let
M
M
M
be a connected, compact
C
∞
C^{\infty}
C
∞
-differentiable manifold, and denote the vector space of smooth real functions on
M
M
M
by
C
∞
(
M
)
C^{\infty}(M)
C
∞
(
M
)
. Let the subspace
V
≤
C
∞
(
M
)
V\le C^{\infty}(M)
V
≤
C
∞
(
M
)
be invariant under
C
∞
C^{\infty}
C
∞
-diffeomorphisms of
M
M
M
, that is, let
f
∘
h
∈
V
f\circ h\in V
f
∘
h
∈
V
for every
f
∈
V
f\in V
f
∈
V
and for every
C
∞
C^{\infty}
C
∞
-diffeomorphism
h
:
M
→
M
h\colon M\rightarrow M
h
:
M
→
M
. Prove that if
V
V
V
is different from the subspaces
{
0
}
\{ 0\}
{
0
}
and
C
∞
(
M
)
C^{\infty}(M)
C
∞
(
M
)
then
V
V
V
only contains the constant functions.
8
1
Hide problems
Miklós Schweitzer 2002, Problem 8
Prove that there exists an absolute constant
c
c
c
such that any set
H
H
H
of
n
n
n
points of the plane in general position can be coloured with
c
log
n
c\log n
c
lo
g
n
colours in such a way that any disk of the plane containing at least one point of
H
H
H
intersects some colour class of
H
H
H
in exactly one point.
7
1
Hide problems
Miklós Schweitzer 2002, Problem 7
Let the complex function
F
(
z
)
F(z)
F
(
z
)
be regular on the punctuated disk
{
0
<
∣
z
∣
<
R
}
\{ 0<|z| < R\}
{
0
<
∣
z
∣
<
R
}
. By a level curve we mean a component of the level set of
R
e
F
(
z
)
\mathrm{Re}F(z)
Re
F
(
z
)
, that is, a maximal connected set on which
R
e
F
(
z
)
\mathrm{Re}F(z)
Re
F
(
z
)
is constant. Denote by
A
(
r
)
A(r)
A
(
r
)
the union of those level curves that are entirely contained in the punctuated disk
{
0
<
∣
z
∣
<
r
}
\{ 0<|z|<r\}
{
0
<
∣
z
∣
<
r
}
. Prove that if the number of components of
A
(
r
)
A(r)
A
(
r
)
has an upper bound independent of
r
r
r
then
F
(
z
)
F(z)
F
(
z
)
can only have a pole type singularity at
0
0
0
.
6
1
Hide problems
Miklós Schweitzer 2002, Problem 6
Let
K
⊆
R
K\subseteq \mathbb{R}
K
⊆
R
be compact. Prove that the following two statements are equivalent to each other. (a) For each point
x
x
x
of
K
K
K
we can assign an uncountable set
F
x
⊆
R
F_x\subseteq \mathbb{R}
F
x
⊆
R
such that
d
i
s
t
(
F
x
,
F
y
)
≥
∣
x
−
y
∣
\mathrm{dist}(F_x, F_y)\ge |x-y|
dist
(
F
x
,
F
y
)
≥
∣
x
−
y
∣
holds for all
x
,
y
∈
K
x,y\in K
x
,
y
∈
K
; (b)
K
K
K
is of measure zero.
5
1
Hide problems
Miklós Schweitzer 2002, Problem 5
Denote by
λ
(
H
)
\lambda (H)
λ
(
H
)
the Lebesgue outer measure of
H
⊆
[
0
,
1
]
H\subseteq \left[ 0,1\right]
H
⊆
[
0
,
1
]
. The horizontal and vertical sections of the set
A
⊆
[
0
,
1
]
×
[
0
,
1
]
A\subseteq [0, 1]\times [ 0, 1]
A
⊆
[
0
,
1
]
×
[
0
,
1
]
are denoted by
A
y
A^y
A
y
and
A
x
A_x
A
x
respectively; that is,
A
y
=
{
x
∈
[
0
,
1
]
:
(
x
,
y
)
∈
A
}
A^y=\{ x\in [ 0, 1] \colon (x, y) \in A\}
A
y
=
{
x
∈
[
0
,
1
]
:
(
x
,
y
)
∈
A
}
and
A
x
=
{
y
∈
[
0
,
1
]
:
(
x
,
y
)
∈
A
}
A_x=\{ y\in [ 0, 1]\colon (x,y)\in A\}
A
x
=
{
y
∈
[
0
,
1
]
:
(
x
,
y
)
∈
A
}
for all
x
,
y
∈
[
0
,
1
]
x,y\in [0,1]
x
,
y
∈
[
0
,
1
]
. (a) Is there a decomposition
A
∪
B
A\cup B
A
∪
B
of the unit square
[
0
,
1
]
×
[
0
,
1
]
[0,1]\times [0,1]
[
0
,
1
]
×
[
0
,
1
]
such that
A
y
A^y
A
y
is the union of finitely many segments of total length less than
1
2
\frac12
2
1
and
λ
(
B
x
)
≤
1
2
\lambda (B_x)\le \frac12
λ
(
B
x
)
≤
2
1
for all
x
,
y
∈
[
0
,
1
]
x, y\in [0,1]
x
,
y
∈
[
0
,
1
]
? (b) Is there a decomposition
A
∪
B
A\cup B
A
∪
B
of the unit square
[
0
,
1
]
×
[
0
,
1
]
[0,1] \times [0,1]
[
0
,
1
]
×
[
0
,
1
]
such that
A
y
A^y
A
y
is the union of finitely many segments of total length not greater than
1
2
\frac12
2
1
and
λ
(
B
x
)
<
1
2
\lambda (B_x)<\frac12
λ
(
B
x
)
<
2
1
for all
x
,
y
∈
[
0
,
1
]
x,y\in [0,1]
x
,
y
∈
[
0
,
1
]
?
4
1
Hide problems
Miklós Schweitzer 2002, Problem 4
For a given natural number
n
n
n
, consider those sets
A
⊆
Z
n
A\subseteq \mathbb{Z}_n
A
⊆
Z
n
for which the equation
x
y
=
u
v
xy=uv
x
y
=
uv
has no other solution in the residual classes
x
,
y
,
u
,
v
∈
A
x,y,u,v\in A
x
,
y
,
u
,
v
∈
A
than the trivial solutions
x
=
u
x=u
x
=
u
,
y
=
v
y=v
y
=
v
and
x
=
v
x=v
x
=
v
,
y
=
u
y=u
y
=
u
. Let
g
(
n
)
g(n)
g
(
n
)
be the maximum of the size of such sets
A
A
A
. Prove that
lim sup
n
→
∞
g
(
n
)
n
=
1
\limsup_{n\to\infty}\frac{g(n)}{\sqrt{n}}=1
n
→
∞
lim
sup
n
g
(
n
)
=
1
3
1
Hide problems
Miklós Schweitzer 2002, Problem 3
Put
A
=
{
y
e
s
,
n
o
}
\mathbb{A}=\{ \mathrm{yes}, \mathrm{no} \}
A
=
{
yes
,
no
}
. A function
f
:
A
n
→
A
f\colon \mathbb{A}^n\rightarrow \mathbb{A}
f
:
A
n
→
A
is called a decision function if (a) the value of the function changes if we change all of its arguments; and (b) the values does not change if we replace any of the arguments by the function value. A function
d
:
A
n
→
A
d\colon \mathbb{A}^n \rightarrow \mathbb{A}
d
:
A
n
→
A
is called a dictatoric function, if there is an index
i
i
i
such that the value of the function equals its
i
i
i
th argument. The democratic function is the function
m
:
A
3
→
A
m\colon \mathbb{A}^3 \rightarrow \mathbb{A}
m
:
A
3
→
A
that outputs the majority of its arguments. Prove that any decision function is a composition of dictatoric and democratic functions.
1
1
Hide problems
Miklós Schweitzer 2002, Problem 1
For an arbitrary ordinal number
α
\alpha
α
let
H
(
α
)
H(\alpha)
H
(
α
)
denote the set of functions
f
:
α
→
{
−
1
,
0
,
1
}
f\colon \alpha \rightarrow \{ -1,0,1\}
f
:
α
→
{
−
1
,
0
,
1
}
that map all but finitely many elements of
α
\alpha
α
to
0
0
0
. Order
H
(
α
)
H(\alpha)
H
(
α
)
according to the last difference, that is, for
f
,
g
∈
H
(
α
)
f, g\in H(\alpha)
f
,
g
∈
H
(
α
)
let
f
≺
g
f\prec g
f
≺
g
if
f
(
β
)
<
g
(
β
)
f(\beta) < g(\beta)
f
(
β
)
<
g
(
β
)
holds for the maximum ordinal number
β
<
α
\beta < \alpha
β
<
α
with
f
(
β
)
≠
g
(
β
)
f(\beta) \neq g(\beta)
f
(
β
)
=
g
(
β
)
. Prove that the ordered set
(
H
(
α
)
,
≺
)
(H(\alpha), \prec)
(
H
(
α
)
,
≺
)
is scattered (i.e. it doesn't contain a subset isomorphic to the set of rational numbers with the usual order), and that any scattered order type can be embedded into some
(
H
(
α
)
,
≺
)
(H(\alpha), \prec)
(
H
(
α
)
,
≺
)
.
2
1
Hide problems
Paths having at most 20n/k edges
Let
G
G
G
be a simple
k
k
k
edge-connected graph on
n
n
n
vertices and let
u
u
u
and
v
v
v
be different vertices of
G
G
G
. Prove that there are
k
k
k
edge-disjoint paths from
u
u
u
to
v
v
v
each having at most
20
n
k
\frac{20n}{k}
k
20
n
edges.