4

Part of 2010 Tuymaada Olympiad

Problems(4)

Tuymaada 2010, Junior League, Problem 8

Source:

(I'll skip over the whole "dressing" of the graph in cities and flights [color=#FF0000][Mod edit: Shu has posted the "dressed-up" version below])
For an ordinary directed graph, show that there is a subset A of vertices such that:

1.

There are no edges between the vertices of A.

2.

v

, there is either a direct way from

v

to a vertex in A, or a way passing through only one vertex and ending in A (like

v

v'

a

a

is a vertex in A)

inductioncombinatorics unsolvedcombinatorics

Tuymaada 2010, Junior League, Problem 4

Source:

On a blackboard there are

2010

natural nonzero numbers. We define a "move" by erasing

x

y

y\neq0

and replacing them with

2x+1

y-1

, or we can choose to replace them by

2x+1

\frac{y-1}{4}

y-1

is divisible by 4.
Knowing that in the beginning the numbers

2006

2008

have been erased, show that the original set of numbers cannot be attained again by any sequence of moves.

combinatorics unsolvedcombinatoricsinvariant

[a n^2] is even for infinitely many n

Source: XVII Tuymaada Mathematical Olympiad (2010), Senior Level

Prove that for any positive real number

\alpha

\lfloor\alpha n^2\rfloor

is even for infinitely many positive integers

n

floor functionalgebrapolynomiallimitnumber theory unsolvednumber theory

Schoolchildren living in four cities

Source: Tuymaada 2010

In a country there are

4^9

schoolchildren living in four cities. At the end of the school year a state examination was held in 9 subjects. It is known that any two students have different marks at least in one subject. However, every two students from the same city got equal marks at least in one subject. Prove that there is a subject such that every two children living in the same city have equal marks in this subject.
Fedor Petrov

combinatorics unsolvedcombinatorics