3

Part of 2016 All-Russian Olympiad

Problems(2)

Divisors of...divisors

Source: 2016 All-Russian Olympiad,Problem 9.3

Alexander has chosen a natural number

N>1

and has written down in a line,and in increasing order,all his positive divisors

d_1<d_2<\ldots <d_s

d_1=1

d_s=N

).For each pair of neighbouring numbers,he has found their greater common divisor.The sum of all these

s-1

numbers (the greatest common divisors) is equal to

N-2

.Find all possible values of

N

number theoryDivisorsgreatest common divisor

Triangles on the paper

Source: All russian olympiad 2016,Day1,grade 11,P3

We have sheet of paper, divided on

100\times 100

unit squares. In some squares we put rightangled isosceles triangles with leg =

1

( Every triangle lies in one unit square and is half of this square). Every unit grid segment( boundary too) is under one leg of triangle. Find maximal number of unit squares, that don`t contains triangles.