MathDB

6

Part of 2015 Saint Petersburg Mathematical Olympiad

Problems(3)

All numbers occur exactly once

Source: St. Petersburg Olympiad 2015, 2nd Round, Grade 9, also known as Yellowstone Permutation

9/24/2016
A sequence of integers is defined as follows: a1=1,a2=2,a3=3a_1=1,a_2=2,a_3=3 and for n>3n>3, an=The smallest integer not occurring earlier, which is relatively prime to an−1 but not relatively prime to an−2.a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.Prove that every natural number occurs exactly once in this sequence.
M. Ivanov
number theoryrelatively prime
Bunches of roads

Source: St Petersburg Olympiad 2015, Grade 11, P6

10/17/2017
In country there are some cities, some pairs of cities are connected with roads.From every city go out exactly 100100 roads. We call 1010 roads, that go out from same city, as bunch. Prove, that we can split all roads in several bunches.
combinatoricsgraph theory
Removing Edges for Connected Subgraph

Source: St. Petersburg Mathematical Olympiad 2015 9.6

2/25/2016
There are 10201510^{2015} planets in an Intergalactic empire. Every two planets are connected by a two-way space line served by one of 20152015 travel companies. The Emperor would like to close kk of these companies such that it is still possible to reach any planet from any other planet. Find the maximum value of kk for which this is always possible.
(D. Karpov)
combinatoricsgraph theoryColoring