如何确定N匹马的M条轨道的秩

Question

提供N匹马和M(M <= N)条赛道，但没有计时器，那么你在一个回合中所能得到的就是M匹马的顺序。问题是，如果你想知道所有马的排名，至少需要多少轮?

。N=3, M=3, Round=1; N=3, M=2, Round=3; N=4, M=3, Round=3;

当N=1000, M=3时，什么是Round ?

Answer 1

你可以用信息论得到一个下界。

每场比赛给你log(m!)比特的信息，而你需要log(n!)比特。因此，比赛数量的自然下界是log(n!)/log(m!)。

Answer 2

问题的正式定义-

http://www.math.uiuc.edu/西方海军学校规则/ksetsort.html