Problems

A graph is called Bipartite if it is possible to split all its vertices into two groups in such a way that there are no edges connecting vertices from the same group. Find out whic of the following graphs are bipartite and which are not:

Show that a bipartite graph with \(n\) vertices cannot have more than \(\frac{n^2}{4}\) edges.

Imagine you are a manager of a very special hotel, a hotel with an infinite number of rooms, where each room has a natural number on the door \(1,2,3,4,...\). Only one guest can stay in each room and in most cases the hotel will be initially full with no vacant rooms left.
You will have to deal with unusual situations that may occur.

Today we will solve some geometric problems using the triangle inequality. This is an inequality between the lengths of the sides of any triangle, or between the distances of any three points.

The shortest path between any two points \(A\) and \(B\) is a straight segment - every other path is longer. In particular, a path through another point, \(C\), is equal or longer. \[AC + BC \ge AB\] The triangle inequality says that the sum of lengths of any two sides of a triangle is always larger than the length of the third side. The inequality only becomes an equality if \(ABC\) is not actually a triangle and the point \(C\) lies on the segment from \(A\) to \(B\).

Even though it is a simple idea, it can be a really helpful tool in problem solving.

A set is a collection of objects of any specified kind, the objects are called elements or members, the objects in one set cannot repeat, namely \(\{1,2,3\}\) and \(\{1,2,2,2,3\}\) are identical sets. We denote a set by a capital letter \(A\), or \(B\) and write \(x\in A\) if \(x\) is an element of \(A\), and \(x\notin A\) if it is not. The notation \(A=\{a,b,c,...\}\) means that the set \(A\) consists of the elements \(a,b,c,...\). The empty or void set, \(\emptyset\), has no elements. If all elements of \(A\) are also in \(B\), then we call \(A\) a subset of \(B\) and we write \(A\subseteq B\). It is an axiom that the sets \(A\) and \(B\) are equal \(A=B\) if they have the same elements. Namely, \(A\) is a subset of \(B\) and \(B\) is a subset of \(A\) at the same time.
For any sets \(A\) and \(B\), we define their union \(A\cup B\), intersection \(A\cap B\), and the difference \(A-B\) as follows:

• the union \(A\cup B\) is the set of all elements that belong to \(A\) or \(B\);

• the intersection \(A\cap B\) is the set of elements that belong to both \(A\) and \(B\);

• the difference \(A-B\) consists of those \(x \in A\) that are do not belong to \(B\).

Sometimes it is useful to draw sets as Venn diagrams, on the diagram below the pink circle represents the set \(A\), the yellow circle represents the set \(B\), the orange part is the intersection \(A\cap B\), the pink part is \(A-B\), the yellow part is \(B-A\), and the whole picture is the union \(A\cup B\).

A circle is inscribed into the triangle \(ABC\) with sides \(BC=6, AC=10\) and \(AB= 12\). A line tangent to the circle intersects two longer sides of the triangle \(AB\) and \(AC\) at the points \(F\) and \(G\) respectively. Find the perimeter of the triangle \(AFG\).

Liam saw an unusual clock in the museum: the clock had no digits, and it’s not clear how the clock should be rotated. That is, we know that \(1\) is the next digit clockwise from \(12\), \(2\) is the next digit clockwise from \(1\), and so on. Moreover all the arrows (hour, minute, and second) have the same length, so it’s not clear which is which. What time does the clock show?

Two circles are tangent to each other and the smaller circle with the center \(A\) is located inside the larger circle with the center \(C\). The radii \(CD\) and \(CE\) are tangent to the smaller circle and the angle \(\angle DCE = 60^{\circ}\). Find the ratio of the radii of the circles.

For positive real numbers \(a,b,c\) prove the inequality: \[(a^2b + b^2c + c^2a)(ab^2 + bc^2 + ca^2)\geq 9a^2b^2c^2.\]

On a \(10\times 10\) board, a bacterium sits in one of the cells. In one move, the bacterium shifts to a cell adjacent to the side (i.e. not diagonal) and divides into two bacteria (both remain in the same new cell). Then, again, one of the bacteria sitting on the board shifts to a new adjacent cell, either horizontally or vertically, and divides into two, and so on. Is it possible for there to be an equal number of bacteria in all cells after several such moves?