MathDB
Problems
Contests
Undergraduate contests
Brazil Undergrad MO
2024 Brazil Undergrad MO
2024 Brazil Undergrad MO
Part of
Brazil Undergrad MO
Subcontests
(6)
6
1
Hide problems
limit sum of Farey sequence
For each positive integer
n
n
n
, list in increasing order all irreducible fractions in the interval
[
0
,
1
]
[0, 1]
[
0
,
1
]
that have a positive denominator less than or equal to
n
n
n
:
0
=
p
0
q
0
<
1
n
=
p
1
q
1
<
⋯
<
1
1
=
p
M
(
n
)
q
M
(
n
)
.
0 = \frac{p_0}{q_0} < \frac{1}{n} = \frac{p_1}{q_1} < \cdots < \frac{1}{1} = \frac{p_{M(n)}}{q_{M(n)}}.
0
=
q
0
p
0
<
n
1
=
q
1
p
1
<
⋯
<
1
1
=
q
M
(
n
)
p
M
(
n
)
.
Let
k
k
k
be a positive integer. We define, for each
n
n
n
such that
M
(
n
)
≥
k
−
1
M(n) \geq k - 1
M
(
n
)
≥
k
−
1
,
f
k
(
n
)
=
min
{
∑
s
=
0
k
−
1
q
j
+
s
:
0
≤
j
≤
M
(
n
)
−
k
+
1
}
.
f_k(n) = \min \left\{ \sum_{s=0}^{k-1} q_{j+s} : 0 \leq j \leq M(n) - k + 1 \right\}.
f
k
(
n
)
=
min
{
s
=
0
∑
k
−
1
q
j
+
s
:
0
≤
j
≤
M
(
n
)
−
k
+
1
}
.
Determine, in function of
k
k
k
,
lim
n
→
∞
f
k
(
n
)
n
.
\lim_{n \to \infty} \frac{f_k(n)}{n}.
n
→
∞
lim
n
f
k
(
n
)
.
For example, if
n
=
4
n = 4
n
=
4
, the enumeration is
0
1
<
1
4
<
1
3
<
1
2
<
2
3
<
3
4
<
1
1
,
\frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1},
1
0
<
4
1
<
3
1
<
2
1
<
3
2
<
4
3
<
1
1
,
where
p
0
=
0
,
p
1
=
1
,
p
2
=
1
,
p
3
=
1
,
p
4
=
2
,
p
5
=
3
,
p
6
=
1
p_0 = 0, p_1 = 1, p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3, p_6 = 1
p
0
=
0
,
p
1
=
1
,
p
2
=
1
,
p
3
=
1
,
p
4
=
2
,
p
5
=
3
,
p
6
=
1
and
q
0
=
1
,
q
1
=
4
,
q
2
=
3
,
q
3
=
2
,
q
4
=
3
,
q
5
=
4
,
q
6
=
1
q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1
q
0
=
1
,
q
1
=
4
,
q
2
=
3
,
q
3
=
2
,
q
4
=
3
,
q
5
=
4
,
q
6
=
1
. In this case, we have
f
1
(
4
)
=
1
,
f
2
(
4
)
=
5
,
f
3
(
4
)
=
8
,
f
4
(
4
)
=
10
,
f
5
(
4
)
=
13
,
f
6
(
4
)
=
17
f_1(4) = 1, f_2(4) = 5, f_3(4) = 8, f_4(4) = 10, f_5(4) = 13, f_6(4) = 17
f
1
(
4
)
=
1
,
f
2
(
4
)
=
5
,
f
3
(
4
)
=
8
,
f
4
(
4
)
=
10
,
f
5
(
4
)
=
13
,
f
6
(
4
)
=
17
, and
f
7
(
4
)
=
18
f_7(4) = 18
f
7
(
4
)
=
18
.
5
1
Hide problems
when tr(A^n) is bounded?
Let
A
A
A
be a
2
×
2
2 \times 2
2
×
2
matrix with integer entries and
det
A
≠
0
\det A \neq 0
det
A
=
0
. If the sequence
tr
(
A
n
)
\operatorname{tr}(A^n)
tr
(
A
n
)
, for
n
=
1
,
2
,
3
,
…
n = 1, 2, 3, \ldots
n
=
1
,
2
,
3
,
…
, is bounded, show that A^{12} = I \text{or} (A^2 - I)^2 = O. Here,
I
I
I
and
O
O
O
denote the identity and zero matrices, respectively, and
tr
\operatorname{tr}
tr
denotes the trace of the matrix (the sum of the elements on the main diagonal).
4
1
Hide problems
Is there a parimpar polynomial?
We say that a function
f
:
R
→
R
f: \mathbb{R} \to \mathbb{R}
f
:
R
→
R
is morally odd if its graph is symmetric with respect to a point, that is, there exists
(
x
0
,
y
0
)
∈
R
2
(x_0, y_0) \in \mathbb{R}^2
(
x
0
,
y
0
)
∈
R
2
such that if
(
u
,
v
)
∈
{
(
x
,
f
(
x
)
)
:
x
∈
R
}
(u, v) \in \{(x, f(x)) : x \in \mathbb{R}\}
(
u
,
v
)
∈
{(
x
,
f
(
x
))
:
x
∈
R
}
, then
(
2
x
0
−
u
,
2
y
0
−
v
)
∈
{
(
x
,
f
(
x
)
)
:
x
∈
R
}
(2x_0 - u, 2y_0 - v) \in \{(x, f(x)) : x \in \mathbb{R}\}
(
2
x
0
−
u
,
2
y
0
−
v
)
∈
{(
x
,
f
(
x
))
:
x
∈
R
}
. On the other hand,
f
f
f
is said to be morally even if its graph
{
(
x
,
f
(
x
)
)
:
x
∈
R
}
\{(x, f(x)) : x \in \mathbb{R}\}
{(
x
,
f
(
x
))
:
x
∈
R
}
is symmetric with respect to some line (not necessarily vertical or horizontal). If
f
f
f
is morally even and morally odd, we say that
f
f
f
is parimpar.(a) Let
S
⊂
R
S \subset \mathbb{R}
S
⊂
R
be a bounded set and
f
:
S
→
R
f: S \to \mathbb{R}
f
:
S
→
R
be an arbitrary function. Prove that there exists
g
:
R
→
R
g: \mathbb{R} \to \mathbb{R}
g
:
R
→
R
that is parimpar such that
g
(
x
)
=
f
(
x
)
g(x) = f(x)
g
(
x
)
=
f
(
x
)
for all
x
∈
S
x \in S
x
∈
S
.(b) Find all polynomials
P
P
P
with real coefficients such that the corresponding polynomial function
P
:
R
→
R
P: \mathbb{R} \to \mathbb{R}
P
:
R
→
R
is parimpar.
3
1
Hide problems
easy coloring
Consider a game on an
n
×
n
n \times n
n
×
n
board, where each square starts with exactly one stone. A move consists of choosing
5
5
5
consecutive squares in the same row or column of the board and toggling the state of each of those squares (removing the stone from squares with a stone and placing a stone in squares without a stone). For which positive integers
n
≥
5
n \geq 5
n
≥
5
is it possible to end up with exactly one stone on the board after a finite number of moves?
2
1
Hide problems
Fixed point in cute polynomial
For each pair of integers
j
,
k
≥
2
j, k \geq 2
j
,
k
≥
2
, define the function
f
j
k
:
R
→
R
f_{jk} : \mathbb{R} \to \mathbb{R}
f
jk
:
R
→
R
given by
f
j
k
(
x
)
=
1
−
(
1
−
x
j
)
k
.
f_{jk}(x) = 1 - (1 - x^j)^k.
f
jk
(
x
)
=
1
−
(
1
−
x
j
)
k
.
(a) Prove that for any integers
j
,
k
≥
2
j, k \geq 2
j
,
k
≥
2
, there exists a unique real number
p
j
k
∈
(
0
,
1
)
p_{jk} \in (0, 1)
p
jk
∈
(
0
,
1
)
such that
f
j
k
(
p
j
k
)
=
p
j
k
f_{jk}(p_{jk}) = p_{jk}
f
jk
(
p
jk
)
=
p
jk
. Furthermore, defining
λ
j
k
:
=
f
j
k
′
(
p
j
k
)
\lambda_{jk} := f'_{jk}(p_{jk})
λ
jk
:=
f
jk
′
(
p
jk
)
, prove that
λ
j
k
>
1
\lambda_{jk} > 1
λ
jk
>
1
.(b) Prove that
p
j
k
j
=
1
−
p
k
j
p^j_{jk} = 1 - p_{kj}
p
jk
j
=
1
−
p
kj
for any integers
j
,
k
≥
2
j, k \geq 2
j
,
k
≥
2
.(c) Prove that
λ
j
k
=
λ
k
j
\lambda_{jk} = \lambda_{kj}
λ
jk
=
λ
kj
for any integers
j
,
k
≥
2
j, k \geq 2
j
,
k
≥
2
.
1
1
Hide problems
Aproximate ln(2) using perfect numbers
A positive integer
n
n
n
is called perfect if the sum of its positive divisors
σ
(
n
)
\sigma(n)
σ
(
n
)
is twice
n
n
n
, that is,
σ
(
n
)
=
2
n
\sigma(n) = 2n
σ
(
n
)
=
2
n
. For example,
6
6
6
is a perfect number since the sum of its positive divisors is
1
+
2
+
3
+
6
=
12
1 + 2 + 3 + 6 = 12
1
+
2
+
3
+
6
=
12
, which is twice
6
6
6
. Prove that if
n
n
n
is a positive perfect integer, then:
∑
p
∣
n
1
p
+
1
<
ln
2
<
∑
p
∣
n
1
p
−
1
\sum_{p|n} \frac{1}{p + 1} < \ln 2 < \sum_{p|n} \frac{1}{p - 1}
p
∣
n
∑
p
+
1
1
<
ln
2
<
p
∣
n
∑
p
−
1
1
where the sums are taken over all prime divisors
p
p
p
of
n
n
n
.