How many distinct trees with exactly 7 vertices are there? Here, a tree in graph theory refers to a connected graph without cycles, which can be simply understood as connecting nnn vertices with n−1n-1n−1 edges.
In a chess tournament, each of the eight participants played against every other participant. In case of a draw (and only in this case), the game was replayed exactly once, and the result of the replay was recorded in the table. Baron Munch…
In a plane, there are nnn identical gears positioned such that the first gear is meshed with the second, the second with the third, and so on, until the last nnn-th gear is meshed with the first. Can the gears in such a system rotat…
Elza draws 201320132013 cities on the map and connects some of them with NNN roads. Then Elza and Susy erase cities in turns until just two cities left (first city is to be erased by Elza). If these cities are connected with a road then Elza…
A rock travelled through an n x n board, stepping at each turn to the cell neighbouring the previous one by a side, so that each cell was visited once. Bob has put the integer numbers from 1 to n^2 into the cells, corresponding to the order…
A fly is sitting on one of the vertices of a) an octahedron; b) a cube. Can it crawl along all its edges exactly once and return to the starting vertex?
At a conference, there are nnn professors A1,A2,A3,⋯ ,AnA_{1}, A_{2}, A_{3}, \cdots, A_{n}A1,A2,A3,⋯,An participating. Prove: It is possible to divide these nnn individuals into two groups such that for each person AiA_{i}Ai, the number of people did_{i}di they know in…
In the country of Dumulandia, exactly 10 roads originate from each city, and each road connects exactly two cities. The network of roads was connected, meaning it was possible to travel from any city to any other city along the roads, possi…
Is it possible to arrange the numbers 1,2,…,121, 2, \ldots, 121,2,…,12 on a circle so that the difference between any two adjacent numbers is 3, 4, or 5?
Let GGG be a connected graph with kkk edges. Prove that it is possible to label the edges of GGG with the numbers 1,2,…,k1, 2, \ldots, k1,2,…,k in such a way that for every vertex incident to two or more edges, the greatest common divisor of the labels…
Let Zn\mathbb{Z}^nZn be the integer lattice in Rn\mathbb{R}^nRn . Two points in Zn\mathbb{Z}^nZn are called {\em neighbors} if they differ by exactly 1 in one coordinate and are equal in all other coordinates. For which integers n≥1n \geq 1n≥1…
Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?
On a 999×999999 \times 999999×999 board, a limp rook can move in the following way: From any square it can move to any of its adjacent squares, i.e., a square having a common side with it, and every move must be a turn, i.e., the directions of any two…
Prove that in any group of 12 people, you can find two people such that among the remaining 10 people, for each of them, at least 5 individuals either all know or do not know the initial pair of people.
There are nnn ministers, each of whom has issued a (unique) decree. To familiarize everyone with the decrees, the ministers send telegrams to each other. No two telegrams can be sent simultaneously. When a minister receives a telegram,…
The distance between two arbitrary vertices of a tree is defined as the length of the simple path connecting them. The remoteness of a vertex in a tree is defined as the sum of the distances from it to all other vertices. Prove that a tree…
In Flower City, each short man knows 6 little girls, and each little girl knows 6 short men. Prove that the number of short men in this city is equal to the number of little girls.
What minimum number of colours is sufficient to colour all positive real numbers so that every two numbers whose ratio is 4 or 8 have different colours?
The founder of a noble family received a plot of land. Each man in the family, upon his death, divided the land equally among his sons. If a man had no sons, the land was transferred to the state. No other family members gained or lost land…
In a round-robin tournament with 8 teams, each team plays one game against each other team, where each game results in one team winning and one team losing. No draws are allowed. What is the maximum number of teams that could be tied for th…