Electronic manual on discrete mathematics. Scientific forum dxdy. Theorem on the parity of the number of odd vertices

Hello, I am using this forum to check the following proof. In general, this problem is , but I heard that schoolchildren solve it at the Olympiad.

Task.
There are 100 cities in the country, some pairs of cities are connected by roads. For any four cities there are at least two roads between them. It is known that there is no route that passes through each city exactly once.
Prove that it is possible to choose two cities in such a way that any of the remaining cities is connected by a road to at least one of the two chosen cities.

Proof.
Cities are peaks. Ribs are roads.

Let's find out whether the graph can be disconnected. If there are more than 3 components, then we will select 2 vertices from one, one from the other and another from the third. It turns out that they can be connected by at most one edge. The condition of the problem is violated.
Let there be two components, each consisting of more than one vertex. Then they should all be full. If this is not the case, then take two non-adjacent vertices from the first, and any two from the other. Only two cities can be connected in such a set. Contradiction. The same goes for the other component. So both are full. Well then, take any one vertex from the first and any one from the second component. The condition of the task is fulfilled.
Now let one component be just one vertex of degree 0. Then it turns out that the other component will be made up of 99 vertices. If we remove more than two edges from any vertex, then the condition is immediately violated: we take a vertex of degree 0, a vertex without two edges, and vertices to which there are no edges from it (there will be 1 edge). This means that only one edge can be removed from each vertex. But if you do this, then each vertex will have an odd degree (before each one had 98). And there can only be an even number of odd degrees, so either we remove somewhere two edges and the restriction about 4 cities is violated, or we leave all the edges and then there is a complete vertex.

We will call cities from which there are roads to all other cities q and p.

Next, we prove by induction that for any connected graph with the constraint of 4 cities and a path, the condition will be satisfied.
Base. of 4 vertices is obvious: take any spanning tree and choose a vertex in it that is different from a leaf, and the second one is a leaf.

Transition. Let there be a graph of vertices. Then for all graphs smaller size, for which the conditions of the problem are satisfied, everything is proven.

It is necessary to prove that the induction hypothesis can be used.
Let's name the vertex that will be thrown out as .
If there is a graph from a vertex, where for any 4 cities there must be two roads, then this should also be true for cities: we will consider all cities without one. The main thing is that the graph does not lose connectivity, and this can always be done by removing only the hanging vertex, if there is one.

If it turned out that a r.path was formed, then it could not be connected to one of its ends (otherwise the g.path in the graph). So, for deletion, it is a hanging vertex in the spanning tree. If it turns out that this is still not possible: it was connected through one vertex to the end that was removed, then we will remove the other. At the same time, it could not happen that a vertex is connected through one vertex to both of the ends: it would be a graph on 3 vertices (and if there is a second path to the end, then there is a r.path), and this can be proven for graphs with more than for 4 vertices.
Obviously, by removing a hanging vertex in a spanning tree, connectivity is not lost.

Now it has been proven that if there is any graph, double. condition, then you can select a vertex, after removing which a smaller graph will be obtained that satisfies the original condition. This means that we can use the inductive hypothesis.

Now there is a connected to a graph of vertices, this country of cities has its own p and q. It is clear that if there is an edge from to p or q, then there is no need to prove anything. Then let there be no roads from to p and to q.
The set to which there are roads from p will be called A, and the set to which there are roads from q will be called B.
Let there be no road from p to q. Then let the city not be connected by road to the city. But then it must have roads in both p and q, otherwise we take the vertices , , p and q.
Then it turns out that the city cannot but be connected by roads with cities from
But then you can make the city new p, and leave q the same (or vice versa).

This means that there is only one case left: p and q are connected by a road.
We will leave the names of the sets the same.
By the induction hypothesis: the graph does not have a Hamiltonian path.
Once again, if there are roads from to the entire set or to everything, then everything has already been proven.

Now there is a pair of vertices and from which there are no edges to .
If there is only , then it covers everything that q does not cover, then p. Then - a new big city.
If empty, then it is connected to and everything is proven.

If there is no edge between and, then we take , , and p - there will be one edge. So it exists. Now it turns out that - a complete subgraph, however, as well as (otherwise we take or, p or q, as necessary, and unconnected vertices).
Now consider the subgraph on vertices from . Let's try to cover the entire set of vertices using simple paths.
Let the result be a covering of only 4 simple paths. Let's take one extreme vertex from each: if there is an edge, then we could connect two extreme vertices and get a longer path. The result was an anti-clique on four peaks. Contradiction.
It is now known that the set is covered by at most 3 simple paths. We will consider each simple one as one vertex: if you can come to any of the ends, then you can go along each vertex inside it once - it is also simple, and this can be done, because each vertex from can be reached through both p and q. Now there are only no more than 3 vertices.
A path may consist of one vertex or more. If more, then we identify the entire path with one extreme vertex.
Let's call the left set - , the right - , the middle - (the paths are compressed into vertices).
You can forget about the vertex: if it turns out that there is an r.path, then there will already be a contradiction with the inductive assumption.
Case 1. The middle set is empty. Then we simply (by vertices simply) go around the left set, starting from any vertex other than , we end in , then in p , then immediately q , then in and just go around the right set. It turned out to be a city path.
Case 2. The middle set has one vertex. Everything is the same, but from p to q we pass through this vertex.
Case 3. Now there are vertices in the middle set

1. The board has the shape of a cross, which is obtained if the corner squares are removed from a $4 \times 4$ square board. Is it possible to bypass it by moving a chess knight and return to the original square, having visited all the squares exactly once?
2. In the country of Digit there are 9 cities with names 1, 2, 3, 4, 5, 6, 7, 8, 9. A traveler discovered that two cities are connected by an airline if and only if two-digit number, made up of the numbers-names of these cities, is divided by 3. Is it possible to get from city 1 to city 9?
3. There are 15 telephones in the town of Malenky. Is it possible to connect them with wires so that each phone is connected to exactly five others?
4. There are 100 cities in the state, and each of them has 4 roads. How many roads are there in the state?
5. There are 30 people in the class. Could it be that 9 of them have 3 friends (in this class), 11 have 4 friends, and 10 have 5 friends?
6. There are 15 telephones in the town of Malenky. Is it possible to connect them with wires so that there are 4 telephones, each of which is connected to three others, 8 telephones, each of which is connected to six, and 3 telephones, each of which is connected to five others?
7. The king has 19 vassal barons. Could it be that each vassal barony has 1, 5 or 9 neighboring baronies?
8. Can a state in which there are 3 roads leading out of each city have exactly 100 roads?
9. John, having arrived from Disneyland, said that there were 7 islands on the enchanted lake, with 1, 3 or 5 bridges leading from each of them. Is it true that at least one of these bridges necessarily goes to the shore of the lake?
10. Prove that the number of people who have ever lived on Earth and made an odd number of handshakes is even.
11. Is it possible to draw 9 segments on a plane so that each one intersects exactly three others?
12. There are 15 cities in the country of Seven, each of which is connected by roads to at least 7 others. Prove that from any city you can get to any other (possibly by passing through other cities).
13. Prove that a graph with $n$ vertices, each of which has degree at least $(n - 1)/2$, is connected.
14. In the Far Far Away Kingdom there is only one type of transport - a flying carpet. There are 21 carpet lines leaving the capital, one from the city of Dalniy, and 20 from all other cities. Prove that it is possible to fly from the capital to Dalniy (possibly with transfers).
15. In the country, every city has 100 roads, and from any city you can get to any other. One road was closed for repairs. Prove that now you can get from any city to any other.
16. a) Given a piece of wire 120 cm long. Is it possible, without breaking the wire, to make the frame of a cube with an edge of 10 cm?
    b) What is the least number of times the wire will have to be broken in order to still produce the required frame?
