Competition problem — Combinatorics

Library / /9 of 11

Combinatorics Difficulty 7.0 National Olympiad Find the answer

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?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.