There are $100$ cities in Matland. Every road in Matland connects two cities, does not pass through any other city and does not form crossroads with other roads (although roads can go through tunnels one after the other). Driving in Matlandia by road, it is possible to get from any city to any other. Prove that that it is possible to repair some of the roads of Matlandia so that from an odd number of repaired roads would go in each city.
Problem
Source: 2020 Grand Duchy of Lithuania, Mathematical Contest p2 (Baltic Way TST)
Tags: combinatorics
gnoka
06.10.2020 06:07
parmenides51 wrote: There are $100$ cities in Matland. Every road in Matland connects two cities, does not pass through any other city and does not form crossroads with other roads (although roads can go through tunnels one after the other). Driving in Matlandia by road, it is possible to get from any city to any other. Prove that that it is possible to repair some of the roads of Matlandia so that from an odd number of repaired roads would go in each city. What do you mean by “repair”？ Are they broken？ You didn't mention it
parmenides51
06.10.2020 07:53
Matlandijoje yra 100 miestų. Kiekvienas kelias Matlandijoje jungia du
miestus, neina per jokį kitą miestą ir nesudaro kryžkelių su kitais keliais
(nors keliai gali tuneliais eiti vieni po kitais). Važiuojant Matlandijos
keliais, iš kiekvieno miesto įmanoma patekti į bet kurį kitą. Įrodykite,
kad įmanoma taip suremontuoti kai kuriuos Matlandijos kelius, kad iš
kiekvieno miesto eitų nelyginis skaičius suremontuotų kelių
indeed (using google translate) it doesn't mention anything for the repairs (source)
gnoka
06.10.2020 11:26
parmenides51 wrote:
Matlandijoje yra 100 miestų. Kiekvienas kelias Matlandijoje jungia du
miestus, neina per jokį kitą miestą ir nesudaro kryžkelių su kitais keliais
(nors keliai gali tuneliais eiti vieni po kitais). Važiuojant Matlandijos
keliais, iš kiekvieno miesto įmanoma patekti į bet kurį kitą. Įrodykite,
kad įmanoma taip suremontuoti kai kuriuos Matlandijos kelius, kad iš
kiekvieno miesto eitų nelyginis skaičius suremontuotų kelių
indeed (using google translate) it doesn't mention anything for the repairs (source) thanks very much.
YII.I.
07.10.2020 17:06
parmenides51 wrote:
Matlandijoje yra 100 miestų. Kiekvienas kelias Matlandijoje jungia du
miestus, neina per jokį kitą miestą ir nesudaro kryžkelių su kitais keliais
(nors keliai gali tuneliais eiti vieni po kitais). Važiuojant Matlandijos
keliais, iš kiekvieno miesto įmanoma patekti į bet kurį kitą. Įrodykite,
kad įmanoma taip suremontuoti kai kuriuos Matlandijos kelius, kad iš
kiekvieno miesto eitų nelyginis skaičius suremontuotų kelių
indeed (using google translate) it doesn't mention anything for the repairs (source) My translation: There are 100 cities in the Matlandia. Each road in Matlandia connects with two cities, and does not pass through other cities. And any two roads doesn't intersect (although the road can go through tunnels beneath the other road). We can go to any city from any city, by driving on the roads of Matlandia. Prove that it is possible to choose some roads and repair them, such that any city connects with odd repaired roads. (well my poor english...) (if you really want, you may ask me and read my chinese translation)