Ball Game v2
Yolanda and Zachary are sitting at a round table with a number of other people (possibly 0). They play a game in which they pass a ball around the table, always to the person to the left. The ball starts with Yolanda, and after 2017 passes, Zachary has the ball. After additional passes, where is some positive integer, Yolanda has the ball again.
For how many integers between 1 and 2017 inclusive is it possible that Yolanda and Zachary are sitting next to each other?
The answer is 1441.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let n be the number of people sitting at the table. Note that n ≥ 2 . Starting from Yolanda and going clockwise, we label each person with the numbers 0 , 1 , 2 , … , n − 1 , so that after p passes, the person with the number p ( m o d n ) has the ball.
From the problem statement, we know that k + 2 0 1 7 ≡ 0 ( m o d n ) , since Yolanda ends up with the ball after k + 2 0 1 7 passes. Assuming that Zachary is sitting next to Yolanda, we also have 2 0 1 7 ≡ ± 1 ( m o d n ) , since the numbers next to Yolanda are 1 and n − 1 ≡ − 1 ( m o d n ) .
In order for this system of congruences to have a solution n ≥ 2 , we see that we must have g cd ( k + 2 0 1 7 , 2 0 1 7 ± 1 ) > 1 , since otherwise the only possible value for n would be 1, which is not possible. This gives us two cases:
Case 1: g cd ( k + 2 0 1 7 , 2 0 1 6 ) > 1
By the Euclidean algorithm, this can be simplified into g cd ( k + 1 , 2 0 1 6 ) > 1 . First, notice that k = 2 0 1 7 is a solution to this inequality. To easily count the number of solutions from 1 to 2016 inclusive, we count the number of solutions to g cd ( k + 1 , 2 0 1 6 ) = 1 , where 1 ≤ k ≤ 2 0 1 6 , and subtract by 2016.
By the definition of Euler's totient function, the number of solutions to g cd ( k + 1 , 2 0 1 6 ) = 1 , where 0 ≤ k ≤ 2 0 1 5 , is ϕ ( 2 0 1 6 ) = 5 7 6 . So, there are 2 0 1 6 − 5 7 6 = 1 4 4 0 solutions to g cd ( k + 1 , 2 0 1 6 ) > 1 in that interval. Since k = 0 and k = 2 0 1 6 are not solutions to this inequality, there are still 1 4 4 0 solutions the inequality for 1 ≤ k ≤ 2 0 1 6 .
Combining this with the solution k = 2 0 1 7 , we find that there are 1 4 4 1 solutions to g cd ( k + 2 0 1 7 , 2 0 1 6 ) > 1 , where 1 ≤ k ≤ 2 0 1 7 .
Case 2: g cd ( k + 2 0 1 7 , 2 0 1 8 ) > 1
We approach this case similar to the previous case. First, note that k = 1 is a solution. Then, for k > 1 , the Euclidean algorithm tells us that the inequality is equivalent to g cd ( k − 1 , 2 0 1 8 ) > 1 .
There are ϕ ( 2 0 1 8 ) = 1 0 0 8 solutions to g cd ( k − 1 , 2 0 1 8 ) = 1 , where 2 ≤ k ≤ 2 0 1 9 . So, there are 2 0 1 8 − 1 0 0 8 = 1 0 1 0 solutions to g cd ( k − 1 , 2 0 1 8 ) > 1 in that interval. Since k = 2 0 1 9 is a solution to the inequality, but k = 2 0 1 8 is not, there are 1 0 0 9 solutions to the inequality for 2 ≤ k ≤ 2 0 1 7 .
Combining this with the solution k = 1 , we find that there are 1 0 1 0 solutions to g cd ( k + 2 0 1 7 , 2 0 1 8 ) > 1 . where 1 ≤ k ≤ 2 0 1 7 .
Now, we must subtract the number of overcounted solutions in both cases. First, we count jthe number of k from 1 to 2017 inclusive such that k + 1 is even i.e. k is odd. There are 1 0 0 9 odd numbers from 1 to 2017 inclusive. We must also include k = 1 0 1 0 , since g cd ( 3 0 2 7 , 2 0 1 6 ) = 3 and g cd ( 3 0 2 7 , 2 0 1 8 ) = 1 0 0 9 . Thus, there are 1 0 1 0 overcounted solutions in both cases.
Finally, the total number of k from 1 to 2017 inclusive such that it is possible for Yolanda and Zachary to be sitting next to each other is 1 4 4 1 + 1 0 1 0 − 1 0 1 0 = 1 4 4 1 .