Olympiad problems

2016 Croatia Team Selection Test, Problem 2

Tags: matrix , combinatorics , linear combination , Coloring , cauchy schwarz , Croatia , TST 2016

Let $N$ be a positive integer. Consider a $N \times N$ array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A [i]move[/i] consists of choosing a row or a column and changing the color of every cell in the chosen row or column. What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?

2016 Croatia Team Selection Test, Problem 2

Tags: matrix , combinatorics , linear combination , Coloring , cauchy schwarz , Croatia , TST 2016

Let $N$ be a positive integer. Consider a $N \times N$ array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A [i]move[/i] consists of choosing a row or a column and changing the color of every cell in the chosen row or column. What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?

2014 Belarusian National Olympiad, 4

Tags: combinatorics , TST , graph theory , Croatia , paths

There are $N$ cities in a country, some of which are connected by two-way flights. No city is directly connected with every other city. For each pair $(A, B)$ of cities there is exactly one route using at most two flights between them. Prove that $N - 1$ is a square of an integer.