17. Prove that a graph in which any two vertices are connected by exactly one simple path is a tree.
18. Prove that any two vertices in a tree are connected by exactly one simple path.
19. Prove that there is a vertex in the tree from which exactly one edge emerges (such a vertex is called a hanging vertex).
20. All vertices in the graph have degree 3. Prove that it contains a cycle.
21. Prove that removing any edge from a tree turns it into a disconnected graph.
22. There are 101 cities in the country of Drevland, and some of them are connected by roads. Moreover, any two cities are connected by exactly one path. How many roads are there in this country?
23. Prove that a connected graph whose number of edges is one less than the number of vertices is a tree.
24. The volleyball net has the shape of a rectangle measuring $50 \times 600$ cells. Which greatest number Can the strings be cut so that the mesh does not fall into pieces?
25. In a certain country there are 30 cities, each connected to each by a road. What is the largest number of roads that can be closed for repairs so that it is possible to travel from each city to each?
26. Prove that in any connected graph you can remove a vertex along with all the edges coming from it so that it remains connected.
27. There are 100 cities in the country, some of which are connected by airlines. It is known that from any city you can fly to any other (possibly with transfers). Prove that you can visit every city in no more than
    a) 198 flights;
    b) 196 flights.
28. In the country of Ozernaya there are 7 lakes connected to each other by 10 canals, and from any lake you can swim to any other. How many islands are there in this country?
29. We marked 20 points in the square and connected them with non-intersecting segments to each other and to the vertices of the square so that the square was divided into triangles. How many triangles did you get?
30. A graph that has 5 vertices, each of which is connected by an edge to any other, is not planar.
31. Is it possible to build three houses, dig three wells and connect each house with each well with paths so that the paths do not intersect?
32. Prove that a graph with 10 vertices, each of degree 5, is not planar.
33. Prove that a planar graph has a vertex whose degree does not exceed 5.
34. Each edge of a complete graph with 11 vertices is colored one of two colors: red or blue. Prove that either the "red" or the "blue" graph is not planar.
35. The heptagon is divided into convex pentagons and hexagons, and in such a way that each of its vertices is a vertex in at least two partition polygons. Prove that the number of pentagons in the partition is at least 13.

2. Solve the following graph traversal problem:

A certain country has a capital and 100 other cities. Some cities (including the capital) are connected by one-way roads. Each non-capital city has 20 roads, and each such city has 21 roads. Prove that it is impossible to get to the capital from any city.

Let a road enter the capital. Then total number"incoming" roads are equal to 21 100 +a, and the total number of "outgoing" roads is no more

20 100 + (100-a ). Therefore, 21 100 + a 20 100 + (100 – a), that is, 2a 0.

Thus a = 0.

3.3.2.1. Digraph G1 (V,E): V=(a, b, c, d, e, f), is defined as an algebraic system.

a) For the given relation, define the digraph geometrically. b) Construct the digraph adjacency matrix.

0) R = ((a, b), (b, a), (b, c), (c, b), (c, a), (a, c), (d, e), (e, d) );

1) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (c, a), (a, c) );

2) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (d, e), (e, d) );

3) R = ((a, b), (b, c), (a, c), (b, e), (c, f), (c, d), (d, f), (f, e) );

4) R = ((b, c), (a, d), (b, a), (d, c), (b, d), (c, a), (f, d), (f ,c) );

5) R = ((b, a), (a, a), (b, c), (c, d), (d, c), (d, b), (d, a), (d, e) );

6) R = ((a, b), (a, c), (a, d), (c, a), (d, e), (e, d), (c, c), (d, b) );

7) R=((b, a), (c, c), (a, d), (c, a), (d, e), (e, c), (d, b), (e, f) );

8) R = ((a, b), (a, c), (a, d), (e, a), (d, e), (e, d), (c, b), (d, d) );

9) R = ((a, e), (a, a), (a, d), (c, a), (d, e), (d, d), (c, c), (b, d) ).

3.3.2.2. The digraph is defined geometrically. Specify the valency of the vertices.

8) 1

3.3.2.3. The adjacency matrix of the digraph is given. a) Define the digraph geometrically, c) construct an incidence matrix.

        

001100

001000

3.3.2.4. The incidence matrix of the digraph is given. a) Define the digraph geometrically, c) construct an adjacency matrix.

3.3.2.5. Solve the following graph traversal problems:

0) Dima, having arrived from Vrunland, said that there are several lakes there, connected by rivers. Three rivers flow out of each lake, and four rivers flow into each lake. Prove him wrong.

1) In a certain state, every city is connected to every road. The crazy king wants to introduce one-way traffic on the roads so that once you leave any city, you cannot return to it. Is it possible to do this?

2) It is said that in a company of five people, each person knows two others. Is such a company possible?

3) Some state has 101 cities. All cities are connected by one-way roads, with 50 roads entering each city and 50 roads leaving each city. Prove that you can get from any city to any other by driving along no more than two roads.

4) There are 6 points given on a plane such that no three of them lie on the same straight line. Each pair of dots is connected by a blue or red line. Prove that among the given points it is possible to choose three such that all sides of the triangle formed by them are painted the same color.

5) Some state has 101 cities. Some cities are connected by one-way roads, with 40 roads entering each city and 40 roads leaving each city. Prove that you can get from any city to any other by driving along no more than three roads.

6) Is it possible to create 10 bus routes in a city and install stops on them so that no matter which 8 routes are taken, there is a stop that does not lie on any of them, and any 9 routes pass through all the stops.

7) A beetle crawls along the edges of a cube. Will he be able to traverse all edges sequentially, passing each edge exactly once? Hint: Think about the question: how many times can a beetle visit each vertex?

8) The artist painted the picture "The outline of a square and its diagonals." Could he draw his picture without lifting his pencil from the paper or drawing the same line twice? Instruction: An even number of lines must emanate from each point, with the exception of the beginning and end of the pencil path.

9) Arkady, Boris. Vladimir, Grigory and Dmitry shook hands when they met (each shook hands with each other once). How many handshakes were done?

3.3.2.6. Solve the following graph traversal problems:

0) The Uryupinsk metro consists of three lines and has at least two terminal stations and at least two transfer nodes, and none of the terminal stations is a transfer station. You can change from each line to each in at least two places. Draw an example of such a subway diagram, if you know that this can be done without lifting the pencil from the paper and without drawing the same segment twice. Note: Don't forget that there are ring lines.

3) The board has the shape of a cross, which is obtained by removing the corner squares from a 4 × 4 square board. Is it possible to bypass it by moving a chess knight and return to the original square, having visited all squares exactly once?

4) A pedestrian walked around six streets of one city, walking through each exactly twice, but could not get around them, walking through each only once. Could this be?

5) There is a beetle sitting in the center of the 3 3 3 cube. Prove that, crawling over the edges, he cannot go around all the cubes 1 1 1 once.

6) In a 6x6 square, several cells are marked so that from any marked one you can go to any other marked one, passing only through the common sides of the marked cells. A marked cell is called an end cell if it borders on the side of exactly one marked cell. Mark several cells so that you get a) 10, b) 11, c) 12 cells.

