8

Part of 2000 All-Russian Olympiad

Problems(3)

100 numbers around a circle

Source: All-Russian MO 2000

One hundred natural numbers whose greatest common divisor is

1

are arranged around a circle. An allowed operation is to add to a number the greatest common divisor of its two neighhbors. Prove that we can make all the numbers pairwise copirme in a finite number of moves.

number theorygreatest common divisormodular arithmeticrelatively primeRussia

Nailing Paper Squares

Source: All-Russian MO 2000

Some paper squares of

k

distinct colors are placed on a rectangular table, with sides parallel to the sides of the table. Suppose that for any

k

squares of distinct colors, some two of them can be nailed on the table with only one nail. Prove that there is a color such that all squares of that color can be nailed with

2k-2

combinatorics unsolvedcombinatorics

Coloring 100 x 100 array of points in four colors

Source: ARMO 2000

All points in a

100 \times 100

array are colored in one of four colors red, green, blue or yellow in such a way that there are

25

points of each color in each row and in any column. Prove that there are two rows and two columns such that their four intersection points are all in different colors.

LaTeXcombinatorics unsolvedcombinatorics