Problems(3)
Wizards spell on island
Source: Saint Petersburg olympiad 2024, 11.7
9/22/2024
A tourist has arrived on an island where wizards live, each of whom can be a knight or a liar. He knows that at the time of his arrival, one of the hundred wizards is a knight (but does not know who exactly), and the rest are liars. A tourist can choose any two wizards and and ask to spell on with the spell "Whoosh"!, which changes the essence (turns a knight into a liar, and a liar into a knight). Wizards fulfill the tourist's requests, but if at that moment wizard is a knight, then the essence of really changes, and if is a liar, that doesn't change. The tourist wants to know the essence of at least wizards at the same time after several consecutive requests. For which maximum will he be able to achieve his goal?
combinatorics
Complete graph in 3 colors
Source: Saint Petersburg math olympiad 2024, 10.7
9/22/2024
The edges of a complete graph on vertices are colored in three colors. Prove that this graph contains a non-self-intersecting single-color cycle whose length is odd and not less than .
combinatorics
Metro tunnels divides into lines
Source: Saint Petersburg olympiad 2024, 9.7
9/22/2024
In a very large City, they are building a subway: there are many stations, some pairs of which are connected by tunnels, and from any station you can get through tunnels to any other. All metro tunnels must be divided into "lines": each line consists of several consecutive tunnels, all stations in which are different (in particular, the line should not be circular); lines consisting of one tunnel are also allowed. By law, it is required that you can get from any station to any other station by making no more than transfers from line to line. At what is the largest , any connected metro with stations can be divided into lines, observing the law?
combinatorics