Maths Olympiad Prep

Library / /4 of 5

Combinatorics Difficulty 5.3 AIME, harder Prove it Japan

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 XX, YY IXYI_{XY}. 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 LL, there are exactly 4 interpreters who are proficient in LL. If there are 3 or more rooms having a language LL as the common language, then there must be 2×3=62 \times 3 = 6 or more interpreters who are proficient in LL, 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 L1L_1 and L2L_2 are the common languages of 2 different rooms, then 4 interpreters proficient in the language L1L_1 must be staying in the 2 rooms whose common language is L1L_1, 4 interpreters proficient in the language L2L_2 must be staying in the 2 rooms whose common language is L2L_2. But, then the interpreter IL1L2I_{L_1 L_2} 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 GG the German, and the room whose common language is German by RGR_G. Suppose languages AA, BB are the languages different from German that the 2 interpreters staying in RGR_G are proficient in, respectively. There are 2 other interpreters besides those 2 in the room RGR_G 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 RCR_C and RDR_D with respective common language being CC and DD. If the languages CC and AA are the same, then there would be 2 interpreters whose proficient languages are GG and AA, contradicting the assumption. Thus CC has to be different from AA, and for the same reason, CC is different from BB. Similarly, DD has to be different from both AA and BB, now the common languages of the 2 rooms besides RG,RC,RDR_G, R_C, R_D must be AA and BB, respectively. Call these 2 rooms RAR_A and RBR_B, respectively. We know that the interpreter IABI_{AB} must be staying in the room RAR_A or RBR_B, and ICDI_{CD} in RCR_C or RDR_D. Suppose IABI_{AB} is staying in the room RAR_A and ICDI_{CD} is staying in the room RCR_C. Then, there are 1 spot each in the rooms RDR_D and RAR_A, 2 spots in the room RBR_B to be filled by the remaining 4 interpreters IAC,IAD,IBC,IBDI_{AC}, I_{AD}, I_{BC}, I_{BD}. Among these 4 interpreters, only 2 who are proficient in the language BB, namely IBCI_{BC} and IBDI_{BD} can go into the room RBR_B. But then, the only interpreter who can go into the room RDR_D is IADI_{AD} who is proficient in the language DD, and the remaining interpreter IACI_{AC} goes into the room RAR_A. Summarizing we get the room assignment as follows:

RG:IGA,IGB,RA:IAB,IAC,RB:IBC,IBD,RC:IGC,ICD,RD:IGD,IAD. R_G : I_{GA}, I_{GB}, \quad R_A : I_{AB}, I_{AC}, \quad R_B : I_{BC}, I_{BD}, \quad R_C : I_{GC}, I_{CD}, \quad R_D : I_{GD}, I_{AD}.

This room assignment clearly satisfies the condition of the problem. There are 3 other choices for the combination of the rooms for IABI_{AB} and ICDI_{CD} 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 4!2!2!\frac{4!}{2!2!} ways of choosing the languages AA, BB and once the choice is made CC, DD are determined. There are 2×22 \times 2 ways of determining the rooms for IABI_{AB}, ICDI_{CD} 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 4!2!2!×2×2=24\frac{4!}{2!2!} \times 2 \times 2 = 24.

Next we consider the case (ii),

Let the language LL be the common language for both of the rooms RL1R_{L_1} and RL2R_{L_2}. Let (RA,A)(R_A, A), (RB,B)(R_B, B), (RC,C)(R_C, C) be the 3 remaining rooms with their respective common languages. LL, AA, BB, CC are distinct languages. Let XX be the remaining language different from any of LL, AA, BB, CC. All of the 4 people staying in the rooms RL1R_{L_1} and RL2R_{L_2} are proficient in the language LL, so none of the people staying in other 3 rooms are proficient in LL. The interpreter IXAI_{XA} cannot stay in any of the rooms RL1R_{L_1}, RL2R_{L_2}, RBR_B, RCR_C because the common language of the room he stays must either be AA or XX. Hence he has to stay in the room RAR_A. Similarly, IXBI_{XB} has to stay in the room RBR_B and IXCI_{XC} in the room RCR_C. The interpreter IABI_{AB} can stay either in RAR_A or RBR_B. Let us suppose that he stays in RAR_A. (Subsequent argument will work in the same way if we assume that IABI_{AB} stays RBR_B instead.) Then, 2 people to stay in the room RAR_A are decided so the interpreter IACI_{AC} has to stay in RCR_C, and this determines the 2 people who should go into the room RCR_C, which in turn determines that the interpreter IBCI_{BC} has to go into the room RBR_B. Remaining 4 interpreters ILAI_{LA}, ILBI_{LB}, ILCI_{LC}, ILXI_{LX} can go into the remaining 2 rooms RL1R_{L_1} and RL2R_{L_2} (with 2 people in a room) in any combination. There are 4!2!2!=3\frac{4!}{2!2!} = 3 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 IABI_{AB} goes into the room RAR_A or RBR_B, then the occupants of the rooms RAR_A, RBR_B, RCR_C will be determined completely. Thus, when the combination of common languages is determined, then there are 3×2=63 \times 2 = 6 ways of room assignments. The combination of the common languages is determined if the language LL is picked from the 5 given languages and then the language XX is chosen from the remaining 4. Consequently, there are 5×4=205 \times 4 = 20 ways of determining the combination of the common languages, and the number of room assignments satisfying the requirement under the condition (ii) is 6×20=1206 \times 20 = 120 and the total number of the room assignments is 24+120=14424 + 120 = 144.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.