Посмотрим, сколько может быть пар утверждений $%(A_i\Rightarrow A_j,A_j\Rightarrow A_i)$%. Таких пар не более $%n-1$%, иначе найдётся из этих пар цикл и какое-то утверждение будет следствием других. "Одинарных" утверждений $%A_i\Rightarrow A_j$% не более $%C_n^2$%, итого не более $%C_n^2+n-1$% аспирантов. Пример для $%C_n^2+n-1$%: $%A_i\Rightarrow A_j$% для всех $%i< j$% плюс $%A_n\Rightarrow A_i$% для всех $%i< n$%. отвечен 12 Июн '15 21:30 EdwardTurJ |
$$C_n^2+n-1.$$
@EdwardTurJ: может быть, имеет смысл написать подробное решение?
@sapere aude, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).