6. In the Thirtieth Kingdom, there are 100 cities, and no more than one road connects any two cities. One day, the tsar ordered that one-way traffic be introduced on each road, and at the same time, each road should be painted either white or black. The Minister of Transport proudly reported that after the order was carried out, from any city to any other, one could travel by alternating the colors of the roads, and in such a way that the first road in the journey would be white. What is the minimum number of roads that could have been in this country? When traveling from city to city, one can pass through intermediate cities any number of times. (M. Antipov)
Answer: 150. Solution: Example. Arrange the cities on a circle so that they divide it into equal arcs, and declare these arcs to be roads directed clockwise. Paint these 100 arcs in white and black colors so that the colors alternate on the circle. Direct another 50 white roads along the chords from the cities where black roads originate to the cities located one step away from them in the clockwise direction. Clearly, the described construction satisfies the emperor's order. Evaluation: We will prove a more general fact: if the kingdom has $2k$ cities, then there must be no fewer than $3k$ roads. Suppose this is not the case. Take the smallest natural $k$ such that in a kingdom of $2k$ cities, one can manage with fewer than $3k$ roads. Here $k>1$, since for two cities the order is clearly unfulfillable. Note that there are no fewer than $2k$ white roads among them, as a white road must leave each city. Therefore, there are no more than $k-1$ black roads, and hence there are at least two cities without black roads. Remove them along with the roads connected to them. In doing so, we will remove no fewer than three roads, since from each of the two cities one could leave and one could enter, and no more than one such road is counted twice. Thus, we now have $2(k-1)$ cities and fewer than $3(k-1)$ roads. Since no route with alternating road colors could pass through the removed cities, the remaining cities and roads still satisfy the emperor's condition, which contradicts the minimality of the number $k$.