7) A fly sits at one of the vertices of a) an octahedron b) a cube. Can she crawl along all his ribs exactly once and return to

original vertex? (Note: An octahedron is two quadrangular pyramids glued together at the bases.)

8) How, without lifting the pencil from the paper, draw six segments in such a way that 16 points located at the vertices of a 4 by 4 square grid are crossed out?

9) Is it possible to draw a diagonal in each square on the surface of a Rubik's cube so that a non-self-intersecting path is obtained? Note: There are only 54 squares on the surface of a Rubik's cube.

3.4. Optimization problems on graphs

If an arc of a directed graph G 1 (V ,E) is associated with some real number a (u ,v ), called a weight, then the sequence of vertices v 0 ,v 1 ,...,v p defines a path in G 1 and its length

is defined as the sum of the weights:

If in any

In the graph, the weight of each arc is equal to one, then the length of the path is equal to the number of arcs. The shortest path problem most often arises when solving

transport and discrete problems dynamic programming etc. Length shortest path denote r (v i,v j) and are called the distance from v i to v j (the distance can be negative). For any digraph one can construct distance matrix R=r(i, j). The matrix is ​​filled in row by row, selecting the vertex on the left (right). The value is the smallest number of arcs connecting the vertex on the left to one of the vertices in the row.

If there is no path from v i to v j , then we set r (v i ,v j ) = . If each contour of our graph has a positive length, then the shortest path will always be an elementary path, i.e. there will be no repetitions in the sequence v 1 ,...,v p.

The average deviation of vertex vi from the center of the graph D(vi) is equal to:

D(vi )1 r(vi , v),

m v V

where m is the number of arcs in the graph, v runs through the vertices of the graph, n is the number of vertices in the graph, i = 1..n.

The vertex for which D(vi ) turns out to be minimal is called the center of the graph (several vertices are possible - the center of the graph).

By way or route on a graph G1 (V,E) is the sequence of its vertices and edges v1e1v2e2v3…vnen vn+1, in which

any two adjacent elements are incident. A path is called simple if the silver and all the vertices on it, except the first and last, are different.

A route is called a chain if all its edges are different. A route is called a simple chain if all its vertices, and therefore its edges, are different.

A cycle in a graph is a path in which the initial vertex coincides with the final vertex and which contains at least one edge.

A cycle is called simple if it does not have identical vertices except the first and last, i.e. if the vertices are different.

If a graph has no cycles, then it is called acyclic.

Now we can define the concept of a tree differently. A connected graph without cycles is called a tree.

Examples of completing tasks

D(2)=D(3)=6/8=3/4;

So, the center of the graph is vertices 2 and 3.

2. The village is built in the form of a square of 3 blocks by 3 blocks (blocks are squares with side b, 9 blocks in total). What is the shortest distance the asphalt paver must travel to pave all the streets if it starts and ends its path at corner point A? (The sides of the square are also streets).

Rice. 6. Shortest path

It is clear that the length of the asphalt paver route is at least 24, since it must pass along each street at least once. Let us prove that he will have to drive along at least four streets twice. An odd number of streets intersect at exactly eight intersections.

Therefore, any circular paver route must travel twice on at least 8/2 = 4 streets. The minimum length of a paver route is 28; One of the possible routes is shown in Figure 6.

3. Define the graph geometrically and solve the problem:

Running out into the yard after school, each student threw a snowball at exactly one other student. Prove that all students can be divided into three teams so that members of one team do not throw snowballs at each other.

Let's mark the schoolchildren on the plane with dots and connect them with an arrow if one threw at the other. The resulting picture will look like several cycles with “horns” (paths leading from a point to a cycle). Each such figure can be easily divided into three groups: breaking the cycle, we place one student in the first group, and the resulting trees are divided into even and odd vertices.

Tasks for independent completion

3.4.1. Write down: 1) any path that is not a chain; 2) chain and simple chain; 3) loop, simple loop, if any.

3.4.2. The digraph is defined geometrically. Construct a distance matrix. Calculate the center of the digraph.

EULER GRAPHS.

Prove that a complete set of dominoes can be laid out according to the domino rules.

"Lemma about round dances." In some company, each person has exactly two friends. Prove that if all friends join hands, they will form one or more round dances.

There are more than 101 cities in the country. The capital is connected by airlines to 100 cities, and each city except the capital is connected to exactly ten cities (the airline operates in both directions). It is known that from any city you can get to any other (maybe with transfers). Prove that it is possible to close half of the airlines coming from the capital, so that the ability to get from any city to any will remain.

Prove that a connected graph with 2n odd vertices can be drawn by lifting the pencil from the paper exactly n–1 times and without drawing any edge twice.

In the country, 3 railways leave from each city. Two companies want to privatize them all. The Antimonopoly Committee requires that roads of both companies exit from each city. Prove that companies can agree among themselves so that the Antimonopoly Committee's requirement is met.

Given a connected graph G with k edges. Prove that it is possible to number the edges with all the numbers 1, 2, ..., k so that for each vertex of degree at least two, the set of numbers that mark the edges from this vertex has a gcd equal to 1.

In a football tournament held among 20 teams from different cities, each team played one match at home and no more than two matches away. Prove that it was possible to schedule the games so that each team played no more than one game per day and the entire tournament would be played in three days.

HAMILTON COUNT.

A closed eight-link broken line is drawn on the surface of the cube, the vertices of which coincide with all the vertices of the cube. What is the smallest number of links of this broken line that can coincide with the edges of the cube?

A cube is made from eight small cubes. Is it possible, starting from the center of a large cube and moving along the edges of small cubes, to go around all the vertices of small cubes, visiting each exactly once?

Given a board 55. Can a knight go around all the squares, visiting each square once, and return to its original position?

Is it possible to move a lame king (a king cannot move along diagonals) all the squares of a chessboard, starting in the lower left corner and ending in the upper right corner?

Can a knight make 8 moves and return to its original square, having visited all the horizontal and vertical lines of the chessboard?

A). Black and white chips are placed on two squares of the chessboard. You are allowed to move them in turn, each move moving the next chip to any free adjacent field vertically or horizontally. As a result of such moves, can all possible positions of these two chips occur on the board, and exactly once? b). What if you are allowed to move the chips in any order (not necessarily one by one)?

Which of the following three facts is the “strongest”?

In some state, every 2 cities are connected by a road. Each road is only allowed to move in one direction. Prove that there is a city from which you can travel around the entire state, visiting each city exactly once.

In a certain country, every city is connected to every city by a one-way road. Prove that there is a city from which you can get to any other.

In a certain state there are 100 cities and each is connected to each by a one-way road. Prove that it is possible to change the direction of movement on one road so that you can get from any city to any other.

Prove the “strongest” fact and both consequences from it.

In a one-round chess tournament, each participant played one game against each other. Prove that the participants can be numbered in such a way that none of them loses to the one immediately next to him by number.

There are N cities in the country. Between any two of them there is either a road or Railway. A tourist wants to travel around the country, visiting each city exactly once, and return to the city from which he began the trip. Prove that a tourist can choose the city from which he will start his journey and the route so that he will have to change the mode of transport no more than once. (All-Russian Olympiad, 2003)

A sequence of 36 zeros and ones starts with 5 zeros. Among the fives in a row, all 32 possible combinations are found. Find the last five digits of the sequence.

"Knights in the Court of King Arthur" - Dirac's theorem. 2n knights gathered at King Arthur’s round table, each of whom has no more than (n–1) enemies among the others. Prove that the king's advisor Merlin can seat the knights in such a way that the enemies will not sit nearby. State Dirac's theorem in general form.

