The vertices of a connected graph cannot be coloured with less than colours (so that adjacent vertices have different colours).
Prove that edges can be removed from the graph so that it remains connected.

V. Dolnikov

EDIT. It is confirmed by the official solution that the graph is tacitly assumed to be finite.

Let be a positive integer larger than . Build an infinite set of subsets of having the following properties:

(a) any distinct sets of have exactly one common element;
(b) any distinct sets of have void intersection.

Prove that if is large enough, in every square that a natural number is written on each one of its cells, one can find a subsquare from the main square such that the sum of the numbers is this subsquare is divisible by .

Prove that if is large enough, then for each coloring of the subsets of the set with colors, two non-empty disjoint subsets and exist such that , and are of the same color.

Prove that if is large enough, among any points of plane we can find points such that these points have pairwise distinct distances. Can you prove the assertion for where is a positive real number instead of ?

Prove that for each coloring of the points inside or on the boundary of a square with colors, there exists a monochromatic regular hexagon.

Suppose is the smallest number such that if , for each coloring of the set with two colors there exists a monochromatic arithmetic progression of length . Prove that


.

Consider a set of points in plane. Prove that the number of isosceles triangles having their vertices among these points is . Find a configuration of points in plane such that the number of equilateral triangles with vertices among these points is .

Prove that from an grid, one can find points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of !

Arthur Morgan is playing a game.

He has eggs, each with a hardness value , where is a permutation of the set . He is throwing the eggs from an -floor building.

When the -th egg is dropped from the -th floor, its new hardness becomes
If , then the egg breaks and cannot be used again.

Arthur can drop each egg from a particular floor at most once.
For which values of and can Arthur always determine the correct ordering of the eggs according to their initial hardness values?
Note: The problem might be wrong or too easy