耐丝曼智力擂台赛 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>BrainTeaser - 大脑工作室

耐丝曼智力擂台赛

耐丝曼智力擂台赛# BrainTeaser - 大脑工作室

N*N2007-07-16 07:07

1 楼

背景: 考试试卷共6道题,都是选择题,每题有a b c三个选项,一群学生参加考试
结果: 考试结果,对于任意三个学生的答卷,都有一个题目的答案互不相同.
请问: 参加考试的学生最多有多少人?
(请给出答案的同时,给出解题思路和步骤,擂主具有最终解释权)

b*g2007-07-16 07:07

2 楼

至少一个？还是正好1个？

【在 N*****N 的大作中提到】

: 背景: 考试试卷共6道题,都是选择题,每题有a b c三个选项,一群学生参加考试
: 结果: 考试结果,对于任意三个学生的答卷,都有一个题目的答案互不相同.
: 请问: 参加考试的学生最多有多少人?
: (请给出答案的同时,给出解题思路和步骤,擂主具有最终解释权)

N*N2007-07-16 07:07

3 楼

至少

【在 b*****g 的大作中提到】

:
: 至少一个？还是正好1个？

b*m2007-07-16 07:07

4 楼

49? 蒙的

【在 N*****N 的大作中提到】

N*N2007-07-16 07:07

5 楼

No

【在 b*******m 的大作中提到】

: 49? 蒙的

e*s2007-07-16 07:07

6 楼

3*6*2=36!

n*a2007-07-16 07:07

7 楼

7个人
7选3,35种组合，最大的组合数小于36

【在 N*****N 的大作中提到】

h*02007-07-16 07:07

8 楼

不懂……

【在 n*******a 的大作中提到】

: 7个人
: 7选3,35种组合，最大的组合数小于36

N*N2007-07-16 07:07

9 楼

7个人不可能吧，你列一下？

【在 n*******a 的大作中提到】

: 7个人
: 7选3,35种组合，最大的组合数小于36

e*e2007-07-16 07:07

10 楼

3+3^2+3^3+3^4+3^5+3^6=1092

n*a2007-07-16 07:07

11 楼

现在有对的答案了嘛？
我已经不能停止地想这题了～都快强迫症了@@~~

【在 N*****N 的大作中提到】

: 7个人不可能吧，你列一下？

N*N2007-07-16 07:07

12 楼

没有，别停，继续想:)

【在 n*******a 的大作中提到】

: 现在有对的答案了嘛？
: 我已经不能停止地想这题了～都快强迫症了@@~~

m*t2007-07-16 07:07

13 楼

逆推
21人
0题 2人
1题 3人
2题 4人
3题 6人
4题 9人
5题 14人
6题 21人
7题 32人

【在 N*****N 的大作中提到】

m*t2007-07-16 07:07

14 楼

若有n题时，最大人数是m-1人
则n+1题时，人数为l-1
l-[l/3]=m

【在 m**t 的大作中提到】

: 逆推
: 21人
: 0题 2人
: 1题 3人
: 2题 4人
: 3题 6人
: 4题 9人
: 5题 14人
: 6题 21人
: 7题 32人

b*g2007-07-16 07:07

15 楼

怎么“逆”推？

【在 m**t 的大作中提到】

: 逆推
: 21人
: 0题 2人
: 1题 3人
: 2题 4人
: 3题 6人
: 4题 9人
: 5题 14人
: 6题 21人
: 7题 32人

m*t2007-07-16 07:07

16 楼

从最小的开始推

【在 b*****g 的大作中提到】

: 怎么“逆”推？

N*N2007-07-16 07:07

17 楼

很接近了...

【在 m**t 的大作中提到】

: 逆推
: 21人
: 0题 2人
: 1题 3人
: 2题 4人
: 3题 6人
: 4题 9人
: 5题 14人
: 6题 21人
: 7题 32人

m*t2007-07-16 07:07

18 楼

哪儿有问题啦？
我就是找了个上限
难道其实这个上限太大？
不够精确？？
哎。。。

【在 N*****N 的大作中提到】

: 很接近了...

N*N2007-07-16 07:07

19 楼

nod，太大，呵呵

【在 m**t 的大作中提到】

: 哪儿有问题啦？
: 我就是找了个上限
: 难道其实这个上限太大？
: 不够精确？？
: 哎。。。

m*t2007-07-16 07:07

20 楼

4个题目的能列举
五个就。。。
好多啊！！！
哭
我再想想好了

【在 N*****N 的大作中提到】

: nod，太大，呵呵

N*N2007-07-16 07:07

21 楼