2n people came to the conference, each of whom knows at least n others. Prove that participants can be accommodated in double rooms so that people who know each other live in each room.

Given n chips of several colors, with no more than n/2 chips of each color. Prove that they can be placed on a circle so that no two pieces of the same color stand next to each other.

IN federal state, consisting of two republics, each two cities are connected by a one-way road; At the same time, moving along the roads, you can get from any city to any other. Tourist agency"Hamilton" offers n various tourist routes by city of the first republic and m– by city, the second (any of these routes involves visiting each city of the republic exactly once and returning to the original city, and all this without leaving the republic). Prove that the Hamilton agency could offer no less than mn similar tourist routes in cities throughout the federation.

Tournaments – full graphs.

There are 28 students in the class. The teacher can change students, but each student within school day sits with the same student. In what minimum number of days will each student be able to sit with each other?

The sum of 1000 real numbers is 0. Prove that at least 999 pairwise sums of these numbers are non-negative.

There are 25 stones in a pile. It is divided into two parts, then one of the parts is again divided into two, etc., until you get 25 separately lying stones. Each time one of the piles is divided into two parts, the product of the numbers of stones in these parts is written on the board. Prove that at the end the sum of all the numbers on the board will be equal to 300.

There are 1996 children studying at the school. Each of them likes exactly k of the remaining 1,995 students. At what values k can we say that there will definitely be two students from this school who either both like each other or both don’t like each other?

An astronomer observes 50 stars, the sum of the pairwise distances between them is equal to S. A cloud came up and obscured 25 stars. Prove that the sum of pairwise distances between visible stars is less than S/2.

In a country with 25 cities, three airlines want that for any pair of cities, all nonstop flights between those cities must be operated by only one of the airlines, but any airline can fly passengers from any city to any other with a stop in no more than one intermediate city . Prove that it is feasible.

The commission consists of 49 people. Exactly three commission members participate in each meeting. Is it possible to schedule the work of a commission so that any two members of the commission meet at meetings exactly once?

MINIMUM CONNECTIVITY.

In city N, you can travel from any metro station to any other (possibly with transfers). Prove that one of the metro stations can be closed for repairs without the right to travel through it, so that from any of the remaining stations it is possible to travel to any other.

Prove that in any connected graph you can remove a vertex along with all the edges coming from it so that it remains connected.

In a group of several people, some people know each other and some do not. Every evening one of them arranges a dinner for all his friends and introduces them to each other. After each person had hosted at least one dinner, it turned out that some two people still did not know each other. Prove that they won’t be able to meet each other at the next dinner either.

In a certain country there are 30 cities, and each city is connected to each by road. What is the largest number of roads that can be closed for repairs so that one can travel from each city to each, possibly passing through other cities?

A model of an decagon is made from wire, from one vertex of which all the diagonals are drawn. Two people take turns snacking on one wire. The winner is the one after whose move the model first splits into two parts. Who wins when proper game: the one who goes first, or his partner?

Initially, on each square of the board 1n there is a checker. The first move is to move any checker to an adjacent cell (one of two, if the checker is not on the edge), so that a column of two checkers is formed. Then, in the next move, each column can be moved in any direction by as many cells as there are checkers in it (within the board); If a column lands on a non-empty cell, it is placed on top of the column standing there and merges with it. Prove that in n-1 moves you can collect all the checkers on one cell.

There are 101 cans of canned food with masses of 1001 g, 1002 g, ..., 1101 g. The labels with the scales have been lost, but it seems to the caretaker that he remembers which can weighs how much. He wants to make sure of this in the least number of weighings. There are two pan scales: one is precise, the other is coarse. In one weighing you can compare two cans. Accurate scales they always show which can is heavier, and rough ones only if the difference is more than 1g (otherwise they show equilibrium). The caretaker can only use one scale. Which ones should he choose? (A. Shapovalov)

The volleyball net has the shape of a rectangle with dimensions of 50600 cells. What is the largest number of single ropes (between knots) that can be cut so that the mesh does not fall into pieces?

There is a rope mesh in the form of an 88 square, divided into 11 cells. What is the longest rope that can be cut from it? (You can cut off any end of the knots without disturbing the connection of the rest, but you cannot cut the knot so that no ends are formed).

The notebook sheet was colored in 23 colors according to the cells. A pair of colors is called good if there are two adjacent cells painted with these colors. What is the minimum number of good pairs?

Let's call a labyrinth an 8x8 chessboard where partitions are inserted between some fields. If the rook can go around all the squares without jumping over the partitions, then the maze is called good, otherwise it is called bad. Which labyrinths are there more - good or bad?

There are 100 cities in the country, some of which are connected by airlines. It is known that from any city you can fly to any other (possibly with transfers). Prove that you can visit every city by doing no more than: a). 198 flights; b). 196 flights.

On a chessboard, initially empty, pawns are placed according to following rules: Any four empty squares are selected, the centers of which are the vertices of a rectangle with sides parallel to the sides of the board, after which a pawn is placed on one of these squares. Then similar four empty cells are selected, a pawn is placed on one of them again, and so on. What is the largest number of pawns that can be placed on the board following these rules?

The hostess baked a pie for the guests. There can be either p or q people at the table. For what minimal amount pieces (not necessarily equal), you need to cut the pie in advance so that in any case it can be distributed equally among the guests if: a). p and q are relatively prime; b). do p and q have a greatest common divisor d?

The secret object is an 88 square in plan, divided by corridors into 11 squares. At each vertex of such a square there is a switch. The click of the switch immediately affects all meter-long corridors emerging from this peak, changing their illumination to the opposite. The watchman is in the corner of a completely unlit object. He can only walk along illuminated corridors and flip switches any number of times. Can a watchman ensure that he can pass from any switch to any other without flipping the switches?

In a connected graph 2 n vertices, and all of them are of degree 3. Prove that it is possible to choose this way n+1 edge, so that the correct coloring in 3 colors of the selected edges uniquely determines the correct coloring in 3 colors of all edges of the graph (the coloring is correct if two edges with a common vertex have different colors).

BIPARITE GRAPHS.

Prove that a graph is bipartite if and only if all cycles in it are even.

Prove that a tree (a connected graph without cycles) is a bipartite graph.

In a certain group of people, everyone has one enemy and one friend. Prove that these people can be divided into two companies so that in each company there will be neither enemies nor friends.

There are 16 teams playing in the Russian Football Championship. In the first round, all teams played one game. In the second round, all teams also played a game. Prove that it is possible to identify 8 teams such that no two of them played each other.

On a sheet of checkered paper there is a certain finite set M of nodes. Is it always possible to color some points of the set M in White color, and the rest - in red so that on each grid line the difference between the number of white and red nodes in absolute value does not exceed 1? (IMO, 1986)

There are 1997 points given on the plane. Two people take turns connecting these points with segments, and one segment cannot be drawn twice. The loser is the one whose move first creates a closed broken line with an odd number of links. Who will win if played correctly?

We took 10 points on the circle. What is the largest number of segments with ends at these points that can be drawn such that no three of these segments form a triangle with vertices at these points?

In the village of Martyshkino, every boy, all the girls he knows know each other. Every girl knows more boys than girls among her friends. Prove that there are no fewer boys living in Martyshkino than girls.

