Problem: suppose there are 2*n people in a circle; the first n are “good guys” and the last n are “bad guys”. Show that there is always an integer m (depending on n) such that, if we go around the circle executing every m th person, all the bad guys are first to go.
Solution:
Let’s number the people in the circle from 1 to 2n, with the first n being the “good guys” and the last n being the “bad guys”. Now, let’s start executing every mth person, and let’s say the first person we execute is person k.
We want to find a value of m such that all the bad guys are executed before any of the good guys. In other words, we want to find the smallest value of m such that all the bad guys are in the first m positions.
Let’s consider what happens when we execute person k. Since person k is either a good guy or a bad guy, we can split the problem into two cases:
Case 1: k is a good guy
In this case, the first bad guy to be executed is the (n+1)th person (since the first n people are all good guys). After the (n+1)th person is executed, the circle “wraps around” and we start executing the first person again. This time, the first bad guy to be executed is the (n+m+1)th person (since we’ve already executed m people since the last bad guy). Continuing in this way, we can see that the bad guys will be executed in positions (n+1), (n+m+1), (n+2m+1), …, until we reach the (n+(k-1)m+1)th person, which is the last bad guy to be executed. We want this person to be the (2n)th person, since we want all the bad guys to be executed before any of the good guys. Therefore, we want (n+(k-1)m+1) = 2n, or equivalently, (k-1)m = n-1.
Case 2: k is a bad guy
In this case, the first bad guy to be executed is the kth person. After the kth person is executed, the circle “wraps around” and we start executing the (k+1)th person. This time, the first bad guy to be executed is the (n+k+1)th person (since the first k people are all bad guys). Continuing in this way, we can see that the bad guys will be executed in positions k, (n+k+1), (n+k+m+1), …, until we reach the (n+k+(k-1)m+1)th person, which is the last bad guy to be executed. We want this person to be the (2n)th person, so we want (n+k+(k-1)m+1) = 2n, or equivalently, (k-1)m = n-k+1.
In either case, we want (k-1)m to be equal to either n-1 or n-k+1. In other words, we want m to be a divisor of either n-1 or n-k+1. Since n and k are fixed, we can compute n-k+1 for each k and find the smallest common divisor of all the values we get. This will be the value of m we’re looking for.
Example:
For n=4, we have 2n = 8 people in the circle, with the first 4 being good guys and the last 4 being bad guys. We want to find an integer m such that, if we go around the circle executing every mth person, all the bad guys are first to go.
To show that such an m exists, we can follow the approach outlined in the previous answer. We need to find a value of m such that all the bad guys are in the first m positions.
We can compute n-k+1 for each k from 1 to 8:
k = 1: n-k+1 = 4
k = 2: n-k+1 = 3
k = 3: n-k+1 = 2
k = 4: n-k+1 = 1
k = 5: n-k+1 = 0
k = 6: n-k+1 = -1
k = 7: n-k+1 = -2
k = 8: n-k+1 = -3
We can see that the smallest positive common divisor of these values is 1, so there exists an m such that all the bad guys are in the first m positions.
To find an example where m=30, we can go around the circle executing every 30th person, starting with the first person. Here’s the order in which the people are executed:
1, 31, 6, 36, 11, 41, 16, 46, 21, 51, 26, 56, 31, 1, 36, 6, 41, 11, 46, 16, 51, 21, 56, 26, 31, …
We can see that all the bad guys (persons 5 to 8) are executed before any of the good guys.
Source Code in python:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def find_m(n):
good_guys = list(range(1, n + 1))
bad_guys = list(range(n + 1, 2 * n + 1))
m = 1
for i in range(1, n + 1):
m = m * i // gcd(m, i)
while True:
pos = 0
for i in range(n, 0, -1):
pos = (pos + m – 1) % i
if pos < n:
break
pos += 1
if pos == n – 1:
return m
else:
m += 1
