Problems from mathematical Olympiads

Problem (from ITYM) “Game of cycles”

For this problem I am thankful to Misha who told me about it from ITYM tournament.
Consider an undirected graph G in the plane possibly with loops but with no multiple edges. Let V be the set of its vertices, and E the set of its edges. A path of length k is a
sequence of distinct edges (v0, v1), (v1, v2), . . ., (vk−1, vk) ∈ E. We call v0, vk ∈ V respectively the start and end vertex of the path, and v1, . . . , vk−1 ∈ V are the internal vertices. We say that a path is simple if its vertices are distinct, except possibly for the start and end vertex.
A cycle of length k is a simple path of length k such that v0 = vk. (So, the cycles of length 1 are exactly the loops of G, and there is no cycle of length 2.)
The game itself.
The high school students Clara and Carl play the following game: they alternately draw an edge between two points that are not connected by an edge yet. Clara starts the game. In each of the following cases, find a winning strategy for one of the students:
a) The loser is the one after whose move the obtained undirected graph will contain a cycle of length at least k

I liked the problem so much that I suggest here one trick about how one can form cycles of arbitrary size. The algorithm is the following:
1. Form cycle of length L=3 
2. Merge together two cycles of length L=3 so that they have one common edge.
Now count how many edges does this cycle have? Yes, the answer is L=4 
3. Now it is clear that from two cylces of length L=k-1 and L=3 we can make cycle of length L=k. 

-tCFfPuX3mQ

Illustration of random graph is this picture of randomly emerged graph. (c) LT

Problem (network giant)

Imagine a network G with N nodes (in the case bellow Barabasi Albert network with gamma exponent 3).  The question is whom to target to make the spreading of information the most efficient as possible.

net

Now assume, that you do not know the network, but know only one fact:
everyone is connected to anyone in this network within maximum 6 handshakes,
how many people we need to target to get full coverage of the network of N people? Which other properties of the network would you need to know to address this question?

Problem (ants in the tree)

We are iven a tree graph G with n dead-ends (see figure below), where each edge is of length x cm. Speed of each ant is x cm per second.  After how many second all ant will leave the tree or can there be any ants?
Consider first case n=2 for interval, for which after 1 second there are no ants.

fourmi

Problems on mathematical linguistics. Задачи памяти Успенского,  ОТиПЛ (Moscow State University)

Problems on the classical graph theory

 

One of my favourite books in graph theory is by Ore and Harary.
There are many problems which are proven in a very unusual way: Hamiltonian and Kuratowski problems are the first examples

 

Problem for a starter is a beautiful chess problem where small weak pawns play a big role

nimzowitsch

(from the book “Improve your chess” by Lars Hansen)

***

I am interested in analysis of graphs in different ways: graph coloring, graph embedding, graph combinatorical problems, random graphs. We prepared small file about graph coloring problems, which can be found here and below with the figure from it:

Complete-edge-coloring

***

800px-Six_degrees_of_separation.svg

Here I would like to discuss another topic about networks, which I was working on closely “if in real systems “six degrees of freedom effect” can be really observed?” The scheme illustrating the “well connected society” is given in Wikipedia article and we show above. (TBU)

***

Here is very known and very beautiful problem about infinite number of dwarfs with hats:

“We have an infinite number of prisoners enumerated {1,2,…}{1,2,…}, and on each prisoner there is a hat of either blue or red color. The nnth prisoner sees the hats of prisoners {n+1,n+2,…}{n+1,n+2,…}. A warden asks each prisoner in succession, starting with prisoner n=1n=1, “What is the color of your hat?” If any prisoner fails, then the warden executes that prisoner. Prisoners can not communicate. What strategy should the prisoners use (they discussed it before the moment that hats are put on them) to end up with a finite number of executions? ”

In Russian the full text can be found from harbrahabr website. In short the problem is formulated like this:

На каждого гнома из бесконечной очереди надет либо синий, либо красный колпак. Каждый гномик смотрит в спину впереди стоящего так, что первый видит колпаки всех, кроме своего, второй видит всех, кроме себя и первого, и так далее. Каждый гном знает лишь то, что видит, свое положение в очереди и то, о чем они все вместе договорились перед тем, как получить колпаки.
По команде все гномы должны одновременно назвать цвет. Тех, кто не угадал, какой на них колпак, расстреливают.
Вопрос: как им договориться, чтобы не угадало лишь конечное число гномов?

