MathDB
Problems
Contests
Undergraduate contests
Vojtěch Jarník IMC
2009 VJIMC
2009 VJIMC
Part of
Vojtěch Jarník IMC
Subcontests
(4)
Problem 3
2
Hide problems
coloring with conditions, subsets-based
Let
k
k
k
and
n
n
n
be positive integers such that
k
≤
n
−
1
k\le n-1
k
≤
n
−
1
. Let
S
:
=
{
1
,
2
,
…
,
n
}
S:=\{1,2,\ldots,n\}
S
:=
{
1
,
2
,
…
,
n
}
and let
A
1
,
A
2
,
…
,
A
k
A_1,A_2,\ldots,A_k
A
1
,
A
2
,
…
,
A
k
be nonempty subsets of
S
S
S
. Prove that it is possible to color some elements of
S
S
S
using two colors, red and blue, such that the following conditions are satisfied:(i) Each element of
S
S
S
is either left uncolored or is colored red or blue. (ii) At least one element of
S
S
S
is colored. (iii) Each set
A
i
(
i
=
1
,
2
,
…
,
k
)
A_i~(i=1,2,\ldots,k)
A
i
(
i
=
1
,
2
,
…
,
k
)
is either completely uncolored or it contains at least one red and at least one blue element.
given p^2*A^(p^2)=q^2*A^(q^2)+r^2*I_n
Let
A
A
A
be an
n
×
n
n\times n
n
×
n
square matrix with integer entries. Suppose that
p
2
A
p
2
=
q
2
A
q
2
+
r
2
I
n
p^2A^{p^2}=q^2A^{q^2}+r^2I_n
p
2
A
p
2
=
q
2
A
q
2
+
r
2
I
n
for some positive integers
p
,
q
,
r
p,q,r
p
,
q
,
r
where
r
r
r
is odd and
p
2
=
q
2
+
r
2
p^2=q^2+r^2
p
2
=
q
2
+
r
2
. Prove that
∣
det
A
∣
=
1
|\det A|=1
∣
det
A
∣
=
1
. (Here
I
n
I_n
I
n
means the
n
×
n
n\times n
n
×
n
identity matrix.)
Problem 2
2
Hide problems
composite: 2^(2^k-1)-2^k-1
Prove that the number
2
2
k
−
1
−
2
k
−
1
2^{2^k-1}-2^k-1
2
2
k
−
1
−
2
k
−
1
is composite (not prime) for all positive integers
k
>
2
k>2
k
>
2
.
integral of (1+x^2)f'(x)^2
Let
E
E
E
be the set of all continuously differentiable real valued functions
f
f
f
on
[
0
,
1
]
[0,1]
[
0
,
1
]
such that
f
(
0
)
=
0
f(0)=0
f
(
0
)
=
0
and
f
(
1
)
=
1
f(1)=1
f
(
1
)
=
1
. Define
J
(
f
)
=
∫
0
1
(
1
+
x
2
)
f
′
(
x
)
2
d
x
.
J(f)=\int^1_0(1+x^2)f'(x)^2\text dx.
J
(
f
)
=
∫
0
1
(
1
+
x
2
)
f
′
(
x
)
2
d
x
.
a) Show that
J
J
J
achieves its minimum value at some element of
E
E
E
. b) Calculate
min
f
∈
E
J
(
f
)
\min_{f\in E}J(f)
min
f
∈
E
J
(
f
)
.
Problem 4
2
Hide problems
sequences cover Z
Let
(
a
n
)
n
=
1
∞
(a_n)_{n=1}^\infty
(
a
n
)
n
=
1
∞
be a sequence of real numbers. We say that the sequence
(
a
n
)
n
=
1
∞
(a_n)_{n=1}^\infty
(
a
n
)
n
=
1
∞
covers the set of positive integers if for any positive integer
m
m
m
there exists a positive integer
k
k
k
such that
∑
n
=
1
∞
a
n
k
=
m
\sum_{n=1}^\infty a_n^k=m
∑
n
=
1
∞
a
n
k
=
m
.a) Does there exist a sequence of real positive numbers which covers the set of positive integers? b) Does there exist a sequence of real numbers which covers the set of positive integers?
partition coloring, prove inequality
Let
k
,
m
,
n
k,m,n
k
,
m
,
n
be positive integers such that
1
≤
m
≤
n
1\le m\le n
1
≤
m
≤
n
and denote
S
=
{
1
,
2
,
…
,
n
}
S=\{1,2,\ldots,n\}
S
=
{
1
,
2
,
…
,
n
}
. Suppose that
A
1
,
A
2
,
…
,
A
k
A_1,A_2,\ldots,A_k
A
1
,
A
2
,
…
,
A
k
are
m
m
m
-element subsets of
S
S
S
with the following property: for every
i
=
1
,
2
,
…
,
k
i=1,2,\ldots,k
i
=
1
,
2
,
…
,
k
there exists a partition
S
=
S
1
,
i
∪
S
2
,
i
∪
…
∪
S
m
,
i
S=S_{1,i}\cup S_{2,i}\cup\ldots\cup S_{m,i}
S
=
S
1
,
i
∪
S
2
,
i
∪
…
∪
S
m
,
i
(into pairwise disjoint subsets) such that(i)
A
i
A_i
A
i
has precisely one element in common with each member of the above partition. (ii) Every
A
j
,
j
≠
i
A_j,j\ne i
A
j
,
j
=
i
is disjoint from at least one member of the above partition.Show that
k
≤
(
n
−
1
m
−
1
)
k\le\binom{n-1}{m-1}
k
≤
(
m
−
1
n
−
1
)
.
Problem 1
2
Hide problems
incenter of AIB, etc., limit of sequence
Let
A
B
C
ABC
A
BC
be a non-degenerate triangle in the euclidean plane. Define a sequence
(
C
n
)
n
=
0
∞
(C_n)_{n=0}^\infty
(
C
n
)
n
=
0
∞
of points as follows:
C
0
:
=
C
C_0:=C
C
0
:=
C
, and
C
n
+
1
C_{n+1}
C
n
+
1
is the incenter of the triangle
A
B
C
n
ABC_n
A
B
C
n
. Find
lim
n
→
∞
C
n
\lim_{n\to\infty}C_n
lim
n
→
∞
C
n
.
self-descriptive number in base b
A positive integer
m
m
m
is called self-descriptive in base
b
b
b
, where
b
≥
2
b\ge2
b
≥
2
is an integer, ifi) The representation of
m
m
m
in base
b
b
b
is of the form
(
a
0
a
1
…
a
b
−
1
)
b
(a_0a_1\ldots a_{b-1})_b
(
a
0
a
1
…
a
b
−
1
)
b
(that is
m
=
a
0
b
b
−
1
+
a
1
b
b
−
2
+
…
+
a
b
−
2
b
+
a
b
−
1
m=a_0b^{b-1}+a_1b^{b-2}+\ldots+a_{b-2}b+a_{b-1}
m
=
a
0
b
b
−
1
+
a
1
b
b
−
2
+
…
+
a
b
−
2
b
+
a
b
−
1
, where
0
≤
a
i
≤
b
−
1
0\le a_i\le b-1
0
≤
a
i
≤
b
−
1
are integers). ii)
a
i
a_i
a
i
is equal to the number of occurences of the number
i
i
i
in the sequence
(
a
0
a
1
…
a
b
−
1
)
(a_0a_1\ldots a_{b-1})
(
a
0
a
1
…
a
b
−
1
)
.For example,
(
1210
)
4
(1210)_4
(
1210
)
4
is self-descriptive in base
4
4
4
, because it has four digits and contains one
0
0
0
, two
1
1
1
s, one
2
2
2
and no
3
3
3
s.