Hydras consist of heads and necks (any neck connects exactly two heads). With one blow of the sword you can cut off all the necks coming out of some head A of the hydra. But at the same time, from the head of A, one neck instantly grows into all the heads with which A is not connected. Hercules defeats the hydra if he manages to cut it into two parts not connected by their necks. Find the smallest N at which Hercules can defeat any hundred-necked hydra with no more than N blows. (RosOl, 2002)

In a company of 2n+1 people, for any n people there will be a person different from them who is familiar with each of them. Prove that there is a person in this company who knows everyone. (RosOl, 2002)

FLAT GRAPHS.

There are 5 points on a plane, no three of which lie on the same line. Prove that some four of them lie at the vertices of a convex quadrilateral.

There are 5 circles on a plane, every two of which intersect. Prove that any three of them have a common point.

There are 6 points on the plane (3 blue and 3 red), no three of which lie on the same straight line. Prove that some 2 blue and 2 red points lie at the vertices of a convex quadrilateral.

On a checkered field there is a complete set of dominoes (each domino occupies 2 squares). Let's call region many cells that were hit same numbers dominoes. Let's call the area liaison, if from any of its cells a lame rook can get into any other. What is the largest number of connected areas that can be on the field?

PARTIAL ORDER.

There are 12 girls and 12 boys in the class, all of different heights. During the physical education lesson, they were lined up in two lines (one behind the other): boys - by height from left to right, and girls - by height from right to left. Then the taller one was called out from each boy-girl pair. Prove that you have called the twelve highest students.

Several different natural numbers are given. It is known that among any three of them, two can be chosen so that one is divisible by the other. Prove that all numbers can be colored in two colors so that for any two numbers of the same color, one is divisible by the other.

Prove that out of 17 different natural numbers, either there are 5 numbers a, b, c, d, e such that each of the numbers of this five, except the last one, is divisible by the number behind it, or there are five such numbers that none one of them is not divisible by the other.

The numbers 1, 2, 3, ..., 101 are arranged in a row in some order. Prove that you can always cross out 90 numbers from this series so that the remaining 11 are arranged in ascending or descending order.

ALGORITHMS.

Prove that the vertices in a spanning tree can be colored in a checkerboard pattern.

In a group of people, everyone knows someone. Prove that this group can be divided into two so that each person has an acquaintance from the other group.

In the village, some houses are connected by wires. Neighbors are two people whose houses are connected by wires. Will it always be possible to place one person in each house - a liar or a knight - so that everyone can answer the question: “Are there any liars among your neighbors?” – answered positively. (Everyone knows about each of his neighbors, whether he is a liar or not).

Prove that at the vertices of a polyhedron one can place integers so that in every two vertices connected by an edge there are numbers that are not coprime, and in every two vertices not connected by an edge there are coprime numbers.

IN Port Aventura 16 secret agents were abandoned. Each of them monitors some of their colleagues. It is known that if an agent A keeps an eye on the agent IN, then the agent IN does not follow the agent A. Any 10 agents can be renumbered in such a way that the first monitors the second, the second – the third, ..., the tenth – the first. Prove that some 11 agents can be numbered in the same way.

At what n you can color all the edges n-carbon prism (base – n-gons) in three colors so that at each vertex edges of all three colors meet and each face (including the bases) has edges of all three colors?

A). Prove that the vertices of a 3n-gonal prism can be colored with three colors so that each vertex is connected by edges to vertices of all three colors. b). Prove that if the vertices of an n-gonal prism can be colored with three colors so that each vertex is connected by edges with vertices of all three colors, then n is divisible by 3.

"ANTIGRAPH".

In a company of 2n+1 people, for any n people there will be a person different from them who is familiar with each of them. Prove that there is a person in this company who knows everyone.

GRAPHS AND POLYNOMIALS.

Given a natural number k and polynomials R(x) And S(x) with integer coefficients. It is known that for any integer x number R(S(x)) – x divided by k. Prove that the number S(R(x)) – x is also divisible by k for any whole x.

Are there four polynomials such that the sum of any three of them has at least one root, and the sum of any two has no roots?

CYCLICITY.

IN flower city 2000 shorties live. Every shorty gives a gift to every friend of his every day. To avoid ruin, the gift can be given further, but not to the person who gave you the gift. Znayka calculated that none of the gifts given to him on Friday could be returned to him earlier than the next Friday. Prove that some short guy has no more than 13 friends. (E. Cherepanov)

There are 100 cities in the state. Some pairs of cities are connected by roads, with at least four cyclic routes. Prove that there is a cyclic route passing through no more than 51 cities.

There are 100 cities in the country, some pairs of cities are connected by roads, with a total of 200 roads. It turned out that any cyclic route has a length of at least five. Prove that there are two disjoint cyclic routes.

There are a lot of elevators in the building of Moscow University, and each elevator transports passengers only between some two floors (but on each floor you can go to any elevator that stops on it). It is known that you can travel from any floor to any other using even number elevators, and without going through any floor twice. Prove that if desired, the same thing can be done using an odd number of elevators.

In the land of Oz there are several castles, from each of which there are three paths. The wandering knight left his ancestral castle and set out on a journey around the country. The knight loves variety, so when he reaches the next castle, he turns left each time if he turned right the previous time, and turns right if he turned left before. (When passing the first castle on his way, the knight can turn in any direction). Prove that someday the knight will return to his castle.

An endless sequence of numbers from 1 to 9 is printed on an endless tape. Prove that either some combination of numbers will be repeated 10 times in a row, or 10 hundred-digit numbers can be cut from it in descending order.

THEOREM ON THE PARITY OF THE NUMBER OF ODD VERTS.

The vertices of a convex polyhedron, all of whose faces are triangles, were painted in three colors. Prove that the number of faces whose three vertices are all different colors is even.

Number of ribs.

On a white sheet of checkered paper, draw a square measuring 1212. Two cells are considered adjacent if they have common side. Sasha paints one cell at a time, entering into each painted cell the number of its previously painted neighbors. What will be the sum of all the numbers when all the cells are colored? (A. Shapovalov)

We painted an endless sheet of checkered paper, except for a 77 square. In this square, Vasya colored a cell in which exactly one adjacent (on the side) cell is colored, then another cell in which now exactly one adjacent cell is colored, and so on. Which greatest number Can Vasya paint the cells this way?

At what n>1 it may happen that in a company from n+1 girls and n boys all girls are familiar with different numbers boys, and all boys with the same number of girls?

MIXTURE.

Attended some meeting n Human. It is known that every two acquaintances do not have any common acquaintances, and every two strangers have exactly two common acquaintances. A). Prove that everyone present has the same number of acquaintances. b). At what n possible condition of the problem?

In the city of "Diversity" there live 10,000 inhabitants, every two of whom are either at enmity or friends with each other. Every day, no more than one city resident can “start new life", i.e. quarrel with all your friends and make friends with all your enemies; Moreover, any three residents can become friends with each other. To prove that all residents, without exception, can make friends with each other. What is the smallest number of days that is sure to be sufficient for this?

k And n– natural numbers greater than 1. In a group of kn each person is familiar with more than ( k–1)n from the rest. Prove that you can choose k+1 person so that they all know each other. ( Polish Olympics, 68)

There are 100 points marked on the plane. Two people play and take turns. In one move, you can connect two points with an arrow if they have not been connected before. In this case, it is forbidden to draw an arrow, after which it will be possible to get from any point using the arrows to any other. The one who cannot make another move without breaking the rules loses. Who wins if the game is played correctly: the one who goes first or his partner? ( YES. Rostovsky)