250px-Axiom_of_choice.svg Просто, чтобы дать подсказку, интересно то, что решение в общем виде также относится к аксиоме выбора.

***

SGP_GrandParisExpress_Charte2013Since I work on stochastic processes I wanted to explain the paradox, which is related to our every-day life, so called, bus-paradox, which explains why we are always late for the bus.
Let us assume that the waiting time distribution of various bus routes between points i and j are independent, i.e. w_ij(t) for various i and j.
The average waiting time for a bus on a route between i and j can be computed from the latter after integrating by parts, which gives <t_ij> = 1/2<tau^2>_ij/<tau_ij>,
showing that the average waiting time depends on the variance of the inter-activation time.
AND as the result, interestingly, for fixed inter-activation time <tau_ij>, the total <t_ij> (time we wait at the bus stop) can be arbitrarilly large, which depends on the variance of inter-activation times (which for some buses in some countries can be very large).

Le-Bus-Direct-Paris-Aéroport-Place-de-l'Etoile-_-630x405-_-©-AEROLIS

***

During school I was happy to participate in discussions about so-called Steiner problem in the group of Pr.Tuzhilin and Pr.Ivanov, working on the generalisation of this problem.

The initial problem is formulated as simple as: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments. It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem.

Exciting problems about geometry are discussed in the book by Sharygin (на русском)

20171227_162255.jpg

***

It is easy to formulate problems based on the network measure. For example, can you draw a graph, for which degree and betweenness measures would be proportional. We note that all network measures are given in the review by M.Newman  here.

***

When talking about any scientific subject the most important is to make children interested.
As V. Arnold, famous mathematician, was saying, “it is the most important, to make children to be able to look at some simple yet interesting problems by themselves, so that they would be able to learn to think by themselves.” Book in Russian is here.

 

DSC_9512

***

There is a famous problem “Secretary problem” (in Russian, it is called “Princess, choosing her husband”), which is formulated as follows:

 

  • There is a single position to fill.
  • There are n applicants for the position, and the value of n is known.
  • The applicants, if seen altogether, can be ranked from best to worst unambiguously.
  • The applicants are interviewed sequentially in random order, with each order being equally likely.
  • Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
  • The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
  • The objective of the general solution is to have the highest probability of selecting the best applicant of the whole group. This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.

In fact, this algorithm can be applied in real life for choosing candidates.

***

Epigraph: “There were only 4 cars in the USA at the end of 19th century, but 2 of them managed to crash.”
This anecdote brings us to the famous problem about meeting times of two random walkers on a graph (of roads). On a lattice similar problem was studied extensively, for example here.

probability-two-random-walkers-path

***

Another related problem is so-called “Coupon Collector Problem”.

It is formulated simply as if you want to collect each of n different coupons, and you get every day a random coupon in the mail, how long do you have to wait? This quantity is connected to the cover time on a graph and has been studied by many mathematicians, including famous Hungarian mathematician Lovasz.

 

***

 

Problems related to the combinatorics of graphs. The source. Other famous references for combinatorical problems are here (лекции Носова по Гамильтоновым графам и многому другому).

***

Mathematics of origami is a subject of hundreds of papers.
People now know how to origamize many objects: starting from a tulip and ending up
a complex forest.
Serezha sent me video about the mathematician’s Ted talk about the algorithm how to do this.
origami-tulip TED talk link

***

Another combinatorial life-problem

Given N people, m rooms and k fields, where people are working, find number of possible suitable combination so that noone from (rooms can include as many people).
Now imagine that some people do not like some other people, what will change in solution? (solve this graphically)

Great collection of video lectures in mathematics (video)

***

I continue to upload maths problems about trees (which are loopless graphs).

Interestingly, these problems often appear in physics, for instance in percolation studies.

246107233_28170

 

***

Thanks to Serezha Dovgal I got to know about several problems from one family of mathematical problems called “Rainbow graph coloring”. More in details see here (Sunil Microsoft) or Wikipedia image below.

Start with two definitions.

