We have a very large chessboard, consisting of white and black squares. We would like to place a stain of a specific shape on this chessboard and we know that the area of this stain is less than the area of one square of the chessboard. Show that it is always possible to place the stain in such a way that it does not cover a vertex of any square.
There are \(n\) straight lines on a plane, no two among them are parallel to each other. Show that some two of them cross at an angle less than \(\frac{180^{\circ}}{n}\).
You may have seen the pigeonhole principle before, sometimes called the Dirichlet principle. It says that if you have \(n\) pigeonholes, and more than \(n\) pigeons, and you put all of the pigeons into some pigeonhole, then there exists at least one pigeonhole with at least one pigeon. While it sounds quite simple, it’s a powerful technique. The difficult thing is often choosing the appropriate pigeons and pigeonholes.
It has multiple applications in various situations.
Today we will see how to use it in geometric problems.
There are thirteen boys and girls who met to play a football match. Eleven of them shook hands with everybody else in the group, but 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]{WSP-000146.png}\] Is it possible for a great mathematician Leonard Euler to have an excursion in Konigsberg visiting all islands and land banks, but crossing each bridge only 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.
Sometimes it is hard to rigorously formulate an intuitively correct reasoning. We might not know the proper words, the proper language, we might not have the right tools. Maths problems are not an exception. When we start learning to solve them, we know nothing about possible mathematical approaches and mathematical models. Today you will learn a very useful way to visualise information: you will learn how to represent information as a graph.
A graph is a finite set of points, some of which are connected with line segments. The points of a graph are called vertices. The line segments are called edges. In this problem set we only consider graphs in which every pair of vertices is connected with one or zero edges.
In a mathematical problem, one may use vertices of a graph to represent objects in the problem, i.e. people, cities, airports, etc, and edges of the graph represent relations between the objects such as mutual friendship, railways between cities, plane routes, etc. As you will see in the examples below, representing the initial problem as a graph can considerably simplify the solution.
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?
Can you draw a house like below without lifting a pen from the paper? \[\includegraphics[scale=0.75]{WSP-000149.png}\]
Last week eight heads of state, including 3 presidents, 3 prime ministers and 2 emperors got together for a conference. According to a reporter, each president shook hands with 6 heads of state, each prime minister shook hands with 4, and each emperor - with 1. Is this possible?