网大论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

https://www.chinaedugrp.com/MIT/edm.html
查看: 731|回复: 0

数学应用 [复制链接]

Rank: 10Rank: 10Rank: 10

精华
5
积分
11199
发表于 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 个单向边。因此,加上单向边和对偶边的最大数得:

四万高手过招,这份阿里全球数学竞赛试题你真的不要看吗
您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|mba报考条件|Conference Centre|netbig.com|大学排名|国际学校|欧洲移民|股票行情|网大论坛 ( 粤ICP备08125616号 )

GMT+8, 2019-6-21 03:47

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部