滑道弹珠定三甲问题

毒酒滴冻鸭

假设有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战，此战三甲就是全场总三甲。


如果上面有任何错漏，或者有更好的解法，欢迎指正！

hujunhua

本坛有过类似的讨论，不过是棋赛，有5个台位，即每轮可下5盘棋。棋战与赛车的区别在于，同一轮不同台位之间不能直接比较。

zhouguang

100个的可以如下图的比较，看看有什么问题么？
在图一中，第一批要比20次，第二批要比4次，第三批比1次。
在图二中，有2次比较。
因此一共27次。

毒酒滴冻鸭

受楼上启发弄了两张图，分别代表25和50参赛者时的解法。。。

毒酒滴冻鸭

75参赛者暂时最少15+3+3=21次，100参赛者暂时最少20+4+3=27次，估计还有优化空间，就不做图了。。。

KeyTo9_Fans

对于任意的$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-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-19 21:40
十颗珠的话一般人可能以为需要四场，但是其实有一个妙解可以三场解决：

第一场定出A1,A2,A3,A4,A5， ...

是这样吗？
比赛 1 次，最多可以在 5 颗里找出最快的三颗。
比赛 2 次，最多可以在 7 颗里找出最快的三颗。
比赛 3 次，最多可以在 10 颗里找出最快的三颗。
比赛 4 次，最多可以在 13 颗里找出最快的三颗。
比赛 5 次，最多可以在 17 颗里找出最快的三颗。
比赛 6 次，最多可以在 21 颗里找出最快的三颗。
比赛 7 次，最多可以在 25 颗里找出最快的三颗。
比赛 8 次，最多可以在 29 颗里找出最快的三颗。
还有：
最快的三颗是不分快慢，还是需要分出快慢，答案是不同的。