MathDB
Problems
Contests
Undergraduate contests
Brazil Undergrad MO
2017 Brazil Undergrad MO
2017 Brazil Undergrad MO
Part of
Brazil Undergrad MO
Subcontests
(6)
6
1
Hide problems
Words and equivalence
Let's consider words over the alphabet
{
a
,
b
}
\{a,b\}
{
a
,
b
}
to be sequences of
a
a
a
and
b
b
b
with finite length. We say
u
≤
v
u \leq v
u
≤
v
if
u
u
u
is a subword of
v
v
v
if we can get
u
u
u
erasing some letter of
v
v
v
(for example
a
b
a
≤
a
b
b
a
b
aba \leq abbab
aba
≤
abbab
). We say that
u
u
u
differentiates the words
x
x
x
and
y
y
y
if
u
≤
x
u \leq x
u
≤
x
but
u
≰
y
u \not\leq y
u
≤
y
or vice versa.Let
m
m
m
and
l
l
l
be positive integers. We say that two words are
m
−
m-
m
−
equivalents if there does not exist some
u
u
u
with length smaller than
m
m
m
that differentiates
x
x
x
and
y
y
y
.a) Show that, if
2
m
≤
l
2m \leq l
2
m
≤
l
, there exists two distinct words with length
l
l
l
\
m
−
m-
m
−
equivalents. b) Show that, if
2
m
>
l
2m > l
2
m
>
l
, any two distinct words with length
l
l
l
aren't
m
−
m-
m
−
equivalent.
5
1
Hide problems
Matrix and distances
Let
d
≤
n
d\leq n
d
≤
n
be positive integers and
A
A
A
a real
d
×
n
d\times n
d
×
n
matrix. Let
σ
(
A
)
\sigma(A)
σ
(
A
)
be the supremum of
inf
v
∈
W
,
∣
v
∣
=
1
∣
A
v
∣
\inf_{v\in W,|v|=1}|Av|
in
f
v
∈
W
,
∣
v
∣
=
1
∣
A
v
∣
over all subspaces
W
W
W
of
R
n
R^n
R
n
with dimension
d
d
d
.For each
j
≤
d
j \leq d
j
≤
d
, let
r
(
j
)
∈
R
n
r(j) \in \mathbb{R}^n
r
(
j
)
∈
R
n
be the
j
j
j
th row vector of
A
A
A
. Show that:
σ
(
A
)
≤
min
i
≤
d
d
(
r
(
i
)
,
⟨
r
(
j
)
,
j
≠
i
⟩
)
≤
n
σ
(
A
)
\sigma(A) \leq \min_{i\leq d} d(r(i), \langle r(j), j\ne i\rangle) \leq \sqrt{n}\sigma(A)
σ
(
A
)
≤
i
≤
d
min
d
(
r
(
i
)
,
⟨
r
(
j
)
,
j
=
i
⟩)
≤
n
σ
(
A
)
In which all are euclidian norms and
d
(
r
(
i
)
,
⟨
r
(
j
)
,
j
≠
i
⟩
)
d(r(i), \langle r(j), j\ne i\rangle)
d
(
r
(
i
)
,
⟨
r
(
j
)
,
j
=
i
⟩)
denotes the distance between
r
(
i
)
r(i)
r
(
i
)
and the span of
r
(
j
)
,
1
≤
j
≤
d
,
j
≠
i
r(j), 1 \leq j \leq d, j\ne i
r
(
j
)
,
1
≤
j
≤
d
,
j
=
i
.
4
1
Hide problems
sequences of real numbers
Let
(
a
n
)
n
≥
1
(a_n)_{n\geq 1}
(
a
n
)
n
≥
1
be a sequence of positive real numbers in which
lim
n
→
∞
a
n
=
0
\lim_{n\to\infty} a_n = 0
lim
n
→
∞
a
n
=
0
such that there is a constant
c
>
0
c >0
c
>
0
so that for all
n
≥
1
n \geq 1
n
≥
1
,
∣
a
n
+
1
−
a
n
∣
≤
c
⋅
a
n
2
|a_{n+1}-a_n| \leq c\cdot a_n^2
∣
a
n
+
1
−
a
n
∣
≤
c
⋅
a
n
2
. Show that exists
d
>
0
d>0
d
>
0
with
n
a
n
≥
d
,
∀
n
≥
1
na_n \geq d, \forall n \geq 1
n
a
n
≥
d
,
∀
n
≥
1
.
3
1
Hide problems
Geometry and permutations
Let
X
=
{
(
x
,
y
)
∈
R
2
∣
y
≥
0
,
x
2
+
y
2
=
1
}
∪
{
(
x
,
0
)
,
−
1
≤
x
≤
1
}
X = \{(x,y) \in \mathbb{R}^2 | y \geq 0, x^2+y^2 = 1\} \cup \{(x,0),-1\leq x\leq 1\}
X
=
{(
x
,
y
)
∈
R
2
∣
y
≥
0
,
x
2
+
y
2
=
1
}
∪
{(
x
,
0
)
,
−
1
≤
x
≤
1
}
be the edge of the closed semicircle with radius 1.a) Let
n
>
1
n>1
n
>
1
be an integer and
P
1
,
P
2
,
…
,
P
n
∈
X
P_1,P_2,\dots,P_n \in X
P
1
,
P
2
,
…
,
P
n
∈
X
. Show that there exists a permutation
σ
:
{
1
,
2
,
…
,
n
}
→
{
1
,
2
,
…
,
n
}
\sigma \colon \{1,2,\dots,n\}\to \{1,2,\dots,n\}
σ
:
{
1
,
2
,
…
,
n
}
→
{
1
,
2
,
…
,
n
}
such that
∑
j
=
1
n
∣
P
σ
(
j
+
1
)
−
P
σ
(
j
)
∣
2
≤
8
\sum_{j=1}^{n}|P_{\sigma(j+1)}-P_{\sigma(j)}|^2\leq 8
j
=
1
∑
n
∣
P
σ
(
j
+
1
)
−
P
σ
(
j
)
∣
2
≤
8
. Where
σ
(
n
+
1
)
=
σ
(
1
)
\sigma(n+1) = \sigma(1)
σ
(
n
+
1
)
=
σ
(
1
)
. b) Find all sets
{
P
1
,
P
2
,
…
,
P
n
}
⊂
X
\{P_1,P_2,\dots,P_n \} \subset X
{
P
1
,
P
2
,
…
,
P
n
}
⊂
X
such that for any permutation
σ
:
{
1
,
2
,
…
,
n
}
→
{
1
,
2
,
…
,
n
}
\sigma \colon \{1,2,\dots,n\}\to \{1,2,\dots,n\}
σ
:
{
1
,
2
,
…
,
n
}
→
{
1
,
2
,
…
,
n
}
,
∑
j
=
1
n
∣
P
σ
(
j
+
1
)
−
P
σ
(
j
)
∣
2
≥
8
\sum_{j=1}^{n}|P_{\sigma(j+1)}-P_{\sigma(j)}|^2 \geq 8
j
=
1
∑
n
∣
P
σ
(
j
+
1
)
−
P
σ
(
j
)
∣
2
≥
8
. Where
σ
(
n
+
1
)
=
σ
(
1
)
\sigma(n+1) = \sigma(1)
σ
(
n
+
1
)
=
σ
(
1
)
.
1
1
Hide problems
positivist polynomial
A polynomial is called positivist if it can be written as a product of two non-constant polynomials with non-negative real coefficients. Let
f
(
x
)
f(x)
f
(
x
)
be a polynomial of degree greater than one such that
f
(
x
n
)
f(x^n)
f
(
x
n
)
is positivist for some positive integer
n
n
n
. Show that
f
(
x
)
f(x)
f
(
x
)
is positivist.
2
1
Hide problems
Sequence divisible by infinite primes - Brazil Undergrad MO
Let
a
a
a
and
b
b
b
be fixed positive integers. Show that the set of primes that divide at least one of the terms of the sequence
a
n
=
a
⋅
201
7
n
+
b
⋅
201
6
n
a_n = a \cdot 2017^n + b \cdot 2016^n
a
n
=
a
⋅
201
7
n
+
b
⋅
201
6
n
is infinite.