Problems(3)
St. Petersburg MO 2017 Grade 9 P7
Source: St. Petersburg MO 2017 Grade 9 P7
5/3/2018
Divide the upper right quadrant of the plane into square cells with side length . In this quadrant, cells are colored, show that there’re at least cells (possibly including the colored ones) that at least one of its neighbors are colored.
combinatorics
Deleting cycle in a directed graph preserving connectivity
Source: Saint Petersburg 2017
8/18/2017
In a country, some pairs of cities are connected by one-way roads. It turns out that every city has at least two out-going and two in-coming roads assigned to it, and from every city one can travel to any other city by a sequence of roads. Prove that it is possible to delete a cyclic route so that it is still possible to travel from any city to any other city.
combinatoricsgraph theoryRussiaPetersburg
St. Petersburg MO 2017 Grade 11 P7
Source: St. Petersburg MO 2017 Grade 11 P7
5/3/2018
Given a convex polygon with vertices at lattice points on a plane containing origin . Let be the set of vectors going from to the vertices of the polygon, and be the set of vectors going from to the lattice points that lie inside or on the boundary of the polygon (thus, is contained in .) Two grasshoppers jump on the whole plane: each jump of the first grasshopper shift its position by a vector from the set , and the second by the set . Prove that there exists positive integer that the following statement is true: if both grasshoppers can jump from to some point and the second grasshopper needs jumps to do it, then the first grasshopper can use at most jumps to do so.
combinatoricsnumber theory