How to determine the rank of N horses with M-tracks?

Question

Providing N horses and M (M <= N) tracks, but without a timer, all you could get from one round is the order of the horses M. The question is, how many rounds at least if you want to get the title of all horses?

eg. N=3, M=3, Round=1; N=3, M=2, Round=3; N=4, M=3, Round=3;

What is Round when N = 1000, M = 3?

Answer 1

You can get a lower bound on information theory.

Each race gives you a bit (m!) Of information, and you need the log (n!) Bits. Thus, the natural lowest number in terms of the number of races is log (n!) / Log (m!).

Answer 2

The formal definition of a problem is

http://www.math.uiuc.edu/~west/regs/ksetsort.html