In One-Sided County, there are one-way roads between some (but unfortunately not all) estates. Moreover, when any new road(also with one-way traffic) between estates not connected by a road before, it turns out that you can get from any estate to any other without breaking the rules. Prove that such an opportunity exists now. ( YES. Rostovsky; St. Petersburg, city 2000)

Met several friends. Each of them shook hands with everyone except Fedot Burcheev, who, being out of sorts, shook hands with some and not with others. A total of 197 handshakes were made. How many handshakes did Fedot make? ( I.S. Rubanov)

There are 100 cities in the country, and each city has at least one road. Prove that it is possible to close several roads so that there is still at least one road leading out of each city, and at the same time at least 67 cities have exactly one road leading out of them. ( E.A. Girsh, S.V. Ivanov, D.V. Karpov)

The school has 40 classrooms that can be opened with 5 keys different types, and the number of keys of different types is different. All 40 keys were locked in the rooms, so that in each room there was one key that could not be used to open that room. The watchman Sergeev has a duplicate key to one of the rooms. Prove that he can open all the rooms. ( )

The school has 40 classrooms that can be opened with 4 different types of keys. All 40 keys were locked in the rooms so that in each room there was one key locked that could not be used to open that room. The watchman Sergeev knows where each key is. Prove that the watchman Sergeev can make duplicate keys for two offices, with which you can open all the rooms. ( R.A. Ismailov, S.L. Berlov, D.V. Karpov)

(S. Berlov, St. Petersburg, city, 2001, 6-1) At a cat show, 19 cats and 10 male cats sat in a row, and next to each cat sat a cat that was fatter than she was. Prove that next to each cat sat a cat that was thinner than him.

(S. Berlov)The square continent is divided into 19 countries in the form of convex polygons, and there are no points at which the borders of four or more countries. Of any three borders that converge at one point, one is closed, and two are open to travel. Prove that it is impossible to travel around all these countries, visiting each one once and return to the original country.

In the country of Falkersonia, some cities are connected by airlines, and it is impossible to get from city A to city B with less than ten transfers. Prove that all airlines can be sold to 11 airlines in such a way that any route from A to B will pass along lines owned by all 11 companies. (Folklore, 100)

Each student in the class is involved in two clubs, and for every three students there is a club that they go to together. Prove that there is a club in which all students study. (Olympiad DalFO 2001, 104)

. Ten people came to visit in galoshes. They left one by one, and each put on a random pair of galoshes that he could fit into (that is, no smaller than his own). What is the largest number of people who could not put on galoshes?

IN fairyland Perra Terra, among other inhabitants, is home to carabasses and barabasses. Each Karabas is familiar with six Karabas and nine Barabas. Each drum is familiar with ten carabasses and seven drums. Who is more numerous in this country - Karabas or Barabas?

In a group of 100 people, among any three there is a person who knows both of the others. Prove that from this group you can choose a company of 50 people in which everyone knows each other. (S. Berlov)

20 gentlemen came to the club: some with hats, some without. Then, from time to time, one of the gentlemen took off his hat and put it on the head of another gentleman, who at that moment did not have a hat. An hour later, 10 gentlemen said: “I gave away a hat more often than I received!” How many gentlemen came to the club wearing hats? ( SLB, Yu.M. Lifshits; SPb-02)

In a certain company there are more than 10 people, and each person’s number of acquaintances is divided by 10. Prove that there are at least 11 people with the same amount acquaintances ( SLB based on Moldova)

At the Olympiad, 8 (6) problems were proposed. Each participant solved exactly 3 of them, and no two participants solved more than one common task. What is the largest number of participants at the Olympiad? ( Baltic Way, 01)

For a company from n a person fulfills the following condition: if any 2 people have an equal number of acquaintances, then each of the others is acquainted with exactly one of them. At what n is it possible? ( Baltic Way, 2000)

19 guests came to the party. Among any 3 of them there are 2 acquaintances. Prove that guests can be divided into 5 groups, in each of which everyone knows each other in pairs. ( V.L. Dolnikov, SLB, SVI)

(Folklore) There are several cities and several one-way roads in the country. Each road connects two cities and does not pass through the others. At the same time, no matter which two cities you take, you can drive from at least one of them to the other without violating traffic rules. Prove that there is a city from which you can drive to any other without breaking traffic rules.

Among 11 people, any two have exactly one common friend. Prove that at least one of them knows all the others.

(Lapok) Among 5 people, any two have exactly one common friend. Prove that at least one of them knows all the others.

(Jurybased on classic facts) There are 120 cities in the country. Some pairs of cities are connected by roads that do not pass through other cities. Every city has at least three roads. Prove that there is a non-self-intersecting cyclic route consisting of at most 11 cities.

(Yu.M. Lifshits) In the country of Jurland, some cities are connected by roads (not passing through other cities), and from any city you can get to any other. One unfortunate day, an evil tribe of subchiks captured a certain city. Every next day, the subchiks either captured a city adjacent to one of the captured ones, or liberated a captured city, all neighboring ones were captured. Moreover, no city was captured more than once. Prove that if the subchiks can no longer capture anything, then from any two neighboring cities at least one has been captured.

(Yu.M. Lifshits) 14 jury members were present at the banquet and drank 17 bottles of lemonade. Four members of the jury drank each bottle of lemonade. Prove that there are two jury members who did not drink lemonade from the same bottle.

(Folklore) Each of the 7 team members has no more than two close friends. Once in the same room, two close friends begin to chat incessantly, and all work in this room stops. Prove that three rooms are enough for the captain to ensure the smooth functioning of the entire team.

(Yu.M. Lifshits) 10 chess players played a one-round tournament, and each won, lost and drew 3 games. It is known that there are no three chess players who scored exactly 1 point in matches against each other. Prove that all ten chess players can be placed in a circle so that each of them beats the one standing to his right. For a victory in chess, 1 point is given, for a draw, 0.5 points are given, and for a loss, 0 points.

(Yu.M. Lifshits) 10 chess players played a one-round tournament, and each won and lost 4 games and tied one game. Prove that you can choose three chess players and place them in a circle so that each of them beats the one standing to his right.

Octopuses live in the Sea of ​​Rains, each with one or two friends. When the Sun rose, all those octopuses who had two friends turned blue, and all those who had one friend turned red. It turned out that any two friends are different colors. Then 10 blue octopuses were repainted red, and at the same time 12 red octopuses were repainted red. Blue colour, after which any two friends became the same color. How many octopuses are there in the Sea of ​​Rains?

There are 12 pillars in the yard. Electrician Petrov was given the task of connecting the poles with wires in such a way that each wire connected exactly two poles, no two poles would be connected twice, and, most importantly, that for any four poles there would be exactly three wires stretched between these poles. Prove that electrician Petrov will not be able to cope with this task.

Each of the 24 people knows at least 11 of the others. Is it always possible to put them in double hotel rooms so that everyone is accommodated with someone they know?

Planet Thor is shaped like a donut. There are 5 cities on it. Is it possible to connect each pair of these cities with roads so that the roads do not intersect anywhere?

There are 45 languages ​​spoken on the island of New Babylonia, with every resident knowing at least five of them. It is known that any two residents can conduct a conversation with each other, possibly through the mediation of several translators. Prove that then any two islanders can talk to each other using the services of no more than 15 interpreters.

In a group of 100 people, some know each other, and each member of the group knows at least 20 others. Prove that you can select 40 group members and divide them into 20 pairs so that in each pair the people are familiar.

