level 7
广场上站着 999 个间谍,间谍与间谍之间的距离互不相等。每个间谍都盯着离自己最近的那个间谍看。
1. 证明至少有一个没被人盯着的间谍。
2. 最多有可能有多少个间谍没被盯着?
2018年08月15日 05点08分
1
level 1
第一问
既证明没有一个间谍被两个看是不可能
假设ab距离最短,则ab互看,此时不得存在间谍x,间谍x的最短距离是xa或xb。那么可以排除ab继续考虑剩余的997个。类推,每次排除2个,999是奇数,最后必然剩余1个间谍无人看
第二问
b中ab最短,c中ac最短,可以证明∠bac大于60度,既a最多被5人看。
既此5组中ab最短。此时d非这5个之一,可以构建a中ad最短。此时再构建包括a在内的5组距离d最短
999/6=166余3,则可以有5+165*4+2=667间谍无人看
2018年08月15日 06点08分
2
发现第二问有问题。如果5个分别都是距离a最短,那么第6个必然不可能最短是a,最短的应该是那5个中之一。
2018年08月15日 09点08分
一个间谍同时被两个人盯着也是有可能的啊
2018年08月15日 09点08分
@蜗靠 楼主你可能没有读懂题意。结果就是至少有一个人同时被两个人看等价于至少有一个人无人看
2018年08月15日 10点08分
level 1
第一问只有双数才能保证每个间谍都能被盯着看,因圈型监视必有一间谍被忽略,只有两人对视才能保证全都被监视。
第二问从每个间谍的最大被监视数出发,abc三人必成其中一角大于60度的三角形,则最大被五人监视。若初始距离足够长,则距离依次缩短,可以让后续所有人都有监视的对象。则999-1-5-25-125-625=999-781=218,故监视不完全内圈人数,还差625*5-218=2907人,则有2907/5=581人缺少监视(余两人监视同一人),那么总共未被监视的人数有218+581=799人。
通过同方法计算可得2人监视一人时500人未被监视,3人时666人,4人时749人。
2018年08月17日 15点08分
4
749人还不是最多
2018年08月17日 16点08分
这种计算是有问题的。假设abcde这5人都监视x。那么按层主的计算,必然有fghij监视a。那么首先,x监视谁?其次,不考虑x监视谁时,fghdij这5人中必然至少有一人,到bcdex中的某人距离更短,或a到fghij中某人距离小于ax
2018年08月18日 00点08分
@gf10025 x监视abcde中任何距离其最短之人,题目并没有限制两人不能对视,只说监视最短距离之人,那么五人之于x必有一人距离最短,则x监视此人即可
2018年08月18日 13点08分