ENS 发表于 2018-12-22 18:48:09

数学应用

答案:我们首先指导 0.5(n+2)(n-1) 个学生,下面,我们将证明这个答案。

解释:首先,(n-1) 个学生证明 A1->Ai,其中 i 为 2 到 n 的整数;然后,(n-2) 个学生证明 A2->Ai,其中 i 为 3 到 n 的整数。一直这样做,直到最后一个学生证明 An-1->An。
然后,(n-1) 个学生证明 An->An-1,An-1->An-1,...,A2->A1。它们的总数为:

四万高手过招,这份阿里全球数学竞赛试题你真的不要看吗

让 四万高手过招,这份阿里全球数学竞赛试题你真的不要看吗。

最优性证明:假设图 G=(N,E)的节点为 N={1,2,...,n},其有向边为 E={(i,j)|Ai -> Aj已经被证明了}。完成一个课题,意味着给 E 加上一条边。

假设 E': = { (i, j ) | 其中,Ai -> Aj 和 Aj -> Ai在前面已经被证明了 } 是对偶边,是集合 E 的子集,子图 G’=(N,E')最多有 2(n-1) 个有向边;否则,必然存在一些对偶边包含无效课题。

G 最多有 n(n-2)/2 对节点,去掉对偶边上的节点,正如前面所证明的,此时最多有 2(n-1) 个有向边,因此最多有 (n-1) 对有向边,也就是说,有 n(n-1)/2 - (n-1) = (n-2)(n-1)/2 对节点之间是单向边或者是没有边的。因此,最多有 (n-2)(n-1)/2 个单向边。因此,加上单向边和对偶边的最大数得:

四万高手过招,这份阿里全球数学竞赛试题你真的不要看吗
页: [1]
查看完整版本: 数学应用