On kn cards have numbers from 1 to n 2 each k times each. Prove that these cards can be placed on the table so that each number is written exactly on top k once.

There are 201 cities in the country, each with exactly 10 roads, and from any city you can get to any other. Prove that you can choose 20 cities, no two of which are connected by a road.

There are several poles in the yard, some pairs are connected by wires. Total stretched mn wires, and these wires are painted in n colors, and no wires of the same color extend from any pole. Prove that you can recolor these wires so that there are equal numbers of wires of all colors and still no two wires of the same color come from any pole. (130, Ukraine 1989)

There are 36 pillars in the yard; initially, a wire is stretched between any two pillars. Every morning on the way to school, the bully Vasya breaks 35 wires. Every evening, electrician Petrov restores the wires coming from a certain pole. Prove that Vasya can act in such a way that one morning after another act of vandalism there are less than 18 wires left. (135, A.V. Pastor, St. Petersburg 2000)

There are 100 points marked on the plane. Two people play and take turns. In one move, you can connect two points with an arrow if they have not been connected before. In this case, it is forbidden to draw an arrow, after which it will be possible to get from any point using the arrows to any other. The one who cannot make another move without breaking the rules loses. Who wins if the game is played correctly: the one who goes first or his partner?

Several different numbers were chosen from the integers from 1 to 100. Let us call the divisibility index of a given number the number of selected numbers by which given number is divided entirely. It turned out that all the selected numbers have different divisibility indices. What is the largest number of numbers that could be chosen?

N The circles are arranged so that the center of each of them lies inside exactly one of the others, and inside each of them lies the center of exactly one of the others. Find all the numbers N, in which this is possible.

22 schoolchildren took part in the congress of young writers. After the congress, each of them read the works of three young writers who attended the congress. Prove that it is possible to form a commission of 4 people from the congress delegates so that no one in the commission reads the works of the other members.

There are 1999 holidaymakers in the holiday home. Some of them know each other, and any two strangers have a common friend among the vacationers. What is the smallest possible number steam vacationers you know?

There are 1000 cities on the planet, including state capitals. Some cities are connected by roads in such a way that any road connects exactly two cities, and from any city to any other one can be reached by roads. Moreover, to get from one capital to another, you need to travel at least 21 roads. Prove that there are no more than 90 capitals on the planet.

There are 1997 nails driven into the board. The two take turns making moves. The move consists of the player connecting any two nails that were not previously connected with a wire. The loser is the one after whose move it becomes possible for the first time to get through the wires from any nail to any other. Who will win if the game is played correctly: the one who makes the first move, or his partner?

Connected graph G remains connected when any 18 vertices are removed (along with all edges emerging from them). Let's call cut any set of 19 vertices, when removed, the graph loses connectivity, and piece any component of connectivity that is formed when the cut is removed. It is known that any piece containing less than 10 vertices is not contained in any cut. Prove that no piece is contained inside the cut.

Graph G connected Let's call cut the minimum inclusion set of vertices, when removed (together with all the edges emerging from them), the graph loses connectivity. It is known that when removing cut vertices R vertices from the cut S end up in the same connected component. Prove that when removing vertices of a cut S vertices from the cut R end up in the same connected component.

There are 49 grid points marked on the checkered paper, arranged in a 66 square. What is the minimum number of unit segments with ends at marked nodes that must be drawn so that between any pair of adjacent nodes there is a path no longer than 3?

In a company from n a person where everyone knows at least one of the others, everyone has an equal number of acquaintances (it is believed that if A is familiar with IN, then IN is familiar with A). Prove that from the members of this company it is possible to choose at least n/3 disjoint pairs of acquaintances.

In a company, every two people have exactly five mutual acquaintances. Prove that the number of acquaintances (pairs of acquaintances) is a multiple of three. ( Yu.M. Lifshits)

In the single round-robin tournament, two participants left the competition after the fifth round. In the end, 38 games were played in the tournament. Did these two have time to play with each other? ( Bulgaria, 1982)

In the single round-robin tournament, six participants left the competition after the sixth round. In the end, 67 games were played in the tournament. Prove that at least two of the eliminated players did not play against each other. ( K.A. Knop)

What is the smallest possible number of edges in a graph with 100 vertices such that among any 11 vertices there is one connected to the other 10 of them? ( R. Fedorov)

In connected graph 2 n vertices, the degree of each vertex is three. Prove that the number of ways to color the edges of this graph in three colors so that edges of different colors converge at each vertex does not exceed 32 n .

In some state 4 n airports, there are exactly 3 airlines leaving from each airport (an airline connects two airports). From any airport you can fly to any other (possibly with transfers). Let TO - number of ways to sell All airlines to three airlines in such a way that three airlines of different airlines depart from each airport. Prove that TO 32 3 n .

Eight chess players played the tournament in one round. It is known that in any three chess players there were two who played a draw with each other. What is the smallest number of draws that could happen in this tournament?

At the vertices of the square there are 4 computers connected to their neighbors on the sides of the square. At the initial moment, each computer received an important piece of news (each with its own). Every second, a computer can either transmit all the news it knows to a neighboring computer, or receive relevant information from a neighboring computer, or do nothing. How for least time can all computers receive all the news available in the system?

In the country of Elenia n residents. They unite in interest groups. There are exactly three people in each circle, and any two are members of exactly one circle at the same time. Prove that n When divided by 6, the remainder is either 1 or 3.

We arrived at the camp m boys and d girls. Each girl knows no more than 10 boys, and each boy knows no less than one girl. It turned out that each boy knew more girls than any girl he knew knew boys. Prove that d 1.1 m. (D.V. Karpov)

Give an example of a fourteen-sided structure, each face of which is either a square or regular triangle? (YES. Kramarenko)

There are 2000 black points in space, no four of which lie in the same plane. Some of the points are connected by arrows. It is known that there is no path following the arrows and passing through all points (even if it is possible to pass through one point several times). Prove that some of the points (at least one, but not all) can be recolored blue so that no arrow leads from the blue point to the black one. ( Belarus, 1992)

The graph has a spanning tree with exactly n hanging vertices and a spanning tree exactly with m hanging peaks, n  k  m. Prove that this graph contains a spanning tree with exactly k hanging peaks.

In a company of 200 people, any five can be imprisoned for round table so that each of them sits between two acquaintances (it is assumed that if A is familiar with B, That B is familiar with A). What is the smallest number of pairs of acquaintances there can be in this company?

Prove that each polyhedron can have two faces red and the other two blue, so that the red faces have equal sides and the blue ones too.

In a connected graph 3 k vertices, all of them have degree 3, with each vertex included in exactly one triangle. Some edges of the graph were removed so that a tree was obtained. Prove that this tree has at most k+2 vertices of degree 1.( D.V. Karpov)

In the kingdom N cities and r roads (each road connects two cities, and from any city you can get to any one along the roads). Messengers live in cities. At the beginning of each year, one of the cities sends a messenger to all neighboring (i.e., connected to it by roads) cities. (Such a city must have a sufficient number of messengers for this.) After a few (more than zero) years, each city had the same number of messengers as there were initially. What is the smallest number of messengers a kingdom can have? ( I.I. Bogdanov)

Given a graph whose degree of any vertex is at least k(Where k2). Prove that this graph contains a simple cycle of length at least k+1. ()

In a gang of terrorists, each suspects at least 10 others of treason.. Prove that in this gang it is possible to identify at least 11 terrorists and number them so that the first suspects the second, second, third, ..., the penultimate suspects the last, and the last suspects the first. ( based onKözepiskolai Matematikai Lapok)