Def.1. A path between two vertices is a rainbow path if no two edges
in this path have the same color.

Def.2. If there is a rainbow path between every pair of vertices, then
the coloring is called a rainbow coloring.
Minimum number of colors required to achieve this is called
the rainbow connection number rc(G).

Problem is, in general to estimate this number rc(G) for special class of graphs.

450px-Wheel_rainbow_coloring.svg

 

***

Another mathematical problem is for highschool-university students.
So-called “Bus arrival problem and memoryless processes”.
Question is simple: can we model bus arrival process (knowing that it arrives every 20 mins approximately) by Poisson process?

Definition.
Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space.
The homogeneous Poisson point process, when considered on the positive half-line, can be defined as a counting process, a type of stochastic process, which can be denoted as {\displaystyle \textstyle \{N(t),t\geq 0\}} \textstyle \{N(t),t\geq 0\}.[32][41] A counting process represents the total number of occurrences or events that have happened up to and including time {\displaystyle \textstyle t} \textstyle t. A counting process is a Poisson counting process with rate {\displaystyle \textstyle \lambda >0} \textstyle \lambda >0 if it has the following three properties:
1. N(0)=0, 2. has independent increments; 3. the number of events (or points) in any interval of length t is a Poisson random variable with parameter
\lambda t (since \lambda is a rate).

Hint 1. Consider and example: I am waiting for the bus, and bus arrivals are known to be a Poisson
process at rate 1 bus per 10 minutes. Starting at time t = 0, what is the
expected arrival time of the third bus?

Hint 2. The answer for the problem is no.
More you can learn at HSE coursera course on stochastic processes.

prTKI.jpg

***

“Not just mathematical question”

Recently in Quanta magazine there have been an article about new phases of matter. One of the main take-home message for me after this article was “what is next?”

“Condensed matter physicists have discovered a wonderland of exotic new phases of matter: emergent, collective states of interacting particles that are nothing like the solids, liquids and gases of common experience”

For explanations about fractal properties of materials and definitions of fractons look at  Quanta!

Скриншот 02-06-2018 193150.png

***

Another mathematical problem with a clear physical output is called “Ant on the tree”

Imagine, that you have an ant, a random walker, X(t), which can move on a tree. For simplicity we can say that a tree is a simple structure, which is represented by a graph, G (V,E), such that a tree is encoded by its adjacency matrix structure.

The question of an ant on the tree is how long on average it will take for an ant to get from the bottom of a tree to reach the top and to come back? How does it depend on the “type” of a tree?

4179-15915

***

I like the problem, which I saw on Salon de Maths by one mathematician from Paris, the problem is called “Game of life: ill and healthy cells”
Some squares on a chessboard suddenly catch a contagious disease. Infection then threatens all n×n cells by spreading to any healthy cell sharing at least two of its four sides with infected cells. The process ends only after total contamination of the board, or when all healthy squares have less than one ill neighbor.
See example below.
Consider the same problem on a finite graph, where initially the finite number of nodes are infected.
On a lattice (in 1D) solution is quite simple. If initially there are any two nodes, with one node between them, then the node between them
will get infected, however, the next step, if there are no other close nodes, the solution will become localised and will soon disappear.
What will be the solution on a 2D lattice or other disordered lattice.

download (4)

 

***

One of the recent problems I rediscovered for me is so-called “Travelling salesman” problem. The problem is very simply formulated: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

The question which I ask in the case of NP-hard problems is whether there are any sets of nodes, for which this NP problem can be solved reasonably fast.

map002g

***

One of the basic problems in graph theory is so-called “Handshake dilemma”, which was nicely explained on this network website.

There are some  simple conditions on the degrees that is true in any graph. The handshake lemma is the following: if we compute the sum the degrees over all the vertices in the graph, then we arrive at an even number. In fact, it is equal to twice the number of edges in the graph. In a mathematical formula:
2|E| = ∑p(k)        or      total degree of all vertices = 2 x total number of edges
Why it is called the handshake lemma? If we model whether pairs of people have shaken each other’s hands as a network, then the sum of the number of handshakes over the people is again an even number that equals twice the number of handshakes. The handshake lemma is even true in cases where pairs of people can shake each other’s hands arbitrarily often.

Advertisements