a. Prove that any graph without a kkk-clique that has a maximum number of edges is a complete (k−1)(k-1)(k−1)-partite graph. In other words, the graph can be partitioned into k−1k-1k−1 subsets of vertices such that each vertex is connected to all other…
In a certain country, any two cities are always connected by either an airline or a navigable canal (both ways). Show that it is possible to choose one mode of transportation so that, starting from any city, one can reach any other city usi…
After a Gobbit tournament, each person has played at least one game with each of the other participants. Each person writes on a sheet the names of the opponents they have defeated, as well as the people on the sheet of the defeated opponen…
Let d,r≥2d, r \geq 2d,r≥2 be integers satisfying d≥r2r+2d \geq r^{2r+2}d≥r2r+2, and let GGG be a graph that contains a collection H\mathcal{H}H of r2−1r^2 - 1r2−1 pairwise disjoint paths and a collection V={V1,…,Vd}\mathcal{V} = \{V_1, \ldots, V_d\}V={V1,…,Vd} of ddd pairwise disjoint…
Each face of a convex polyhedron is a triangle, and each edge is labeled with one of the letters aaa, bbb, or ccc, such that each face has all three letters each appearing exactly once on its edges. For each face, when the polyh…
a) The sum of the edge lengths of any convex polyhedron is greater than three times its diameter. Prove this. (The diameter of a polyhedron is the longest possible segment connecting two vertices of the polyhedron.) b) For any two vertices…
A new website registered 200020002000 people. Each of them invited 100010001000 other registered people to be their friends. Two people are considered to be friends if and only if they have invited each other. What is the minimum number of pairs of…
There are 100 participants in an international StarCraft championship. The tournament is single-elimination, meaning in each match, two players compete, the loser is eliminated, and the winner continues. Find the maximum possible number of…
In the Lemon Kingdom, there are 2020 villages. Some pairs of villages are directly connected by paved roads. The road network is arranged so that for any two villages, there is exactly one way to travel from one to the other without traveli…
From a 13×1313 \times 1313×13 chessboard, two opposite corner squares were removed. On the remaining part of the board, several squares were marked. Prove that kings can be placed on the marked squares such that the total number of kings is no more…
Given nnn points on a plane, where no three points are collinear, and some of these points are connected by line segments, let NkN_{k}Nk denote the number of complete graphs of kkk points. Prove that:…
12 chess players participated in a round-robin tournament. Afterwards, each player wrote 12 lists. The first list contains only himself, the (k+1)(k+1)(k+1)-th list contains the players from the kkk-th list and those who were defeated by any of the…
a) Prove that from a connected graph, several edges can be removed so that a tree remains. b) Prove that in a tree with nnn vertices, there are exactly n−1n-1n−1 edges. c) Prove that in a tree, there are at least two leaf vertices. d) Prove…
In a certain meeting, there are 30 participants. Each person knows at most 5 other people among the remaining participants; for any group of five people, at least two people are not acquainted with each other. Find the largest positive inte…
Each rational number is painted either white or red. Call such a coloring of the rationals sanferminera if for any distinct rationals numbers xxx and yyy satisfying one of the following three conditions: [list=1][] xy=1xy=1xy=1 , []…
Given a 15×1515 \times 1515×15 board, some pairs of centers of adjacent (sharing a side) cells are connected by line segments in such a way that a closed, non-self-intersecting polygonal chain is formed, symmetric with respect to one of the diago…
Lucky and Jinx were given a paper with 202320232023 points arranged as the vertices of a regular polygon. They were then tasked to color all the segments connecting these points such that no triangle formed with these points has all edges in th…
Given a finite sequence of 0s and 1s, it has the following properties: 1. If you extract any consecutive 5 digits from the sequence and any other consecutive 5 digits from the sequence, these 5 digits will not be the same (they can overlap…
Given that a spatial graph is composed of nnn points and lll connecting line segments such that: n=q2+q+1,l⩾12q(q+1)2+1,q⩾2,q∈N,n = q^{2} + q + 1, \quad l \geqslant \frac{1}{2} q(q + 1)^{2} + 1, \quad q \geqslant 2, \quad q \in \mathbf{N},n=q2+q+1,l⩾21q(q+1)2+1,q⩾2,q∈N, and it is known that any…
What is the minimum number of colors required to paint all the vertices, edges, and diagonals of a convex nnn-gon, given that the following two conditions must be met: 1. Any two segments emerging from the same vertex must be different col…