滑道弹珠定三甲问题
假设有N颗弹珠，因为表面光滑度互有不同，其在标准滑道（微下坡）前进的速度亦互有不同。现在有五条并排的标准滑道，每次可让五颗弹珠同时比拼速度定出名次。同时设定假如一颗弹珠比另一颗走得快，那么它俩比赛多少次结果都会一样。
但是不能用秒表等工具来分开测量弹珠的速度，因为每次比赛的气温、湿度等客观条件会影响时间的准确性。换句话说只能用一轮又一轮的滑道赛跑来找出弹珠间的速度关系。
现在要求用最少的赛跑次数找出最快的三颗弹珠。
假如N=25，那么答案很多人都知道，就是七次：首先五次初赛找出五个分组冠军，然后一次决赛找出全场总冠军，并假设决赛名次为A1、B1、C1、D1、E1，再把A至E定为初赛分组的编号。最后让A2、A3、B1、B2、C1进行一场遗材赛，就能定出三甲。
那么，现在的问题是：当N=50、75、100时，最少需要赛多少次才能定出三甲？（还是规定只有5条赛道。） 看来这里不是很活跃的样子。。。先给一个50球14次的解法好了。。。如果大家没有兴趣就让它沉底吧。。。
目前猜测最优解是75球21次、100球28次，但是很难建构。。。
50球14次定三甲：
首先50球分10组每组5球，进行10场初赛。
让其中5组的分组冠军进行第11战，设三甲顺序为X1、Y1、Z1（把其代表的小组也分别定为X、Y、Z组，下同）。
X1跟另外4组的分组冠军进行第12战，并假设剩下来的第10个分组冠军为T1。这里生出三个分支：
1：X1在第12战得第三或更差。那么让第12战的三甲和T1进行第13战，并假设此战三甲顺序为A1、B1、C1。
那么A1、B1、C1就是10个分组冠军里的总三甲，A1也就是全场总冠军。
让A2、A3、B1、B2、C1进行第14战，即可决出全场总三甲！（第14战冠、亚军为全场总亚、季军。）
2：X1在第12战得第二，并假设第12战的三甲顺序为P1、X1、Q1。
那么让P2、X1、T1、T2、T3进行第13战，并假设此战三甲顺序为A1、B1、C1。这里再生出三个分支：
2.1：A1 = P2：P1、P2为全场总冠、亚军，最后第14战让B1、P3两者PK争夺全场总季军。
2.2：A1 = X1：P1、X1为全场总冠、亚军，最后第14战让B1、Q1、X2、Y1四者争夺全场总季军。
2.3：A1 = T1：让P1、T1、B1、C1四者进行第14战，此战三甲就是全场总三甲。
3：X1在第12战得第一，并假设第12战的三甲顺序为X1、P1、Q1。
那么让X2、P1、Y1、T1、T2进行第13战，并假设此战冠、亚军分别为A1、B1。这里再生出四个分支：
3.1：A1 = X2：X1、X2为全场总冠、亚军，最后第14战让B1、X3两者PK争夺全场总季军。
3.2：A1 = P1：X1、P1为全场总冠、亚军，最后第14战让B1、P2、Q1三者争夺全场总季军。
3.3：A1 = Y1：X1、Y1为全场总冠、亚军，最后第14战让B1、Y2、Z1三者争夺全场总季军。
3.4：A1 = T1：让X1、T1、B1、T3四者进行第14战，此战三甲就是全场总三甲。
如果上面有任何错漏，或者有更好的解法，欢迎指正！ 本坛有过类似的讨论，不过是棋赛，有5个台位，即每轮可下5盘棋。棋战与赛车的区别在于，同一轮不同台位之间不能直接比较。 100个的可以如下图的比较，看看有什么问题么？
在图一中，第一批要比20次，第二批要比4次，第三批比1次。
在图二中，有2次比较。
因此一共27次。
受楼上启发弄了两张图，分别代表25和50参赛者时的解法。。。
75参赛者暂时最少15+3+3=21次，100参赛者暂时最少20+4+3=27次，估计还有优化空间，就不做图了。。。 对于任意的$N$，比赛次数为$x_1+x_2+x_3$。
其中：
找出第$1$名至少需要$x_1=(N-1)/4$次比赛，
第$1$名确定后，确定第$2$名至少需要$x_2=(\log_5(N)-1)/4$次比赛，
前$2$名确定后，确定第$3$名还需要$x_3=(\log_5(N))/4$次比赛。
其中$x_1$取上整，
$x_2$和$x_3$的取整需要根据$N$的五进制表示分情况讨论，比较麻烦。
对于楼主需要的数据，结果如下：
$N$ $x_1$ $x_2$ $x_3$ 总次数
$25$ $6$ $1$ $0$ $7$
$50$ $13$ $1$ $0$ $14$
$75$ $19$ $1$ $1$ $21$
$100$ $25$ $1$ $1$ $27$
$125$ $31$ $1$ $1$ $33$
#####
从上表可以看到，$x_2$和$x_3$增长得非常缓慢。
对于更大的$N$，$x_2+x_3$的值如下：
$N$ $x_2+x_3$
$5^2$ $1$
$5^3$ $2$
$5^4$ $2$
$5^5$ $3$
$5^6$ $3$
$5^7$ $4$
$5^8$ $4$
$5^9$ $5$
$5^10$ $5$
$5^11$ $6$
$5^12$ $6$
$5^13$ $7$
$5^14$ $7$
$5^15$ $8$
$5^16$ $8$
$5^17$ $9$
$5^18$ $9$
$5^19$ $10$
…… ……
#####
更一般地，
当$(N-1)/4$是大于$1$的整数时，$x_2+x_3=\ceil(\frac{\log_5 N-\log_5 1.8}{4})+\ceil(\frac{\log_5 N-2}{4})$。
当$(N-1)/4$不是整数时，情况比较复杂，难以找到$x_2+x_3$的通式。 题目没吃透，10颗珠怎么算？ 本帖最后由 毒酒滴冻鸭 于 2019-12-19 21:46 编辑
王守恩 发表于 2019-12-18 09:52
题目没吃透，10颗珠怎么算？
十颗珠的话一般人可能以为需要四场，但是其实有一个妙解可以三场解决：
第一场定出A1,A2,A3,A4,A5，此时A4,A5淘汰。
第二场让A2和另外四颗（设为B1,B2,B3,B4，余下最后一颗为C1）比，此时有以下四种情况：
一、A2得第一，即第二场结果为A2,B1,B2,B3,B4，则B2,B3,B4淘汰，第三场A1,A2,A3,B1,C1定出最终三甲。
二、A2得第二，即第二场结果为B1,A2,B2,B3,B4，则A3,B2,B3,B4淘汰，第三场A1,A2,B1,C1定出最终三甲。
三、A2得第三，即第二场结果为B1,B2,A2,B3,B4，则A2,A3,B3,B4淘汰，第三场A1,B1,B2,C1定出最终三甲。
四、A2得第四或第五，即第二场三甲为B1,B2,B3，则A2,A3,B4淘汰，第三场A1,B1,B2,B3,C1定出最终三甲。
就是这样，难点是第二场想出让A2参与而不是A1或A3。 本帖最后由 王守恩 于 2019-12-27 13:30 编辑
毒酒滴冻鸭 发表于 2019-12-19 21:40
十颗珠的话一般人可能以为需要四场，但是其实有一个妙解可以三场解决：
第一场定出A1,A2,A3,A4,A5， ...
是这样吗？
比赛 1 次，最多可以在 5 颗里找出最快的三颗。
比赛 2 次，最多可以在 7 颗里找出最快的三颗。
比赛 3 次，最多可以在 10 颗里找出最快的三颗。
比赛 4 次，最多可以在 13 颗里找出最快的三颗。
比赛 5 次，最多可以在 17 颗里找出最快的三颗。
比赛 6 次，最多可以在 21 颗里找出最快的三颗。
比赛 7 次，最多可以在 25 颗里找出最快的三颗。
比赛 8 次，最多可以在 29 颗里找出最快的三颗。
还有：
最快的三颗是不分快慢，还是需要分出快慢，答案是不同的。
页:
[1]