MathDB
Problems
Contests
National and Regional Contests
Bulgaria Contests
Bulgaria National Olympiad
2021 Bulgaria National Olympiad
1
1
Part of
2021 Bulgaria National Olympiad
Problems
(1)
4n crossroads on boulevards
Source: Bulgaria NMO 2021 P1
5/16/2021
A city has
4
4
4
horizontal and
n
≥
3
n\geq3
n
≥
3
vertical boulevards which intersect at
4
n
4n
4
n
crossroads. The crossroads divide every horizontal boulevard into
n
−
1
n-1
n
−
1
streets and every vertical boulevard into
3
3
3
streets. The mayor of the city decides to close the minimum possible number of crossroads so that the city doesn't have a closed path(this means that starting from any street and going only through open crossroads without turning back you can't return to the same street).
a
)
a)
a
)
Prove that exactly
n
n
n
crossroads are closed.
b
)
b)
b
)
Prove that if from any street you can go to any other street and none of the
4
4
4
corner crossroads are closed then exactly
3
3
3
crossroads on the border are closed(A crossroad is on the border if it lies either on the first or fourth horizontal boulevard, or on the first or the n-th vertical boulevard).
combinatorics