Merlin's castle has 100 rooms and 1000 corridors. Each corridor links some two rooms. Each pair of rooms is linked by one corridor at most. Merlin has given out the plan of the castle to the wise men and declared the rules of the challenge. The wise men need to scatter across the rooms in a manner they wish. Each minute Merlin will choose a corridor and one of the wise men will have to pass along it from one of the rooms at its ends to the other one. Merlin wins when in both rooms on the ends of the chosen corridor there are no wise men. Let us call a number $m$ the magic number of the castle if $m$ wise men can pre-agree before the challenge and act in such a way that Merlin never wins, $m$ being the minimal possible number. What are the possible values of the magic number of the castle? (Merlin and all the wise men always know the location of all the wise men). Timofey Vasilyev
Problem
Source: 46th International Tournament of Towns, Senior A-Level P6, Fall 2024
Tags: combinatorics
29.11.2024 17:52
m is 1000. You link each corridor to either one of the 2 rooms connected to it. Then you place the men s.t. the number of men in a room is the same number as the number of corridors linked to that room. When Merlin picks a corridor, one of the men that is in the room linked to the corridor Merlin picked moves to the other room, and then we relink the corridor to the other room instead of the original linked room. Notice that for every pair of connected rooms, the corridor must link to at least one of them, thus there must be at least one man in one of the 2 rooms. You can make a counter example for m < 1000 by proving that m must be n choose 2 in a complete graph with n rooms. In a complete graph with n rooms, if you have a room with more than n-1 men, then you can use a induction argument and only consider the other n-1 rooms. If not, there is guaranteed to be 2 rooms with the same amount of men and Merlin can choose the corridor connecting these 2 rooms. Merlin can repeatedly do this until either 2 rooms have no men or one room has more than n-1 men. It is also clear that this process cannot be infinite. This proves that m must be n choose 2 for a complete graph with n rooms. Then you just make a bunch of complete graphs whose total sum of edges is 1000 and total sum of rooms is 100. You can have a complete graph of 45 rooms, then 5 complete graphs of 4 rooms, then a bunch of rooms with no corridors connecting to them