Browse · MathNet
Print6 TST for BMO
Bulgaria counting and probability
Problem
Some cities of country Graphland are connected with roads provided that (i) from each city we can reach any other city. It turned out that every city can choose its favourite number which is an integer, such that the following condition holds: (ii) the favourite numbers of any two cities connected with a road are different. Let be a given integer. A tourist arrives in the capital of Graphland. He can move from city to city (in this direction), if and only if there is a road connecting and and additionally For which values of it is guaranteed (no matter of the cities and roads, provided that (i) and (ii) hold) that the cities can choose their favourite numbers (complying with (ii)) in a way that the tourist can reach any city starting from the capital? (Dragomir Grozev)
Solution
Answer: For each coprime with .
Let us first assume that . Then the tourist, starting from the capital with a favourite number , can reach only cities with numbers (mod ), . Since it is not a complete system of residues modulo , it means that the set of all favourite numbers consists of less than numbers. Take now cities and connect every two of them with a road. This is an example for which (i) can hold if all colours (favourite numbers) are used. That is, in this particular case it's impossible to reach every city starting from the capital.
Let us assume now that . Denote by the set of all cities and let be the maximal possible subset of vertices such that we can assign favourite numbers and starting from the capital we can reach every vertex in . We prove . Assume for the sake of contradiction . Then, for any vertices that are connected, we have Now, we construct a different mapping by changing the assigning of vertices in . We set, For any we set . Observe that under the new mapping , condition (i) still holds. Indeed, if for some connected vertices , it implies and thus, we would reach from under the mapping , which contradicts the maximality of .
Therefore, the mapping satisfies (i), and moreover starting from we can reach any vertex in . Since is maximal, it's not possible to access any vertex outside . It allows us to change the assignment of favourite numbers again using the rule and so on. Suppose now, are connected. There exists for which , because is a complete system of residues modulo . But this means that under the mapping , the vertex is accessible from , which contradicts the maximality of .
Let us first assume that . Then the tourist, starting from the capital with a favourite number , can reach only cities with numbers (mod ), . Since it is not a complete system of residues modulo , it means that the set of all favourite numbers consists of less than numbers. Take now cities and connect every two of them with a road. This is an example for which (i) can hold if all colours (favourite numbers) are used. That is, in this particular case it's impossible to reach every city starting from the capital.
Let us assume now that . Denote by the set of all cities and let be the maximal possible subset of vertices such that we can assign favourite numbers and starting from the capital we can reach every vertex in . We prove . Assume for the sake of contradiction . Then, for any vertices that are connected, we have Now, we construct a different mapping by changing the assigning of vertices in . We set, For any we set . Observe that under the new mapping , condition (i) still holds. Indeed, if for some connected vertices , it implies and thus, we would reach from under the mapping , which contradicts the maximality of .
Therefore, the mapping satisfies (i), and moreover starting from we can reach any vertex in . Since is maximal, it's not possible to access any vertex outside . It allows us to change the assignment of favourite numbers again using the rule and so on. Suppose now, are connected. There exists for which , because is a complete system of residues modulo . But this means that under the mapping , the vertex is accessible from , which contradicts the maximality of .
Final answer
All integers m between 1 and 2024 that are coprime to 2024
Techniques
Graph TheoryColoring schemes, extremal argumentsGreatest common divisors (gcd)Inverses mod n