MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
2010 Miklós Schweitzer
2010 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(11)
11
1
Hide problems
Problem 11 Miklos Schweitzer
For problem 11 , i couldn’t find the correct translation , so i just posted the hungarian version . If anyone could translate it ,i would be very thankful . [tip=see hungarian]Az
X
X
X
́es
Y
Y
Y
valo ́s ́ert ́eku ̋ v ́eletlen v ́altoz ́ok maxim ́alkorrel ́acio ́ja az
f
(
X
)
f(X)
f
(
X
)
́es
g
(
Y
)
g(Y )
g
(
Y
)
v ́altoz ́ok korrela ́cio ́j ́anak szupr ́emuma az olyan
f
f
f
́es
g
g
g
Borel m ́erheto ̋,
R
→
R
\mathbb{R} \to \mathbb{R}
R
→
R
fu ̈ggv ́enyeken, amelyekre
f
(
X
)
f(X)
f
(
X
)
́es
g
(
Y
)
g(Y)
g
(
Y
)
v ́eges sz ́ora ́su ́. Legyen U a
[
0
,
2
π
]
[0,2\pi]
[
0
,
2
π
]
interval- lumon egyenletes eloszl ́asu ́ val ́osz ́ınu ̋s ́egi v ́altozo ́, valamint n ́es m pozit ́ıv eg ́eszek. Sz ́am ́ıtsuk ki
sin
(
n
U
)
\sin(nU)
sin
(
n
U
)
́es
sin
(
m
U
)
\sin(mU)
sin
(
m
U
)
maxim ́alkorrela ́ci ́oja ́t. Edit: [hide=Translation thanks to @tintarn] The maximal correlation of two random variables
X
X
X
and
Y
Y
Y
is defined to be the supremum of the correlations of
f
(
X
)
f(X)
f
(
X
)
and
g
(
Y
)
g(Y)
g
(
Y
)
where
f
,
g
:
R
→
R
f,g:\mathbb{R} \to \mathbb{R}
f
,
g
:
R
→
R
are measurable functions such that
f
(
X
)
f(X)
f
(
X
)
and
g
(
Y
)
g(Y)
g
(
Y
)
is (almost surely?) finite. Let
U
U
U
be the uniformly distributed random variable on
[
0
,
2
π
]
[0,2\pi]
[
0
,
2
π
]
and let
m
,
n
m,n
m
,
n
be positive integers. Compute the maximal correlation of
sin
(
n
U
)
\sin(nU)
sin
(
n
U
)
and
sin
(
m
U
)
\sin(mU)
sin
(
m
U
)
. (Remark: It seems that to make sense we should require that
E
[
f
(
X
)
]
E[f(X)]
E
[
f
(
X
)]
and
E
[
g
(
Y
)
]
E[g(Y)]
E
[
g
(
Y
)]
as well as
E
[
f
(
X
)
2
]
E[f(X)^2]
E
[
f
(
X
)
2
]
and
E
[
g
(
Y
)
2
]
E[g(Y)^2]
E
[
g
(
Y
)
2
]
are finite. In fact, we may then w.l.o.g. assume that
E
[
f
(
X
)
]
=
E
[
g
(
Y
)
]
=
0
E[f(X)]=E[g(Y)]=0
E
[
f
(
X
)]
=
E
[
g
(
Y
)]
=
0
and
E
[
f
(
Y
)
2
]
=
E
[
g
(
Y
)
2
]
=
1
E[f(Y)^2]=E[g(Y)^2]=1
E
[
f
(
Y
)
2
]
=
E
[
g
(
Y
)
2
]
=
1
.)
10
1
Hide problems
Finite number of Borel sets
Consider the space
{
0
,
1
}
N
\{0,1 \} ^{N}
{
0
,
1
}
N
with the product topology (where
{
0
,
1
}
\{0,1 \}
{
0
,
1
}
is a discrete space). Let
T
:
{
0
,
1
}
N
→
{
0
,
1
}
N
T: \{0,1 \} ^ {\mathbb {N}} \rightarrow \{0,1 \} ^ {\mathbb {N}}
T
:
{
0
,
1
}
N
→
{
0
,
1
}
N
be the left-shift, ie
(
T
x
)
(
n
)
=
x
(
n
+
1
)
(Tx) (n) = x (n+1)
(
T
x
)
(
n
)
=
x
(
n
+
1
)
for every
n
∈
N
n \in \mathbb {N}
n
∈
N
. Can a finite number of Borel sets be given:
B
1
,
…
,
B
m
⊂
{
0
,
1
}
N
B_ {1}, \ldots, B_ {m} \subset \{0,1 \} ^ {N}
B
1
,
…
,
B
m
⊂
{
0
,
1
}
N
such that
{
T
i
(
B
j
)
∣
i
∈
N
,
1
≤
j
≤
m
}
\left \{T ^ {i} \left (B_ {j} \right) \mid i \in \mathbb {N}, 1 \leq j \leq m \right \}
{
T
i
(
B
j
)
∣
i
∈
N
,
1
≤
j
≤
m
}
the
σ
\sigma
σ
-algebra generated by the set system coincides with the Borel set system?
9
1
Hide problems
M dimensional closed set
For each
M
M
M
m-dimensional closed
C
∞
C^{\infty}
C
∞
set , assign a
G
(
m
)
G(m)
G
(
m
)
in some euclidean space
R
q
\mathbb{R}^{q}
R
q
. Denote by
R
P
q
\mathbb{R} \mathbb{P}^{q}
R
P
q
a
q
q
q
-dimensional real projecive space. A
G
(
M
)
⊆
×
R
P
q
G(M) \subseteq \times \mathbb{R} \mathbb{P}^{q}
G
(
M
)
⊆
×
R
P
q
. The set consists of
(
x
,
e
)
(x,e)
(
x
,
e
)
pairs for which
x
∈
M
⊆
P
q
x \in M \subseteq \mathbb {P}^{q}
x
∈
M
⊆
P
q
and
e
⊆
R
q
+
1
=
R
q
×
R
e \subseteq \mathbb {R}^{q+1}= \mathbb{R}^{q} \times \mathbb{R}
e
⊆
R
q
+
1
=
R
q
×
R
and
a
(
0
,
…
,
0
,
1
)
∈
R
q
+
1
\mathrm{a} (0, \ldots,0,1) \in \mathbb{R}^{q+1}
a
(
0
,
…
,
0
,
1
)
∈
R
q
+
1
in a stretched
(
m
+
1
)
(m+1)
(
m
+
1
)
-dimensional linear subspace. Prove that if
N
N
N
is a
n
n
n
-dimensional closed set
C
∞
C^{\infty}
C
∞
, then
P
=
G
(
M
×
M
)
P=G(M \times M)
P
=
G
(
M
×
M
)
and
Q
=
G
(
M
)
×
G
(
N
)
Q=G(M) \times G(N)
Q
=
G
(
M
)
×
G
(
N
)
are cobordant , that is, there exists a
(
2
m
+
2
n
+
1
)
(2m+2n+1)
(
2
m
+
2
n
+
1
)
-dimensional compact , flanged set
C
∞
C^{\infty}
C
∞
with a disjoint union of
P
P
P
and
Q
Q
Q
.
8
1
Hide problems
Finite Lebesgue measure of a connected open set and harmonic function
Let
D
⊂
R
2
D \subset \mathbb {R} ^ {2}
D
⊂
R
2
be a finite Lebesgue measure of a connected open set and
u
:
D
→
R
u: D \rightarrow \mathbb {R}
u
:
D
→
R
a harmonic function. Show that it is either a constant
u
u
u
or for almost every
p
∈
D
p \in D
p
∈
D
f ^ {\prime} (t) = (\operatorname {grad} u) (f (t)), f (0) = p has no initial value problem(differentiable everywhere) solution to
f
:
[
0
,
∞
)
→
D
f:[0,\infty) \rightarrow D
f
:
[
0
,
∞
)
→
D
.
6
1
Hide problems
Continuous function being monotone
Is there a continuous function
f
:
R
2
→
R
f: \mathbb {R} ^ {2} \rightarrow \mathbb {R}
f
:
R
2
→
R
for every
d
∈
R
d \in \mathbb {R}
d
∈
R
we have
g
m
,
d
(
x
)
=
f
(
x
,
m
x
+
d
)
g_{m,d}(x) = f (x, m x + d)
g
m
,
d
(
x
)
=
f
(
x
,
m
x
+
d
)
is strictly monotonic on
R
\mathbb {R}
R
if
m
≥
0
,
m \ge 0,
m
≥
0
,
and not monotone on any non-empty open interval if
m
<
0
?
m <0?
m
<
0
?
5
1
Hide problems
Vectors in a plane
Given the vectors
v
1
,
…
,
v
n
v_ {1}, \dots, v_ {n}
v
1
,
…
,
v
n
and
w
1
,
…
,
w
n
w_ {1}, \dots, w_ {n}
w
1
,
…
,
w
n
in the plane with the following properties: for every
1
≤
i
≤
n
1 \leq i \leq n
1
≤
i
≤
n
,
∣
v
i
−
w
i
∣
≤
1
,
\left | v_{i} -w_{i} \right | \leq 1,
∣
v
i
−
w
i
∣
≤
1
,
and for every
1
≤
i
<
j
≤
n
1 \leq i <j \leq n
1
≤
i
<
j
≤
n
,
∣
v
i
−
v
j
∣
≥
3
\left | v_{i} -v_{j} \right | \ge 3
∣
v
i
−
v
j
∣
≥
3
and
v
i
−
w
i
≠
v
j
−
w
j
v_{i} -w_ {i} \ne v_ {j} -w_ {j}
v
i
−
w
i
=
v
j
−
w
j
. Prove that for sets
V
=
{
v
1
,
…
,
v
n
}
V = \left \{v_ {1}, \dots, v_{n } \right \}
V
=
{
v
1
,
…
,
v
n
}
and
W
=
{
w
1
,
…
,
w
n
}
W = \left \{w_ {1}, \dots, w_ {n} \right \}
W
=
{
w
1
,
…
,
w
n
}
, the set of
V
+
(
V
∪
W
)
V + (V \cup W)
V
+
(
V
∪
W
)
must have at least
c
n
3
/
2
cn^{3/2}
c
n
3/2
elements ,for some universal constant
c
>
0
c>0
c
>
0
.
4
1
Hide problems
Idealized unit-element commutative ring
Prove that if
n
≥
2
n \geq 2
n
≥
2
and
I
1
,
I
2
,
…
,
I
n
I_ {1}, I_ {2}, \ldots, I_ {n}
I
1
,
I
2
,
…
,
I
n
are idealized in a unit-element commutative ring such that any nonempty
H
⊆
{
1
,
2
,
…
,
n
}
H \subseteq \{ 1,2, \dots, n \}
H
⊆
{
1
,
2
,
…
,
n
}
then if
∑
h
∈
H
I
h
\sum_ {h \in H} I_ {h}
∑
h
∈
H
I
h
Is ideal
I
2
I
3
I
4
…
I
n
+
I
1
I
3
I
4
…
I
n
+
⋯
+
I
1
I
2
…
I
n
−
1
I_ {2} I_ {3} I_ {4} \dots I_ {n} + I_ {1} I_ {3} I_ {4} \dots I_ {n} + \dots + I_ {1} I_ {2} \dots I_ {n-1}
I
2
I
3
I
4
…
I
n
+
I
1
I
3
I
4
…
I
n
+
⋯
+
I
1
I
2
…
I
n
−
1
also Is ideal.
3
1
Hide problems
Maximum number of subsets
Let
A
i
,
i
=
1
,
2
,
…
,
t
A_i,i=1,2,\dots,t
A
i
,
i
=
1
,
2
,
…
,
t
be distinct subsets of the base set
{
1
,
2
,
…
,
n
}
\{1,2,\dots,n\}
{
1
,
2
,
…
,
n
}
complying to the following condition
A
i
∩
A
k
⊆
A
j
\displaystyle A_ {i} \cap A_ {k} \subseteq A_ {j}
A
i
∩
A
k
⊆
A
j
for any
1
≤
i
<
j
<
k
≤
t
.
1 \leq i <j <k \leq t.
1
≤
i
<
j
<
k
≤
t
.
Find the maximum value of
t
.
t.
t
.
Thanks @dgrozev
2
1
Hide problems
D-regular ,vertex-transitive graph
Let
G
G
G
be a countably infinite,
d
d
d
-regular, connected, vertex-transitive graph. Show that there is a complete pairing in
G
G
G
.
1
1
Hide problems
x^x \equiv 1 (mod p)
Let
p
p
p
be prime. Denote by
N
(
p
)
N (p)
N
(
p
)
the number of integers
x
x
x
for which
1
≤
x
≤
p
1 \leq x \leq p
1
≤
x
≤
p
and x ^ {x} \equiv 1 (\bmod p) Prove that there exist numbers
c
<
1
/
2
c <1/2
c
<
1/2
and
p
0
>
0
p_ {0}> 0
p
0
>
0
such that
N
(
p
)
≤
p
c
N (p) \leq p ^ {c}
N
(
p
)
≤
p
c
if
p
≥
p
0
p \ge p_ {0}
p
≥
p
0
.
7
1
Hide problems
Non-bounded linear operator \ell^2 \to \ell^2
Is there any sequence
(
a
n
)
n
=
1
∞
(a_n)_{n=1}^{\infty}
(
a
n
)
n
=
1
∞
of non-negative numbers, for which
∑
n
=
1
∞
a
n
2
<
∞
\sum_{n=1}^{\infty} a_n^2<\infty
∑
n
=
1
∞
a
n
2
<
∞
, but
∑
n
=
1
∞
(
∑
k
=
1
∞
a
k
n
k
)
2
=
∞
\sum_{n=1}^{\infty}\left(\sum_{k=1}^{\infty}\frac{a_{kn}}{k} \right)^2=\infty
∑
n
=
1
∞
(
∑
k
=
1
∞
k
a
kn
)
2
=
∞
? That contest - Miklos Schweitzer 2010- is missing on the contest page here for now being. The statements of all problems that year can be found [url=http://www.math.u-szeged.hu/~mmaroti/schweitzer/]here, but unfortunately only in Hungarian. I tried google translate but it was a mess. So, it would be wonderful if someone knows Hungarian and wish to translate it.