MathDB
Problems
Contests
Undergraduate contests
Vojtěch Jarník IMC
2007 VJIMC
2007 VJIMC
Part of
Vojtěch Jarník IMC
Subcontests
(4)
Problem 4
2
Hide problems
weak convexity, prove inequality
Let
f
:
[
0
,
1
]
→
[
0
,
∞
)
f:[0,1]\to[0,\infty)
f
:
[
0
,
1
]
→
[
0
,
∞
)
be an arbitrary function satisfying
f
(
x
)
+
f
(
y
)
2
≤
f
(
x
+
y
2
)
+
1
\frac{f(x)+f(y)}2\le f\left(\frac{x+y}2\right)+1
2
f
(
x
)
+
f
(
y
)
≤
f
(
2
x
+
y
)
+
1
for all pairs
x
,
y
∈
[
0
,
1
]
x,y\in[0,1]
x
,
y
∈
[
0
,
1
]
. Prove that for all
0
≤
u
<
v
<
w
≤
1
0\le u<v<w\le1
0
≤
u
<
v
<
w
≤
1
,
w
−
v
w
−
u
f
(
u
)
+
v
−
u
w
−
u
f
(
w
)
≤
f
(
v
)
+
2.
\frac{w-v}{w-u}f(u)+\frac{v-u}{w-u}f(w)\le f(v)+2.
w
−
u
w
−
v
f
(
u
)
+
w
−
u
v
−
u
f
(
w
)
≤
f
(
v
)
+
2.
A in F, A subset B subset S implies B in F
Let
S
S
S
be a finite set with n elements and
F
\mathcal F
F
a family of subsets of
S
S
S
with the following property:
A
∈
F
,
A
⊆
B
⊆
S
⟹
B
∈
F
.
A\in\mathcal F,A\subseteq B\subseteq S\implies B\in\mathcal F.
A
∈
F
,
A
⊆
B
⊆
S
⟹
B
∈
F
.
Prove that the function
f
:
[
0
,
1
]
→
R
f:[0,1]\to\mathbb R
f
:
[
0
,
1
]
→
R
given by
f
(
t
)
:
=
∑
A
∈
F
t
∣
A
∣
(
1
−
t
)
∣
S
∖
A
∣
f(t):=\sum_{A\in\mathcal F}t^{|A|}(1-t)^|S\setminus A|
f
(
t
)
:=
A
∈
F
∑
t
∣
A
∣
(
1
−
t
)
∣
S
∖
A
∣
is nondecreasing (
∣
A
∣
|A|
∣
A
∣
denotes the number of elements of
A
A
A
).
Problem 3
2
Hide problems
limit of f(tx)/f(x) as x->infinity, f has a constant sign
A function
f
:
[
0
,
∞
)
→
R
∖
{
0
}
f:[0,\infty)\to\mathbb R\setminus\{0\}
f
:
[
0
,
∞
)
→
R
∖
{
0
}
is called slowly changing if for any
t
>
1
t>1
t
>
1
the limit
lim
x
→
∞
f
(
t
x
)
f
(
x
)
\lim_{x\to\infty}\frac{f(tx)}{f(x)}
lim
x
→
∞
f
(
x
)
f
(
t
x
)
exists and is equal to
1
1
1
. Is it true that every slowly changing function has for sufficiently large
x
x
x
a constant sign (i.e., is it true that for every slowly changing
f
f
f
there exists an
N
N
N
such that for every
x
,
y
>
N
x,y>N
x
,
y
>
N
we have
f
(
x
)
f
(
y
)
>
0
f(x)f(y)>0
f
(
x
)
f
(
y
)
>
0
?)
h:f(x+h)=f(x) for some x is lebesgue measurable
Let
f
:
[
0
,
1
]
→
R
f:[0,1]\to\mathbb R
f
:
[
0
,
1
]
→
R
be a continuous function such that
f
(
0
)
=
f
(
1
)
=
0
f(0)=f(1)=0
f
(
0
)
=
f
(
1
)
=
0
. Prove that the set
A
:
=
{
h
∈
[
0
,
1
]
:
f
(
x
+
h
)
=
f
(
x
)
for some
x
∈
[
0
,
1
]
}
A:=\{h\in[0,1]:f(x+h)=f(x)\text{ for some }x\in[0,1]\}
A
:=
{
h
∈
[
0
,
1
]
:
f
(
x
+
h
)
=
f
(
x
)
for some
x
∈
[
0
,
1
]}
is Lebesgue measureable and has Lebesgue measure at least
1
2
\frac12
2
1
.
Problem 1
2
Hide problems
two partitions of Q closed under addition/multiplication
Can the set of positive rationals be split into two nonempty disjoint subsets
Q
1
\mathbb Q_1
Q
1
and
Q
2
\mathbb Q_2
Q
2
, such that both are closed under addition, i.e.
p
+
q
∈
Q
k
p+q\in\mathbb Q_k
p
+
q
∈
Q
k
for every
p
,
q
∈
Q
k
p,q\in\mathbb Q_k
p
,
q
∈
Q
k
,
k
=
1
,
2
k=1,2
k
=
1
,
2
? Can it be done when addition is exchanged for multiplication, i.e.
p
⋅
q
∈
Q
k
p\cdot q\in\mathbb Q_k
p
⋅
q
∈
Q
k
for every
p
,
q
∈
Q
k
p,q\in\mathbb Q_k
p
,
q
∈
Q
k
,
k
=
1
,
2
k=1,2
k
=
1
,
2
?
construct A dense in [0,1]^2 and line intersections
Construct a set
A
⊂
[
0
,
1
]
×
[
0
,
1
]
A\subset[0,1]\times[0,1]
A
⊂
[
0
,
1
]
×
[
0
,
1
]
such that
A
A
A
is dense in
[
0
,
1
]
×
[
0
,
1
]
[0,1]\times[0,1]
[
0
,
1
]
×
[
0
,
1
]
and every vertical and every horizontal line intersects
A
A
A
in at most one point.
Problem 2
2
Hide problems
A+A^T=I implies det A>0
Let
A
A
A
be a real
n
×
n
n\times n
n
×
n
matrix satisfying
A
+
A
T
=
I
,
A+A^{\text T}=I,
A
+
A
T
=
I
,
where
A
T
A^{\text T}
A
T
denotes the transpose of
A
A
A
and
I
I
I
the
n
×
n
n\times n
n
×
n
identity matrix. Show that
det
A
>
0
\det A>0
det
A
>
0
.
necklace, min. # of colorings to distinguish beads
Alice has got a circular key ring with
n
n
n
keys,
n
≥
3
n\ge3
n
≥
3
. When she takes it out of her pocket, she does not know whether it got rotated and/or flipped. The only way she can distinguish the keys is by coloring them (a color is assigned to each key). What is the minimum number of colors needed?