4

Part of 1999 All-Russian Olympiad

Problems(2)

numbers 1 to 1000000 with color

Source:

Initially numbers from 1 to 1000000 are all colored black. A move consists of picking one number, then change the color (black to white or white to black) of itself and all other numbers NOT coprime with the chosen number. Can all numbers become white after finite numbers of moves? Edited by pbornsztein

searchcombinatorics unsolvedcombinatorics

infinite chessboard with moves

Source:

A frog is placed on each cell of a

n \times n

square inside an infinite chessboard (so initially there are a total of

n \times n

frogs). Each move consists of a frog

A

jumping over a frog

B

adjacent to it with

A

landing in the next cell and

B

disappearing (adjacent means two cells sharing a side). Prove that at least

\left[\frac{n^2}{3}\right]

moves are needed to reach a configuration where no more moves are possible.