10 language interpreters are invited to participate in an international mathematical contest. Each of the 10 interpreters is proficient in exactly 2 among the 5 following languages: Greek, Slovanian, Vietnamese, Spanish and German. Furthermore, the combinations of the 2 proficient languages among the 5 are all different for the interpreters. It is decided that the interpreters are distributed into 5 rooms, 2 people per room, in such a way that each pair of the interpreters assigned to the same room shares a common language of proficiency. How many different ways of distributing interpreters satisfy this requirement? Do not distinguish the two arrangements of room assignments in which all the five pairs occupying the same room are identical.
Solution
Let us call the interpreter proficient in the pair of different languages , . Suppose the interpreters are assigned to 5 rooms satisfying the condition of the problem. For each room call the language which the 2 occupants of the room can speak the common language of the room. By assumptions made for the problem, for each of the languages, say , there are exactly 4 interpreters who are proficient in . If there are 3 or more rooms having a language as the common language, then there must be or more interpreters who are proficient in , which contradicts the assumption. Hence for each of the languages, the number of rooms which have that language as the common language must be at most 2. Suppose two different languages and are the common languages of 2 different rooms, then 4 interpreters proficient in the language must be staying in the 2 rooms whose common language is , 4 interpreters proficient in the language must be staying in the 2 rooms whose common language is . But, then the interpreter would have to be staying in 2 different rooms, which is impossible. Therefore, the following 2 cases exhaust all the possibilities:
(i) The common languages are all different for the 5 rooms.
(ii) There exists a pair of rooms whose common languages are the same.
First, let us consider the case (i).
Since there are 5 languages and 5 rooms, every language is a common language of one and only one room. Denote by the German, and the room whose common language is German by . Suppose languages , are the languages different from German that the 2 interpreters staying in are proficient in, respectively. There are 2 other interpreters besides those 2 in the room who are proficient in German. These 2 are staying in different rooms, since if they are staying in a same room, then there would be 2 rooms whose common language is German, contradicting the assumption of (i). So, let those 2 rooms be and with respective common language being and . If the languages and are the same, then there would be 2 interpreters whose proficient languages are and , contradicting the assumption. Thus has to be different from , and for the same reason, is different from . Similarly, has to be different from both and , now the common languages of the 2 rooms besides must be and , respectively. Call these 2 rooms and , respectively. We know that the interpreter must be staying in the room or , and in or . Suppose is staying in the room and is staying in the room . Then, there are 1 spot each in the rooms and , 2 spots in the room to be filled by the remaining 4 interpreters . Among these 4 interpreters, only 2 who are proficient in the language , namely and can go into the room . But then, the only interpreter who can go into the room is who is proficient in the language , and the remaining interpreter goes into the room . Summarizing we get the room assignment as follows:
This room assignment clearly satisfies the condition of the problem. There are 3 other choices for the combination of the rooms for and to go in to start the argument above. But for each of the choices made, the exactly same argument as above, gives a room assignment (all distinct) which satisfies the requirement. There are also ways of choosing the languages , and once the choice is made , are determined. There are ways of determining the rooms for , to go in, and once these are decided, then as we saw above a room assignment for all the interpreters satisfying the requirement of the problem is determined uniquely. Hence the number of room assignments satisfying the requirement under the condition (i) is .
Next we consider the case (ii),
Let the language be the common language for both of the rooms and . Let , , be the 3 remaining rooms with their respective common languages. , , , are distinct languages. Let be the remaining language different from any of , , , . All of the 4 people staying in the rooms and are proficient in the language , so none of the people staying in other 3 rooms are proficient in . The interpreter cannot stay in any of the rooms , , , because the common language of the room he stays must either be or . Hence he has to stay in the room . Similarly, has to stay in the room and in the room . The interpreter can stay either in or . Let us suppose that he stays in . (Subsequent argument will work in the same way if we assume that stays instead.) Then, 2 people to stay in the room are decided so the interpreter has to stay in , and this determines the 2 people who should go into the room , which in turn determines that the interpreter has to go into the room . Remaining 4 interpreters , , , can go into the remaining 2 rooms and (with 2 people in a room) in any combination. There are ways of determining who should occupy these 2 rooms (Note that we do not distinguish the rooms in counting the number of possible distributions.) As we saw above, if we decide whether the interpreter goes into the room or , then the occupants of the rooms , , will be determined completely. Thus, when the combination of common languages is determined, then there are ways of room assignments. The combination of the common languages is determined if the language is picked from the 5 given languages and then the language is chosen from the remaining 4. Consequently, there are ways of determining the combination of the common languages, and the number of room assignments satisfying the requirement under the condition (ii) is and the total number of the room assignments is .