非常接近了，我也只知道答案，想穷举出来，也fail了 :(

c*t2007-07-16 07:07

22 楼

18?

【在 N*****N 的大作中提到】

: 非常接近了，我也只知道答案，想穷举出来，也fail了 :(

m*t2007-07-16 07:07

23 楼

是20
5个题的也错了，那个应该是13
恩，就是这样的！！
*^^*

【在 N*****N 的大作中提到】

: 很接近了...

c*e2007-07-16 07:07

24 楼

N*N2007-07-16 07:07

25 楼

把答案整理一下，给大家看看吧:)

【在 m**t 的大作中提到】

: 是20
: 5个题的也错了，那个应该是13
: 恩，就是这样的！！
: *^^*

m*t2007-07-16 07:07

26 楼

让我想想啊
我表达能力弱弱。。。

【在 N*****N 的大作中提到】

: 把答案整理一下，给大家看看吧:)

m*t2007-07-16 07:07

27 楼

我们可以把这个问题推广到n道题的情况，有m个学生作答
这是个抽屉原则问题
我们可以考虑不符合题目条件的最少学生情况
我们从第n题开始看，根据抽屉原则，对于这一道题，一定有不多于[m/3]个学生有同样
的答案
那也就是说，选另两个答案的学生数最少是l=m-[m/3]
这里[]是下取整
接着看第n-1题。
对于第n题选一样答案的学生，这里不用算上了。对于第n题选两个答案的学生，在第n-
1题，他们选同一个答案的学生数一定不多于[l/3]。那么同样的，选另两个答案的学生
数最少为l-[l/3]个
类推
到第一题，如果我们发现选两个答案的学生数不少于3，那么就与题目违背了。
所以我们的目的就是找出于题目要求违背的最少学生数。
0题，3学生，显然
1题，4学生，显然
2题，x学生。x为满足4=x-[x/3]的最小解
x=5
3题，y学生。y为满足5=y-[y/3]的最小解
y=7
4题，z学生。z为满足7=z-[z/3]的最小解
z=10
5题，s学生。s喂满足10=s-[s/3]的最小解
s=14
6题，t学生。t为满足14=t-[t/3]的最小解

【在 N*****N 的大作中提到】

N*N2007-07-16 07:07

28 楼

r赞，太牛了

n-

【在 m**t 的大作中提到】

: 我们可以把这个问题推广到n道题的情况，有m个学生作答
: 这是个抽屉原则问题
: 我们可以考虑不符合题目条件的最少学生情况
: 我们从第n题开始看，根据抽屉原则，对于这一道题，一定有不多于[m/3]个学生有同样
: 的答案
: 那也就是说，选另两个答案的学生数最少是l=m-[m/3]
: 这里[]是下取整
: 接着看第n-1题。
: 对于第n题选一样答案的学生，这里不用算上了。对于第n题选两个答案的学生，在第n-
: 1题，他们选同一个答案的学生数一定不多于[l/3]。那么同样的，选另两个答案的学生

h*02007-07-16 07:07

29 楼

是牛，但伊还没做完呀。还得证明19个不会违反呀。得给出构造。

【在 N*****N 的大作中提到】

: r赞，太牛了
:
: n-

m*t2007-07-16 07:07

30 楼

我kick你
你构造吧
俺累
或者，我想想怎么证明这个是最小上限好了

【在 h*****0 的大作中提到】

: 是牛，但伊还没做完呀。还得证明19个不会违反呀。得给出构造。

N*N2007-07-16 07:07

31 楼

这个倒是，不过俺也没弄出来，就不强求了，不过有兴趣可以试试。
俺花了两个多小时，弄了一个，但是错了

【在 h*****0 的大作中提到】

: 是牛，但伊还没做完呀。还得证明19个不会违反呀。得给出构造。

h*02007-07-16 07:07

32 楼

耐斯曼，你的科学态度不严谨呀。
你怎么知道19是正确答案，也可以是18,17嘛。现在说19是正确答案，万一以后有WSN拿
这个题去骗MM，结果弄错了，MM跑了，你负得起责吧？万一以后有WSN拿这个题去发
Paper，被拒了，导致不能毕业，你负得起责吗？万一以后有WSN拿这个题去做计算做实
验，地球爆炸了，你负得起责吗？

【在 N*****N 的大作中提到】

: 这个倒是，不过俺也没弄出来，就不强求了，不过有兴趣可以试试。
: 俺花了两个多小时，弄了一个，但是错了

b*g2007-07-16 07:07

33 楼

万一有人把这篇转了joke
奈斯曼负得起责任么？ :)

【在 h*****0 的大作中提到】

: 耐斯曼，你的科学态度不严谨呀。
: 你怎么知道19是正确答案，也可以是18,17嘛。现在说19是正确答案，万一以后有WSN拿
: 这个题去骗MM，结果弄错了，MM跑了，你负得起责吧？万一以后有WSN拿这个题去发
: Paper，被拒了，导致不能毕业，你负得起责吗？万一以后有WSN拿这个题去做计算做实
: 验，地球爆炸了，你负得起责吗？

N*N2007-07-16 07:07

34 楼

ft，唐僧啊.....原体标答是19个，远作者也没给出构造，俺自己构造又失败了 :(

【在 h*****0 的大作中提到】