0
$\begingroup$

Imagine 2 circles connected at 1 point. The smaller of the circles has n equally spaced points around its perimeter labelled $1...n$. The larger of the circles has $n^2$ equally spaced points around its perimeter labelled $1...n^2$.

The points on the larger circle are in a randomized order, while the points on the smaller circle are in numerical order. The smaller circle rotates around the larger circle connecting each until it gets back to its starting position.

So here's my question. In the worst case scenario, how many "matches" will there be? That is, a labelled point on the smaller circle matching with its corresponding point on the larger circle, e.g. 1 with 1, 345 with 345. Any other probabilistic information about this problem would be very useful as well.

To guarantee a match, after each full revolution of the larger circle, the smaller circle's starting point is incremented by 1, and this continues until it starts from all points $1...n$.

For example, in the case $n = 1000$, the smaller circle starts at 1 and it happens to be touching the point 123,456 on the larger circle, lets call this match 1:123,456. On the second cycle, the smaller circle will start from 2, so the beginning match will be 2:123,456, so on and so forth.

I hope I explained that clearly. Thank you for your help.

  • 0
    There's a lot of ambiguity here. a) You introduce a "match" as "a labelled point on the smaller circle matching with its corresponding point on the larger circle, e.g. $1$ with $1$, $345$ with $345$, but later you say "let's call this match $1$:$123,456$", which doesn't fit that definition. b) You introduce the problem with one revolution, then you talk about this problem for a while, then you say that there are $n$ revolutions. Is this meant to be an integral part of the problem? c) You never say what "worst" means. d) The answer seems obvious to me, so I suspect there's more I misunderstood.2012-12-23
  • 0
    Sorry about the ambiguity, thank you for your reply though, I'll try to clear things up for you. a) Yes you're right this was confusing. A match should be when the numbers are the same. e.g. 1:1 2:2 3:3 45:45 999:999 are all matches. 34:85 98:46 578:565 are not matches. b) The reason for $n$ revolutions is to guarantee a match. 1 revolution does not guarantee this. c) Worst means the least amount of possible matches after $n$ revolutions. That is, the smaller circle has made $n$ revolutions around the larger circle. d) I really hope this clears things up. Hopefully that helps?2012-12-23
  • 0
    Please clarify the question itself; people shouldn't have to read through long comments to understand the question.2012-12-23

1 Answers 1