MathDB
Problems
Contests
National and Regional Contests
Brazil Contests
Brazil National Olympiad
2024 Brazil National Olympiad
2024 Brazil National Olympiad
Part of
Brazil National Olympiad
Subcontests
(6)
6
2
Hide problems
minimum sum in Farey sequence
Let
n
>
1
n > 1
n
>
1
be a positive integer. List in increasing order all the 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
1
=
p
0
q
0
<
p
1
q
1
<
⋯
<
p
M
q
M
=
1
1
.
\frac{0}{1} = \frac{p_0}{q_0} < \frac{p_1}{q_1} < \cdots < \frac{p_M}{q_M} = \frac{1}{1}.
1
0
=
q
0
p
0
<
q
1
p
1
<
⋯
<
q
M
p
M
=
1
1
.
Determine, in function of
n
n
n
, the smallest possible value of
q
i
−
1
+
q
i
+
q
i
+
1
q_{i-1} + q_i + q_{i+1}
q
i
−
1
+
q
i
+
q
i
+
1
, for
0
<
i
<
M
0 < i < M
0
<
i
<
M
.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
,
q
0
=
1
,
q
1
=
4
,
q
2
=
3
,
q
3
=
2
,
q
4
=
3
,
q
5
=
4
,
q
6
=
1
p_0 = 0, p_1 = 1, p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3, p_6 = 1, q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1
p
0
=
0
,
p
1
=
1
,
p
2
=
1
,
p
3
=
1
,
p
4
=
2
,
p
5
=
3
,
p
6
=
1
,
q
0
=
1
,
q
1
=
4
,
q
2
=
3
,
q
3
=
2
,
q
4
=
3
,
q
5
=
4
,
q
6
=
1
, and the minimum is
1
+
4
+
3
=
3
+
2
+
3
=
3
+
4
+
1
=
8
1 + 4 + 3 = 3 + 2 + 3 = 3 + 4 + 1 = 8
1
+
4
+
3
=
3
+
2
+
3
=
3
+
4
+
1
=
8
.
hidden configuration
Let
A
B
C
ABC
A
BC
be an isosceles triangle with
A
B
=
B
C
AB = BC
A
B
=
BC
. Let
D
D
D
be a point on segment
A
B
AB
A
B
,
E
E
E
be a point on segment
B
C
BC
BC
, and
P
P
P
be a point on segment
D
E
DE
D
E
such that
A
D
=
D
P
AD = DP
A
D
=
D
P
and
C
E
=
P
E
CE = PE
CE
=
PE
. Let
M
M
M
be the midpoint of
D
E
DE
D
E
. The line parallel to
A
B
AB
A
B
through
M
M
M
intersects
A
C
AC
A
C
at
X
X
X
and the line parallel to
B
C
BC
BC
through
M
M
M
intersects
A
C
AC
A
C
at
Y
Y
Y
. The lines
D
X
DX
D
X
and
E
Y
EY
E
Y
intersect at
F
F
F
. Prove that
F
P
FP
FP
is perpendicular to
D
E
DE
D
E
.
5
2
Hide problems
f(x^2 y - y) = f(x)^2 f(y) + f(x)^2 - 1
Let
R
\mathbb{R}
R
be the set of real numbers. Determine all functions
f
:
R
→
R
f: \mathbb{R} \to \mathbb{R}
f
:
R
→
R
such that, for any real numbers
x
x
x
and
y
y
y
,
f
(
x
2
y
−
y
)
=
f
(
x
)
2
f
(
y
)
+
f
(
x
)
2
−
1.
f(x^2 y - y) = f(x)^2 f(y) + f(x)^2 - 1.
f
(
x
2
y
−
y
)
=
f
(
x
)
2
f
(
y
)
+
f
(
x
)
2
−
1.
Sequence of quadratic equations
Esmeralda chooses two distinct positive integers
a
a
a
and
b
b
b
, with
b
>
a
b > a
b
>
a
, and writes the equation
x
2
−
a
x
+
b
=
0
x^2 - ax + b = 0
x
2
−
a
x
+
b
=
0
on the board. If the equation has distinct positive integer roots
c
c
c
and
d
d
d
, with
d
>
c
d > c
d
>
c
, she writes the equation
x
2
−
c
x
+
d
=
0
x^2 - cx + d = 0
x
2
−
c
x
+
d
=
0
on the board. She repeats the procedure as long as she obtains distinct positive integer roots. If she writes an equation for which this does not occur, she stops. a) Show that Esmeralda can choose
a
a
a
and
b
b
b
such that she will write exactly 2024 equations on the board. b) What is the maximum number of equations she can write knowing that one of the initially chosen numbers is 2024?
4
2
Hide problems
prove that two circles and a line have a common point
Let
A
B
C
ABC
A
BC
be an acute-angled scalene triangle. Let
D
D
D
be a point on the interior of segment
B
C
BC
BC
, different from the foot of the altitude from
A
A
A
. The tangents from
A
A
A
and
B
B
B
to the circumcircle of triangle
A
B
D
ABD
A
B
D
meet at
O
1
O_1
O
1
, and the tangents from
A
A
A
and
C
C
C
to the circumcircle of triangle
A
C
D
ACD
A
C
D
meet at
O
2
O_2
O
2
. Show that the circle centered at
O
1
O_1
O
1
passing through
A
A
A
, the circle centered at
O
2
O_2
O
2
passing through
A
A
A
, and the line
B
C
BC
BC
have a common point.
how many trilegal numbers with 10 digits?
A number is called trilegal if its digits belong to the set
{
1
,
2
,
3
}
\{1, 2, 3\}
{
1
,
2
,
3
}
and if it is divisible by
99
99
99
. How many trilegal numbers with
10
10
10
digits are there?
3
2
Hide problems
largest k increasing path that is garanteed
The numbers from
1
1
1
to
100
100
100
are placed without repetition in each cell of a
10
×
10
10 \times 10
10
×
10
board. An increasing path of length
k
k
k
on this board is a sequence of cells
c
1
,
c
2
,
…
,
c
k
c_1, c_2, \ldots, c_k
c
1
,
c
2
,
…
,
c
k
such that, for each
i
=
2
,
3
,
…
,
k
i = 2, 3, \ldots, k
i
=
2
,
3
,
…
,
k
, the following properties are satisfied: • The cells
c
i
c_i
c
i
and
c
i
−
1
c_{i-1}
c
i
−
1
share a side or a vertex; • The number in
c
i
c_i
c
i
is greater than the number in
c
i
−
1
c_{i-1}
c
i
−
1
.What is the largest positive integer
k
k
k
for which we can always find an increasing path of length
k
k
k
, regardless of how the numbers from 1 to 100 are arranged on the board?
minimum number of bisector in a convex polygon
Let
n
≥
3
n \geq 3
n
≥
3
be a positive integer. In a convex polygon with
n
n
n
sides, all the internal bisectors of its
n
n
n
internal angles are drawn. Determine, as a function of
n
n
n
, the smallest possible number of distinct lines determined by these bisectors.
2
2
Hide problems
number of separated partitions for n+1 is equal the number of partitions for n
A partition of a set
A
A
A
is a family of non-empty subsets of
A
A
A
, such that any two distinct subsets in the family are disjoint, and the union of all subsets equals
A
A
A
. We say that a partition of a set of integers
B
B
B
is separated if each subset in the partition does not contain consecutive integers. Prove that, for every positive integer
n
n
n
, the number of partitions of the set
{
1
,
2
,
…
,
n
}
\{1, 2, \dots, n\}
{
1
,
2
,
…
,
n
}
is equal to the number of separated partitions of the set
{
1
,
2
,
…
,
n
+
1
}
\{1, 2, \dots, n+1\}
{
1
,
2
,
…
,
n
+
1
}
.For example,
{
{
1
,
3
}
,
{
2
}
}
\{\{1,3\}, \{2\}\}
{{
1
,
3
}
,
{
2
}}
is a separated partition of the set
{
1
,
2
,
3
}
\{1,2,3\}
{
1
,
2
,
3
}
. On the other hand,
{
{
1
,
2
}
,
{
3
}
}
\{\{1,2\}, \{3\}\}
{{
1
,
2
}
,
{
3
}}
is a partition of the same set, but it is not separated since
{
1
,
2
}
\{1,2\}
{
1
,
2
}
contains consecutive integers.
prove that 4 points lie on the same circle
Let
A
B
C
ABC
A
BC
be a scalene triangle. Let
E
E
E
and
F
F
F
be the midpoints of sides
A
C
AC
A
C
and
A
B
AB
A
B
, respectively, and let
D
D
D
be any point on segment
B
C
BC
BC
. The circumcircles of triangles
B
D
F
BDF
B
D
F
and
C
D
E
CDE
C
D
E
intersect line
E
F
EF
EF
at points
K
≠
F
K \neq F
K
=
F
, and
L
≠
E
L \neq E
L
=
E
, respectively, and intersect at points
X
≠
D
X \neq D
X
=
D
. The point
Y
Y
Y
is on line
D
X
DX
D
X
such that
A
Y
AY
A
Y
is parallel to
B
C
BC
BC
. Prove that points
K
K
K
,
L
L
L
,
X
X
X
, and
Y
Y
Y
lie on the same circle.
1
2
Hide problems
Find all a_1 that make the sequence eventually periodic, and all periods
Let
a
1
a_1
a
1
be an integer greater than or equal to 2. Consider the sequence such that its first term is
a
1
a_1
a
1
, and for
a
n
a_n
a
n
, the
n
n
n
-th term of the sequence, we have
a
n
+
1
=
a
n
p
k
e
k
−
1
+
1
,
a_{n+1} = \frac{a_n}{p_k^{e_k - 1}} + 1,
a
n
+
1
=
p
k
e
k
−
1
a
n
+
1
,
where
p
1
e
1
p
2
e
2
⋯
p
k
e
k
p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}
p
1
e
1
p
2
e
2
⋯
p
k
e
k
is the prime factorization of
a
n
a_n
a
n
, with
1
<
p
1
<
p
2
<
⋯
<
p
k
1 < p_1 < p_2 < \cdots < p_k
1
<
p
1
<
p
2
<
⋯
<
p
k
, and
e
1
,
e
2
,
…
,
e
k
e_1, e_2, \dots, e_k
e
1
,
e
2
,
…
,
e
k
positive integers.For example, if
a
1
=
2024
=
2
3
⋅
11
⋅
23
a_1 = 2024 = 2^3 \cdot 11 \cdot 23
a
1
=
2024
=
2
3
⋅
11
⋅
23
, the next two terms of the sequence are
a
2
=
a
1
2
3
−
1
+
1
=
2024
4
+
1
=
2025
=
3
4
⋅
5
2
;
a_2 = \frac{a_1}{2^{3-1}} + 1 = \frac{2024}{4} + 1 = 2025 = 3^4 \cdot 5^2;
a
2
=
2
3
−
1
a
1
+
1
=
4
2024
+
1
=
2025
=
3
4
⋅
5
2
;
a
3
=
a
2
5
2
−
1
+
1
=
2025
5
+
1
=
406.
a_3 = \frac{a_2}{5^{2-1}} + 1 = \frac{2025}{5} + 1 = 406.
a
3
=
5
2
−
1
a
2
+
1
=
5
2025
+
1
=
406.
Determine for which values of
a
1
a_1
a
1
the sequence is eventually periodic and what all the possible periods are.Note: Let
p
p
p
be a positive integer. A sequence
x
1
,
x
2
,
…
x_1, x_2, \dots
x
1
,
x
2
,
…
is eventually periodic with period
p
p
p
if
p
p
p
is the smallest positive integer such that there exists an
N
≥
0
N \geq 0
N
≥
0
satisfying
x
n
+
p
=
x
n
x_{n+p} = x_n
x
n
+
p
=
x
n
for all
n
>
N
n > N
n
>
N
.
sequence with prime factors
Consider a sequence whose first term is a given positive integer
N
>
1
N > 1
N
>
1
. Consider the prime factorization of
N
N
N
. If
N
N
N
is a power of 2, the sequence consists of a single term:
N
N
N
. Otherwise, the second term of the sequence is obtained by replacing the largest prime factor
p
p
p
of
N
N
N
with
p
+
1
p + 1
p
+
1
in the prime factorization. If the new number is not a power of 2, we repeat the same procedure with it, remembering to factor it again into primes. If it is a power of 2, the numerical sequence ends. And so on.For example, if the first term of the sequence is
N
=
300
=
2
2
⋅
3
⋅
5
2
N = 300 = 2^2 \cdot 3 \cdot 5^2
N
=
300
=
2
2
⋅
3
⋅
5
2
, since its largest prime factor is
p
=
5
p = 5
p
=
5
, the second term is
2
2
⋅
3
⋅
(
5
+
1
)
2
=
2
4
⋅
3
3
2^2 \cdot 3 \cdot (5 + 1)^2 = 2^4 \cdot 3^3
2
2
⋅
3
⋅
(
5
+
1
)
2
=
2
4
⋅
3
3
. Repeating the procedure, the largest prime factor of the second term is
p
=
3
p = 3
p
=
3
, so the third term is
2
4
⋅
(
3
+
1
)
3
=
2
10
2^4 \cdot (3 + 1)^3 = 2^{10}
2
4
⋅
(
3
+
1
)
3
=
2
10
. Since we obtained a power of 2, the sequence has 3 terms:
2
2
⋅
3
⋅
5
2
2^2 \cdot 3 \cdot 5^2
2
2
⋅
3
⋅
5
2
,
2
4
⋅
3
3
2^4 \cdot 3^3
2
4
⋅
3
3
, and
2
10
2^{10}
2
10
. a) How many terms does the sequence have if the first term is
N
=
2
⋅
3
⋅
5
⋅
7
⋅
11
⋅
13
⋅
17
⋅
19
⋅
23
N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23
N
=
2
⋅
3
⋅
5
⋅
7
⋅
11
⋅
13
⋅
17
⋅
19
⋅
23
? b) Show that if a prime factor
p
p
p
leaves a remainder of 1 when divided by 3, then
p
+
1
2
\frac{p+1}{2}
2
p
+
1
is an integer that also leaves a remainder of 1 when divided by 3. c) Present an initial term
N
N
N
less than 1,000,000 (one million) such that the sequence starting from
N
N
N
has exactly 11 terms.