MathDB

2023 Saint Petersburg Mathematical Olympiad

Part of Saint Petersburg Mathematical Olympiad

Subcontests

(7)
7
2

Bound of number of connected components

Let GG be a connected graph and let X,YX, Y be two disjoint subsets of its vertices, such that there are no edges between them. Given that G/XG/X has mm connected components and G/YG/Y has nn connected components, what is the minimal number of connected components of the graph G/(X∪Y)G/(X \cup Y)?

Really weird combo geo

Let ℓ1,ℓ2\ell_1, \ell_2 be two non-parallel lines and d1,d2d_1, d_2 be positive reals. The set of points XX, such that dist(X,ℓi)dist(X, \ell_i) is a multiple of did_i is called a <spanclass=′latex−italic′>grid</span><span class='latex-italic'>grid</span>. Let AA be finite set of points, not all collinear. A triangle with vertices in AA is called <spanclass=′latex−italic′>empty</span><span class='latex-italic'>empty</span> if no points from AA lie inside or on the sides of the triangle. Given that all empty triangles have the same area, show that AA is the intersection of a grid LL and a convex polygon FF.
6
2

Geo with reflections

Given is a triangle ABCABC. Let XX be the reflection of BB in ACAC and YY is the reflection of CC in ABAB. The tangent to (XAY)(XAY) at AA meets XYXY and BCBC at E,FE, F. Show that AE=AFAE=AF.

Graph with club flavortext

There are several gentlemen in the meeting of the Diogenes Club, some of which are friends with each other (friendship is mutual). Let's name a participant unsociable if he has exactly one friend among those present at the meeting. By the club rules, the only friend of any unsociable member can leave the meeting (gentlemen leave the meeting one at a time). The purpose of the meeting is to achieve a situation in which that there are no friends left among the participants. Prove that if the goal is achievable, then the number of participants remaining at the meeting does not depend on who left and in what order.
5
3

Iteration of a weird function

Let a>1a>1 be a positive integer and let f(n)=n+[a{n2}]f(n)=n+[a\{n\sqrt{2}\}]. Show that there exists a positive integer nn, such that f(f(n))=f(n)f(f(n))=f(n), but f(n)≠nf(n) \neq n.

Expression attains positive and negative values

Let x0,x1,…,xn−1,xn=x0x_0, x_1, \ldots, x_{n-1}, x_n=x_0 be reals and let f:R→Rf: \mathbb{R} \rightarrow \mathbb{R} be a function. The numbers yiy_i for i=0,1,…,n−1i=0,1, \ldots, n-1 are chosen such that yiy_i is between xix_i and xi+1x_{i+1}. Prove that ∑i=0n−1(xi+1−xi)f(yi)\sum_{i=0}^{n-1}(x_{i+1}-x_i)f(y_i) can attain both positive and negative values, by varying the yiy_i.

kn starts with d

For a positive integer nn and a nonzero digit dd, let f(n,d)f(n, d) be the smallest positive integer kk, such that knkn starts with dd. What is the maximal value of f(n,d)f(n, d), over all positive integers nn and nonzero digits dd?
4
2

Grid operations

What is the minimal number of operations needed to repaint a entirely white grid 100×100100 \times 100 to be entirely black, if on one move we can choose 9999 cells from any row or column and change their color?

Two-side grid with numbers

One side of a square sheet of paper is colored red, the other - in blue. On both sides, the sheet is divided into n2n^2 identical square cells. In each of these 2n22n^2 cells is written a number from 11 to kk. Find the smallest kk,for which the following properties hold simultaneously: (i) on the red side, any two numbers in different rows are distinct; (ii) on the blue side, any two numbers in different columns are different; (iii) for each of the n2n^2 squares of the partition, the number on the blue side is not equal to the number on the red side.
3
3
2
3
1
3