In a graph, any two simple cycles of odd length have no common edges. Prove that the vertices of this graph can be colored in two colors so that each vertex is connected by an edge to at most one vertex of the same color.( S.L. Berlov)

There are 100 cities in the country. Some pairs of cities are connected by roads, but no city is connected to all of them. You can get from any city to any other by visiting no more than one city along the way. What is the smallest number of roads this country can have? ( )

There are 25 cities in the country. Some pairs of cities are connected by roads, but no city is connected to all of them. You can get from any city to any other by visiting no more than one city along the way. Prove that there are at least 35 roads in this country. ( Közepiskolai Matematikai Lapok)

There are 9 cities in the country. Some pairs of cities are connected by roads, but no city is connected to all of them. You can get from any city to any other by visiting no more than one city along the way. Can this country have no more than 13 roads?( S.L. Berlov, D.V. Karpov, based on Közepiskolai Matematikai Lapok)

Degrees of all vertices of the graph G less (where n> 2), and among any n+ 1 there are two non-adjacent vertices. Let's call block many of n pairwise adjacent vertices of the graph G.It is known that any two blocks have a common vertex. Prove that all blocks have a common vertex.( S.L. Berlov)

Edges of a complete graph with n the tops are painted in several colors, and the colors are no less than n. Prove that there are three vertices, all the edges between which are colored different colors. ( P.A. Kozhevnikov)

Edges of a complete graph with n the vertices are painted in several colors in such a way that each color occurs at most n- 2 times. Prove that there are three vertices, all the edges between which are colored different colors.( AMM)

In the column G sets of vertices selected S 1 , S 2 , S 3 with 100 vertices each. It is known that when all vertices of any of these three sets (and all edges coming from them) are removed, the remaining vertices of the graph split into exactly two connected components, and when any 99 vertices are removed, the graph remains connected. Prove that all those not included in the sets S 1 , S 2 and S 3 graph vertices G can be divided into 6 groups in such a way that the vertices of one group end up in the same connected component when the vertices of any of the sets are removed from the graph S 1 , S 2 or S 3 .(D.V. Karpov)

King Pea has 20 courtiers. Intriguing against each other, they formed a number of secret societies. The chief of the secret police, studying these societies, discovered three patterns. Firstly, for any two secret societies, all courtiers who are simultaneously members of both societies form a secret society. Secondly, for any two secret societies, all courtiers who are members of at least one of them form a secret society. Thirdly, for any secret society, all courtiers who are not part of it form a secret society. Can it be exactly 2002 at the Pea court? secret societies? (Putnam 1961 restatement)

On the edges of the dodecahedron there are numbers from 1 to 30 without repetitions. Let's count the number of broken lines made up of three edges of the dodecahedron and such that the numbers on the links are in ascending order. Find the minimum possible number of such broken lines. (I.I. Bogdanov, G.R. Chelnokov based on the problem of the Polish Olympiad-89/90 )

On the edges of the cube there are numbers from 1 to 12 without repetitions. Let's count the number of broken lines made up of three edges of a cube and such that the numbers on the links are in ascending order. Find the minimum possible number of such broken lines. (Poland-89/90)

In a company of 20 people, for any three people there is a person who knows them all. Prove that there is a person who has at least nine acquaintances. ( S.L.Berlov, I.I.Bogdanov)

In a company of 10 people, for any three, there is a person who knows them all. Prove that there is a person who has at least six acquaintances.

100 people came to the symposium. Of these, 15 were French, each of whom knew at least 70 participants in the symposium, and 85 Germans, each of whom knew no more than ten participants. They were housed in 21 rooms. Prove that there is not a single pair of acquaintances in any of the rooms. ( Yu. Lifshits)

There are 22 athletes in the company. There are fourteen pairs of athletes who are friends of each other. It turned out that among any 11 athletes there is at least one pair of friends. Prove that everyone can be divided into two football team so that each pair of friends ends up on the same team. ( Simplifying Major League Problem 10)

In column with 4 k vertices 3 k ribs It is known that among any 2 k there are two vertices of it connected by an edge. Prove that the vertices of the graph can be divided into two groups of 2 k vertices in each so that no two vertices from different groups not connected by an edge. (R.A.Brualdi, S.Mellendorf)

A drunken chess king never makes two moves in a row in the same direction. Starting from the corner, he walked around the 99 checkered board, visiting each square once, and returned to the original square. What is the smallest number of diagonal moves he could make? ( S.L. Berlov based on the problem of O.Yu. Lanina, FML Olympiad No. 239, 2002G.)

There are 7 cities in the country, with 7 planes flying between them. The plane flies from each city to any other exactly 1 hour, and immediately after landing it can fly to the next city (while transit passengers remain on the plane). Make a flight schedule so that any passenger, without changing planes along the way, can fly from any city to any other no more than 5 hours after arriving at the airport. (Grossman Olympics)

The five vertices of the cube are painted red. Is it true that there will definitely be three edges with both ends red?

Fedya has a disconnected graph. He is everyone possible ways I removed one vertex from this graph and drew each of the resulting graphs on a separate piece of paper, after which I gave all these pieces of paper to Dima. Prove that Dima can restore the original graph using these leaves. ( D.V. Karpov, based on Ulam's hypothesis)

Fedya has several boxes containing balls. He takes turns taking one ball out of the boxes, writes down a set of numbers on a separate piece of paper - the number of balls remaining in each box, if there is anything left there (without specifying which number corresponds to which box), and then returns the ball to its place. Having taken out each ball once, he gives all the leaves to Dima. Prove that Dima can determine how many balls are in each box. ( D.V. Karpov)

n- odd number. The vertices of the convex n-gons are painted in several colors so that every two adjacent vertices - different color. Prove that this n-gon can be divided into triangles by non-intersecting diagonals, none of which have the same colored ends. ( Kurszak-1978, No. 2)

Given a graph on n peaks. Prove that all its edges can be divided into at most n 2/4 sets, each of which consists of one edge or is a triangle. ( Bogdanov, Karpov)

Cities A, B, C are connected by flights. Between any two cities there is at least one flight, and all flights are two-way (if you can fly from A to B, then the same flight can fly from B to A). In addition, we know that the total number of ways to get from point A to point C (including routes with a transfer at B) is 11, and the total number of ways to get from point A to point B (including routes with a transfer at C) is 13. How many are there? non-stop flights between these cities?

Given a checkered square whose side contains n nodes A non-return path is a path along edges, the intersection of which with any horizontal or vertical line is a segment, point or empty set. What is the smallest number of non-return paths that can cover all vertices? ( I. Pushkarev, I. Bogdanov, G. Chelnokov)

Given a connected graph that remains connected when any vertex is removed. It is known that it contains a triangle. Each vertex, except one, has a token (all tokens are different). It is allowed to move a piece from a vertex adjacent to an empty one to an empty one. Prove that by doing this you can get any configuration of chips. ( M. Mazin)

In the city, 10 streets run from north to south, and 11 from west to east, forming 110 intersections. By order of the mayor, any bus route in the city can go in no more than two directions (east-south, east-north, west-south or west-north). Is it possible to connect all the intersections in the city with seven bus routes? (Based on I. Pushkarev, I. Bogdanov, G Chelnokov)

What is the smallest number of vertices that a convex polyhedron can have, exactly three of whose faces are pentagons? ( USAMTS 2003)