MathDB

4

Part of 2010 Saint Petersburg Mathematical Olympiad

Problems(3)

Substract primes

Source: St Petersburg Olympiad 2010, Grade 11, P4

9/14/2017
Natural number NN is given. Let pNp_N - biggest prime, that ≤N \leq N. On every move we replace NN by N−pNN-p_N. We repeat this until we get 00 or 11. If we get 11 then NN is called as good, else is bad. For example, 9595 is good because we get 95→6→195 \to 6 \to 1. Prove that among numbers from 11 to 10000001000000 there are between one quarter and half good numbers
number theory
Roads and cities

Source: St Petersburg Olympiad 2010, Grade 10, P4

9/14/2017
There are 20102010 cities in country, and 33 roads go from every city. President and Prime Minister play next game. They sell roads by turn to one of 33 companies( one road is one turn). President will win, if three roads from some city are sold to different companies. Who will win?
combinatorics
Big degree

Source: St Petersburg Olympiad 2010, Grade 9, P4

9/14/2017
AA -is 2020-digit number. We write 101101 numbers AA then erase last 1111 digits. Prove that this 20092009-digit number can not be degree of 22
number theory