MathDB
Problems
Contests
National and Regional Contests
Canada Contests
Canada National Olympiad
2023 Canada National Olympiad
2023 Canada National Olympiad
Part of
Canada National Olympiad
Subcontests
(5)
5
1
Hide problems
Anticliques and maximum cut
A country with
n
n
n
cities has some two-way roads connecting certain pairs of cities. Someone notices that if the country is split into two parts in any way, then there would be at most
k
n
kn
kn
roads between the two parts (where
k
k
k
is a fixed positive integer). What is the largest integer
m
m
m
(in terms of
n
n
n
and
k
k
k
) such that there is guaranteed to be a set of
m
m
m
cities, no two of which are directly connected by a road?
4
1
Hide problems
Polynomial mapping set of divisors to set of divisors
Let
f
(
x
)
f(x)
f
(
x
)
be a non-constant polynomial with integer coefficients such that
f
(
1
)
≠
1
f(1) \neq 1
f
(
1
)
=
1
. For a positive integer
n
n
n
, define
divs
(
n
)
\text{divs}(n)
divs
(
n
)
to be the set of positive divisors of
n
n
n
.A positive integer
m
m
m
is
f
f
f
-cool if there exists a positive integer
n
n
n
for which
f
[
divs
(
m
)
]
=
divs
(
n
)
.
f[\text{divs}(m)]=\text{divs}(n).
f
[
divs
(
m
)]
=
divs
(
n
)
.
Prove that for any such
f
f
f
, there are finitely many
f
f
f
-cool integers.(The notation
f
[
S
]
f[S]
f
[
S
]
for some set
S
S
S
denotes the set
{
f
(
s
)
:
s
∈
S
}
\{f(s):s \in S\}
{
f
(
s
)
:
s
∈
S
}
.)
3
1
Hide problems
Inequality with circumcircle of foots in a triangle
An acute triangle is a triangle that has all angles less than
9
0
∘
90^{\circ}
9
0
∘
(
9
0
∘
90^{\circ}
9
0
∘
is a Right Angle). Let
A
B
C
ABC
A
BC
be an acute triangle with altitudes
A
D
AD
A
D
,
B
E
BE
BE
, and
C
F
CF
CF
meeting at
H
H
H
. The circle passing through points
D
D
D
,
E
E
E
, and
F
F
F
meets
A
D
AD
A
D
,
B
E
BE
BE
, and
C
F
CF
CF
again at
X
X
X
,
Y
Y
Y
, and
Z
Z
Z
respectively. Prove the following inequality:
A
H
D
X
+
B
H
E
Y
+
C
H
F
Z
≥
3.
\frac{AH}{DX}+\frac{BH}{EY}+\frac{CH}{FZ} \geq 3.
D
X
A
H
+
E
Y
B
H
+
FZ
C
H
≥
3.
2
1
Hide problems
Peer-pressuring students into buying tickets
There are 20 students in a high school class, and each student has exactly three close friends in the class. Five of the students have bought tickets to an upcoming concert. If any student sees that at least two of their close friends have bought tickets, then they will buy a ticket too.Is it possible that the entire class buys tickets to the concert?(Assume that friendship is mutual; if student
A
A
A
is close friends with student
B
B
B
, then
B
B
B
is close friends with
A
A
A
.)
1
1
Hide problems
Guessing a number based on divisibility
William is thinking of an integer between 1 and 50, inclusive. Victor can choose a positive integer
m
m
m
and ask William: "does
m
m
m
divide your number?", to which William must answer truthfully. Victor continues asking these questions until he determines William's number. What is the minimum number of questions that Victor needs to guarantee this?