How many integers are there from 0 to 999999, in the decimal notation of which there are no two identical numbers next to each other?
Find the number of rectangles made up of the cells of a board with \(m\) horizontals and \(n\) verticals that contain a cell with the coordinates \((p, q)\).
Prove that there is no graph with five vertices whose degrees are equal to 4, 4, 4, 4, 2.
Prove that a graph, in which every two vertices are connected by exactly one simple path, is a tree.
Prove that, in a tree, every two vertices are connected by exactly one simple path.
Prove that there is a vertex in the tree from which exactly one edge emerges (such a vertex is called a hanging top).
At a conference there are 50 scientists, each of whom knows at least 25 other scientists at the conference. Prove that is possible to seat four of them at a round table so that everyone is sitting next to people they know.
Each of the 102 pupils of one school is friends with at least 68 others. Prove that among them there are four who have the same number of friends.
Each of the edges of a complete graph consisting of 6 vertices is coloured in one of two colours. Prove that there are three vertices, such that all the edges connecting them are the same colour.
Eugenie, arriving from Big-island, said that there are several lakes connected by rivers. Three rivers flow from each lake, and four rivers flow into each lake. Prove that she is wrong.