Is it possible to find a way of arranging numbers from \(0\) to \(9\) in a row so that each pair of consecutive numbers adds up to a multiple of \(5\), \(7\), or \(13\)?
A conference was attended by a finite group of scientists, some of whom are friends. It turned out that every two scientists, who have an equal number of friends at the conference, do not have friends in common. Prove that there is a scientist who has exactly one friend among the conference attendees.
Let’s prove the following statement: every graph without isolated vertices is connected.
Proof We use the induction on the number of vertices. Clearly the statement is true for graphs with \(2\) vertices. Now, assume we have proven the statement for graphs with up to \(n\) vertices.
Take a graph with \(n\) vertices by induction hypothesis it must be connected. Let’s add a non-isolated vertex to it. As this vertex is not isolated, it is connected to one of the other \(n\) vertices. But then the whole graph of \(n+1\) vertices is connected!
Let’s compute the infinite sum: \[1+2 + 4 + 8 + 16 + ... + 2^n + ... = c\] Observe that \(1+2+4+8+... = 1 + 2(1+2+4+8+16+...)\), namely \(c = 1+2c\), then it follows that \[c = 1+2+4+8+... = -1.\]
There are \(16\) cities in the kingdom. Prove that it is possible to build a system of roads in such a way that one can get from any city to any other without passing through more than one city on the way, and with at most five roads coming out of each city.
Show that a bipartite graph with \(n\) vertices cannot have more than \(\frac{n^2}{4}\) edges.
Thirteen boys and girls met to play a football match. Eleven of them shook hands with everybody else in the group. The last two shook hands with everybody else but not each other, because they were siblings and arrived together. How many handshakes took place?
The city of Konigsberg has seven bridges as depicted on the layout below. \[\includegraphics[scale=0.5]{https://problems-static.s3.amazonaws.com/production/task_images/2829/WSP-000146.png}\] Is it possible for the great mathematician Leonard Euler to have an excursion in Konigsberg visiting all islands and land banks, but crossing each bridge exactly once?
There are \(6\) people at a party. Each two people either know each other or not, and the knowledge goes both ways: if \(A\) knows \(B\), then \(B\) knows \(A\). Show that there either is a trio of people who all know each other or a trio of people who all don’t know each other.
An elven village in the woods has \(11\) treehouses. We want to link the houses by ropes so that each house is connected to exactly \(4\) others. How many ropes do we need?