Finding the $M^{th}$ person from randomly chosen $S^{th}$ out of $N$ people in a circle?

43 Views Asked by At

$N$ people are sitting in a circle, numbered clockwise from $1$ to $N$. Person number $S$ is chosen at random, and we count $M$ people starting from him, and proceeding clockwise, going back to $1$ after counting person $N$.

What is the number of the last person to be counted?

The answer is: $$((S - 1 + M - 1) \bmod N) + 1$$

I understand the $(S + M -1) \bmod N$ part, since we start from person $S$, and count $M$ people starting from that person, so in total we count $M$ plus $M-1$ people after him. I also understand the need to $\bmod N$ given the circle.

But what is the mathematical rationale to subtract another $1$ from S, and then add $1$ at the end?

P.S. not sure if this question counts as "number theory" or "abstract algebra" or something else, would like to know which one it is.

1

There are 1 best solutions below

2
On BEST ANSWER

Hint: the additions and subtractions of $1$ are compensating for the fact that you numbered the people from $1$ to $N$ rather than from $0$ to $N-1$.