Professor Ma has formulated n different but equivalent statements A_{1}, A_{2}, \ldots, A_{n}. Every semester, he advises a student to prove an implication A_{i} \Rightarrow A_{j}, i \neq j. This is the dissertation topic of this student. Every semester, he has only one student, and we assume that this student finishes her/his dissertation within the semester. No dissertation should be a direct logical consequence of previously given ones. For example, if A_{i} \Rightarrow A_{j} and A_{j} \Rightarrow A_{k} have already been used as dissertation topics, Professor Ma cannot use A_{i} \Rightarrow A_{k} as a new dissertation topic, as the implication follows from the previous dissertations. What is the maximal number of students that Professor Ma can advise?
Solution
We will first construct an answer with \frac{1}{2}(n+2)(n-1) students. Then, we will show this is the best possible answer. Construction: First, (n-1) students sequentially prove A_{1} \Rightarrow A_{i} for i=2, \ldots, n. Then, (n-2) students sequentially prove A_{2} \Rightarrow A_{i} for i=3, \ldots, n. Continue this until 1 student proves A_{n-1} \Rightarrow A_{n}. Note that all implications proven so far are valid these and have the form A_{i} \Rightarrow A_{j} for i<j. Next, (n-1) students sequentially prove A_{n} \Rightarrow A_{n-1}, A_{n-1} \Rightarrow A_{n-2}, \cdots, A_{2} \Rightarrow A_{1}, which are also valid theses. The total number of theses is ((n-1)+(n-2)+\cdots+1)+(n-1)=\frac{1}{2}n(n-1)+(n-1)=\frac{1}{2}(n+2)(n-1).
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.