数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

[讨论] 毒酒问题(加强版)

  [复制链接]
 楼主| 发表于 2011-8-15 07:59:47 | 显示全部楼层
计算机用随机算法,长期计算竟然找到了32个囚徒1000桶酒的解:
83411249
5a91124a
8041124a
4331124c
00811251
09411252
f0411254
35811261
20811262
51211264
3e511264
a4011289
03611289
b0e1128a
0a01128a
1c71128c
8341128c
40a1128c
00111291
0a811292
04111294
19811294
060112a1
4e0112a2
980112a4
d4111309
8411130a
a001130c
1f61130c
40811311
22411312
11111314
91311321
a0211322
01311324
00011449
4501144a
9ca1144c
4e01144c
3ee11451
08011451
05411452
b6211454
41211454
29511461
08011462
0c911464
c2011464
a1c11489
94b11489
8021148a
b081148c
80211491
15011492
12811494
190114a1
429114a1
100114a2
880114a4
350114a4
42a114a4
76611509
81011509
2001150a
0a81150c
11111511
63411511
90011512
c2411514
34111514
0a811521
07211522
f0811522
21a11524
1c111849
01211849
8421184a
0841184c
c5211851
12611851
39811852
80b11852
43811854
a4211854
02011861
6c911861
d2411864
04111864
51911889
1881188a
4e31188c
d5011891
0c011892
b0a11892
21511894
880118a1
339118a1
280118a2
a00118a4
02011909
0211190a
1021190c
40011911
8c111912
0a411914
40411921
40411922
20111924
07012249
0581224a
8291224c
16c12251
81012252
82112254
90012262
68512262
00012264
c9c12289
1301228a
9451228c
42c1228c
c0012292
4db12294
206122a2
040122a4
20012309
a501230a
4831230c
2081230c
00b12311
20412312
39212314
37212321
01012322
11212324
40812449
1401244a
9101244c
10212451
e4012452
b2a12454
00312462
c0312489
0801248a
03a1248c
2d11248c
85012491
04312492
59412492
59412494
b4212494
070124a1
92c124a1
8d8124a2
405124a4
81b12509
1001250a
2001250c
05812511
66012512
00112514
8a112521
00112522
91112849
8261284a
0a91284a
2681284c
4811284c
15512851
00012852
24312854
81a12861
9d012862
63212862
80012864
c2112889
d391288a
0001288c
11b12891
20012892
50012894
0e412894
ca0128a1
406128a2
480128a4
a31128a4
82a12909
0421290a
0301290c
a0a1290c
05012911
e5712912
01a12914
80012921
42512922
21412924
0241424a
6831424a
1d21424c
0e014252
9cd14261
6f214261
94014262
a0214264
9291428a
10a14292
0e014294
454142a1
cb2142a2
0c4142a4
85014309
0481430a
0951430c
08114311
63814312
10114312
31214321
c1c14324
ec014449
f081444a
0201444a
2081444c
00f14451
02214452
08814462
b8014464
44814489
7001448c
0d81448c
45014491
00414492
c9414494
6c1144a1
338144a2
482144a4
82014509
6c01450a
a391450a
10a1450a
0c014511
81814512
5a014514
b8d14514
8a114521
13414521
8c014522
48014524
00214849
6601484a
18b1484a
d611484c
c0014851
cce14852
80a14854
00c14864
71414889
0001488a
2051488c
2d314891
80114891
09814892
8a514894
17014894
022148a1
0b0148a4
1a814909
37414909
2811490a
1201490c
02114911
1d614912
a2814912
48814914
24814921
08114922
28014924
71614924
06918249
60618249
c2018251
08e18251
40118252
01318254
02a18261
90018262
0401828c
a9a18291
71018292
89918292
02318294
00a182a1
418182a2
2191830a
0951830c
f0218311
51018312
4a518312
34118314
98c18314
c8018321
40918322
04e18324
19118324
f0118449
06018449
0911844a
01c1844c
90118451
3e018452
8c518461
57418461
29b18461
03c1848a
0261848c
01518491
04118494
400184a1
430184a4
4b118509
0081850c
11818512
0a118512
0c018514
d2918514
30018521
04718521
24418849
0a41884c
30f18851
31018852
02818854
35e18861
c1118861
81018862
68318864
0f818864
04418889
b211888a
c6d1888c
20c18891
08018892
4a618894
870188a2
10c188a4
21518909
6621890a
1861890a
0111890c
89218911
6a118912
27318914
00018914
01018921
e0018922
1f118922
a0e18924
2112124a
2422124c
02021251
00021252
a7921292
c0521294
2cc21294
c08212a2
1a021309
22021311
00021322
60521324
25121449
44021451
ac021452
42621452
28421454
c0321454
31221461
00a21464
89821489
d442148a
2ab2148a
00c21492
041214a2
00021509
2c52150c
49821514
85421524
b402184a
8ab2184a
1102184c
28021852
40a21864
10021892
a21218a1
232218a2
97021909
7142190a
09021912
e0821914
16821922
08422249
1002224a
00322252
25222254
02422261
48222262
23022264
54222264
1a02228a
98222291
261222a2
13122309
c042230a
ac82230a
c202230c
21322311
01222312
3c022312
02c22321
00122324
00d22449
86222449
08422451
41422452
05422454
10a22461
74b22462
40422464
a122248a
c2e2248c
48822491
16422491
08622492
84022494
004224a2
2282250a
56022512
00022514
25922521
14a22524
de822849
7c22284a
5502284c
00822851
55e22854
09022862
3a222864
4002288a
1092288c
c2c22891
2a722891
10122892
13022894
8c422894
429228a1
845228a2
452228a4
985228a4
00422909
6142290c
40c22911
08422912
5d522921
a1822922
00e22924
40d24249
04024251
08924254
c0624254
36024261
20924262
49024262
8b024264
b6124289
00024289
0022428c
24424291
55124292
494242a1
475242a2
9a9242a2
12d242a4
8542430a
2a02430c
a3c24311
20424321
40024322
1122444c
9c024451
16124452
5aa24454
80824454
11024461
d5024462
01924464
0e424464
32e24489
7c12448c
06124491
30524494
8b4244a1
d43244a2
d1524509
82a2450a
1902450c
00424512
bc924521
02c24522
24a24524
0222484a
18024854
10424861
80024864
3a624889
3092488a
8e32488c
00a2488c
81024891
15824892
22024892
11624894
a8024894
012248a2
2e8248a2
98624909
8002490a
4402490c
13b2490c
68c24911
0d024912
04224914
41124921
00424922
00824924
80028249
20a2824a
cf428251
91828252
79528252
8a028261
a4028264
0a028291
03228292
30428292
78828294
080282a1
102282a2
010282a4
21028309
40a2830a
05228311
c4628312
43828321
00028324
dce28449
00728452
6e028454
28128461
18128464
50c28489
2102848a
d232848a
a012848c
89128491
c4928492
8f028492
29028494
12228494
209284a2
576284a2
720284a4
41b28509
2022850a
6212850c
70a28511
08228512
d5528512
02428514
4c428524
00428849
0292884a
a042884c
09028851
0da28852
22028854
d8028854
e6628862
09328864
01c28889
1ac2888a
5002888c
03a2888c
00628892
60028894
22f28894
001288a1
500288a2
814288a4
9c028909
20c2890a
e6b2890c
82028911
55b28912
a4828914
05028921
39428922
0b228924
4014124c
0a441251
98941254
85141262
67d41262
40d41294
8a441314
99241324
19041449
04a4144c
e0941451
70741452
68841452
84341462
d0641464
ab741489
90441489
23241492
06841494
502414a1
0de4150a
66341511
a8241514
00841521
83141522
2a141849
c0641849
23341864
34441864
03a4188a
3004188a
2e04188c
88141892
80841894
612418a1
0fc418a1
404418a4
29a4190c
c4441911
40941912
11241914
41841922
99141924
1264224a
cf64224a
1014224c
44142254
03242264
12242289
45142289
5014228c
d8142291
836422a4
5c24230a
89142314
c0042321
61a42322
0b942324
04042324
0e842449
22e4244a
b0042452
e8842454
608424a4
18842509
0464250a
1a34250c
91042514
13542521
12a42522
20042849
19c4284a
20042851
00c42861
d9242861
40042862
0064288a
0034288c
20042892
a5042894
178428a1
000428a4
05342909
0904290a
d424290a
10a4290c
51942921
85242924
6004424c
08044251
04244252
00c44254
29c44261
01044264
f544428c
30044291
690442a2
01044309
0054430a
0004430c
80444311
54844312
15044321
a6c44449
73044449
5a144451
40044454
7a044461
30c44462
44044464
0a044489
0014448a
0614448c
80c444a1
4044450a
2d14450c
03a44511
08044512
28244514
b3044521
14444522
c9844522
a4444524
59044849
46b4484a
4504484c
20c44851
c8144852
a0144854
5c544854
21044862
00244864
34644889
d044488a
a8244891
08544894
87944894
64c448a1
2cb448a2
948448a4
42644909
2b84490a
0294490c
a0a44911
d1244912
00044922
10644924
c8144924
d204824a
8644824c
ca048252
85a48254
02148262
00848291
53448291
025482a2
080482a4
e4948309
02848311
c5c48314
41448321
40048322
0e248324
2d748451
48a48454
20748454
38248461
01448462
62b48462
50848464
00b48489
6114848a
9904848a
48048491
821484a2
87448509
0004850a
92048511
88748511
21048512
2e048521
46248522
94148524
32048849
9844884a
5004884c
00848852
30a48861
9b048861
80548862
c4048864
80648889
66c4888a
0604888c
68c4888c
40448892
00d48894
84b488a1
828488a2
b35488a4
00e488a4
12948909
8a14890a
0804890c
e0048912
51848914
39148921
12048922
68048924
64081249
c008124c
2878124c
05581289
1248128a
785812a4
00881309
5028130c
a1281311
28481321
00981449
9008144a
00e81452
8668148c
08181491
4c8814a4
00c81509
25b8150a
00381511
19481511
00481514
78481521
52181524
06181851
c0c8188c
01881891
99981892
63481892
402818a4
64b81909
4098190c
99081914
0a481924
a0182251
00382254
88082262
03082264
14982264
00082289
02082294
546822a2
8a98230a
84482314
5eb82321
14082324
e4f8244a
1928244a
90182451
c2982452
24982491
26482494
008824a4
1f082509
2a282511
b8082512
91c82514
00082521
30382524
40082851
65882852
c8182864
3c882864
2818288c
01082891
00282892
094828a4
11882909
4118290a
0188290c
10882911
2a082922
c2d82922
ac182924
08884249
10484251
2388428c
80c84291
821842a2
c00842a4
00384309
0058430a
07384311
8c184312
b8584314
82284322
04084449
2458444c
0a384452
20684454
22484462
61484464
08484494
49f844a1
025844a2
790844a4
41984509
af48450a
d808450a
f5384511
52184511
44184512
88a84512
0eb84514
17484514
00084524
0088484c
58c84851
50284852
8aa84854
d0084861
82284864
88084889
4028488a
8028488c
0c684891
2a084892
00084894
445848a1
1a9848a4
01e84909
1108490a
82f8490c
1488490c
04184914
1c184921
e2084921
18284922
88288249
2928824a
2288824c
7848824c
04488254
1c888261
0dc88289
19088291
36188292
31288294
9c5882a2
611882a2
0b1882a4
c0288311
98688312
04088314
f1f88322
1a088324
a0c8844c
4a08844c
20088462
02488464
03088489
11e8848a
0888848c
74d88491
02c88494
69388494
406884a1
1c2884a4
9028850c
a6588511
28888512
de088512
21088514
85188524
a0088849
0148884a
09e8884c
01288861
ec488862
02788864
84288889
1c28888a
e228888c
14588894
a3288894
822888a1
35b888a2
030888a2
121888a4
50f8890a
0218890a
0508890c
10488912
8c288914
08388921
09c88922
44888924
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-8-16 11:04:01 | 显示全部楼层
很有趣的题呀
看来还得花点时间看前面的讨论,
不然直接看楼上的数字 ,头很晕
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-8-16 11:10:50 | 显示全部楼层
我想到了数字电路里的 卡诺图 。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-8-31 11:33:12 | 显示全部楼层
竟然用上了随机算法啊,里海
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-8 11:08:53 | 显示全部楼层
想到1个方案,只需要29个人,而且可以证明2^n桶酒,只需要3n-1个人就可以了

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首贴奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-8 11:10:11 | 显示全部楼层
具体步骤要花时间整理下
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-8 20:23:42 | 显示全部楼层
整理的时候发现一个bug,失败
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-2-10 22:08:00 | 显示全部楼层
从概率上讲,$29$人是极有可能做到的。

只要是随机算法,运行时间足够长,有接近$100%$的概率能找到符合条件的解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-20 09:53:06 | 显示全部楼层
嘿嘿,俺看傻了,真是强啊!

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-13 16:40:01 | 显示全部楼层
楼上所说,N(N>20)年前就有结论了,这里的网友们现在还不知道的太少了,枉费我精神看了半天。

评分

参与人数 1贡献 +3 收起 理由
mathe + 3 已删之

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-1-18 17:28 , Processed in 0.112605 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表