MathDB

7

Part of 2023 Saint Petersburg Mathematical Olympiad

Problems(2)

Bound of number of connected components

Source: St. Petersburg 2023 11.7

8/12/2023
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)?
combinatorics
Really weird combo geo

Source: St. Petersburg 2023 10.7

8/12/2023
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.
combinatorics