Guys, don't expect any outstanding mathematical beauties or useful algorithms in life. I am writing just out of pure sporting interest. I was interested in the problem published here , with which American prisoners while away their huge sentences. Judging by the comments to the article, it has already aroused some interest in the community. I understand that I'm not doing very well, I should have given the people time to think for themselves. However, I repent, I am a sinner, I cannot resist. And I post my decision here. Who cares, welcome to cat. If you want to do some more thinking on your own, don't read it yet.
So, the task itself. I will formulate it a little more clearly than in the article itself (alas, the translation there is a little crooked).
The dial (as in Figure 1) can point to any integer from 1 to n when rotated counterclockwise. The countdown starts from 1, then the arrow turns sequentially (always counterclockwise) one position, then two, then three, and so on, until the last turn by n-1 position. We collect the sequence of all numbers pointed to by the arrow.
For example, if n = 12, you get the sequence 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. It can be seen that there are repeating numbers in it.
And for n = 8, the sequence will be 1, 2, 4, 7, 3, 8, 6, 5. And there are no repeating numbers in it.
The question is, for what values of n are the numbers in the sequence not repeated?
Presented by Gary Gordon and Denise Ozbay, November 2020 Issue of Mathematical Horizons.
Let's call the sequence, which is constructed in the problem, the sequence of the n-dial . And numbers, n for which this sequence does not contain repeating numbers, are suitable .
Let's start by getting a very serious tip. Almost immediately ready-made answer. I didn’t go to American prisons, and I don’t know if computers are available to the inmates there. But I have my war horse on my table! So it's a sin not to use it. We launch our favorite jupyter notebook and enter a small program:
def getSeq(n): # n-
lst=[]
s=1 #
d=1 #
for i in range(0, n):
lst.append(s)
s=(s+d) % n
if s==0:
s=n
d=d+1 # 1
return lst
def testSeq(lst): #
if len(set(lst)) == len(lst):
return True
return False
def getList(n): # , 2 n
lst=[]
for i in range(2, n):
if testSeq(getSeq(i)):
lst.append(i)
return lst
Running getList (12345) gives a list of 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
So, it looks very likely that only powers of two are valid numbers, and nothing else. It only remains to prove it. More precisely, two statements will have to be proved:
1) Any power of two is a suitable number.
2) Any number that is not a power of two is not suitable.
First, let's see where the repeating numbers come from in the n-dial sequence.
The sequence starts from 1. Its increment at the first step is also equal to 1, and then with each step it increases by 1. The remainder of division by n is taken as the result. Moreover, if the remainder is zero, then the result is assumed to be equal to n. Let's try to construct such a sequence for some not very large number n. For example n = 6:
s (1) = 1 (mod 6) = 1
s (2) = 1 + 1 (mod 6) = 2
s (3) = 2 + 2 (mod 6) = 4
s (4) = 4 + 3 (mod 6) = 7 (mod 6) = 1
s (5) = 7 + 4 (mod 6) = 11 (mod 6) = 1 + 4 (mod 6) = 5
s (6) = 11 + 5 (mod 6) = 16 (mod 6) = 5 + 5 (mod 6) = 4
We see that two pairs coincided: s (1) and s (4), and s (3) and s (6). Moreover, if we take the values not modulo, the difference between the larger and smaller elements of both pairs is a multiple of 6. That, in general, is quite understandable. The final value is taken modulo n. And if, before taking the modulus, the numbers differ by n (or a multiple of n), then the final values will coincide.
On the other hand, since the increment we have at each step increases by 1. And it is clear that the above differences are equal to the sums of some consecutive numbers. For example, for the pair s (1), s (4):
7 = 1 + (1 + 2 + 3)
And for the pair s (3), s (6):
16 = 4 + (3 + 4 + 5)
For the first the difference is 6 for the pair, and 12 for the second.
Thus, we come to an important conclusion:
If coinciding numbers appear in the sequence of the n-dial, then n or its multiple can be represented as the sum of some consecutive numbers, the largest of which does not exceed the number n-1.
First, we prove an auxiliary statement:
Any number that is not a power of two can be represented as a sum of consecutive numbers. No power of two can be represented by the sum of consecutive numbers.
Let's think about how to generally represent some number as a sum of consecutive numbers. For the odd ones, this is quite simple. If A is odd, then it can be represented by a pair:
A = [A / 2] + ([A / 2] + 1), where [] means the integer part of the number.
For example 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
It's just that for multiples of 3. If A is a multiple of 3, then:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
Similarly, if A is a multiple of 5:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
And in general, if the number A has an odd divisor B, it can be represented as a sum of B consecutive numbers, and the number A / B is exactly in the middle.
Examples:
27 = 3 * 9. Hence 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10.50
= 5 * 10. Hence 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
The opposite is also obvious. If a number is representable as the sum of an odd number of consecutive numbers, then it has an odd divisor, and the representation itself has the form described above. Therefore, the power of two cannot be the sum of an odd number of consecutive numbers , because it has no odd divisors.
But what about the sum of an even number of consecutive numbers? The sum of two consecutive numbers is always odd. This is hopefully obvious. The sum of four can be thought of as the sum of two pairs, each of which is odd. So the sum of four is even. The sum of six is again odd, the sum of eight is even, and so on. Those. the sum of an even number of consecutive numbers is even if their number is a multiple of 4, and odd if it is a multiple of only 2.
Let an even number A be the sum of 4 * k consecutive numbers. For simplicity, let k = 1, for large k the reasoning is completely analogous:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Divide this equality by 2:
A / 2 = (4 * a + 6) / 2 = 2 * a + 3 = (a + 1) + (a + 2).
Those. again we get the sum of consecutive numbers.
Therefore, if for an even number A there is a representation in the form of the sum of an even number of consecutive numbers, then some representation in the form of a sum of consecutive numbers exists for A / 2 .
For example:
26 = 5 + 6 + 7 + 8. Hence 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Suppose that for the Nth power of two there is a representation in the form of a sum of an even number of consecutive numbers (there is no representation in the form of an odd number for it, as shown above). Then there is a representation in the form of a sum of consecutive numbers for the degree N-1. And the number of terms in it is also even. By induction, the same can be said about the degree N-2 and about the degree N-3 and, in general, about any degree less than N. But there is no representation in the form of a sum of consecutive numbers for the number 4, which is easy to see. Therefore, no power of two can be represented as a sum of consecutive numbers .
On the other hand, any number that is not a power of two can be represented as a sum of consecutive numbers. If this number is odd, it can be represented as a pair. If it is even and not a power of two, then it has at least one odd divisor. And representable through it.
The auxiliary statement is proved.
Consider the entire n-dial sequence.
s (1) = 1 (mod n)
s (2) = 1 + 1 (mod n)
s (3) = 2 + 2 (mod n)
s (4) = 4 + 3 (mod n)
…
s (n ) = s (n-1) + n-1 (mod n)
Let n be a power of two. Then 2 * n, 4 * n, 8 * n, etc., are also powers of two. And as a sum of consecutive numbers, they are not representable. Representable are 3 * n, 5 * n, 6 * n, 7 * n, 9 * n, etc. Those. the number m * n must have at least one odd divisor. However, even the smallest of these multiples, 3 * n, must be represented as
(n - 1) + n + (n + 1).
There are no other representations of the number 3 * n. For n as a power of two has no representations at all (see the auxiliary statement). But the terms in this sum should not exceed the number n - 1. Therefore, 3 * n as a difference will never appear. For other multiples, the reasoning is exactly the same. Of course, neither n nor 2 * n will appear as differences either, as powers of two. So any power of two is a suitable number.
Statement (1) is proved.
Now let n not be a power of two. Those. representable as a sum of consecutive numbers. The difference between the first and the last member of the sequence (before taking the module by n) will be:
d = 1 + 2 + 3 +… + (n-1).
And the differences between the members of the n-dial sequence (before taking the module) will be any partial sums of this series. If n is representable as a sum of consecutive numbers, then the largest possible numbers that make up such a sum are
[n / 2] and [n / 2] + 1. ([] is an integer part of a number)
All other variants of such a sum are made up of even smaller numbers ... This means that the members of the sequence of the n-dial, with a difference before taking the modulus equal to n, will certainly be found. And after taking the module, they will give the matching numbers. Those. any n that is not a power of two, and therefore representable as a sum of consecutive numbers, is not a suitable number.
Statement (2) is proved.
In total, the task is completely solved. Suitable numbers are any powers of two and not others. To freedom with a clear conscience !!!
The moral of this fable is perhaps only one. Guys, even if you do pure math, don't neglect computational experiments. Yes, such experiments prove nothing. However, they can give a well-founded guess. Although it may not be as simple as here. And proving is usually much easier than guessing. I would be glad if someone found this presentation useful and interesting.