Chủ đề này có 1 trả lời

[GOONG]

Cho dãy số nhân các giá trị trong các số 0,1 ,...k-1 được định nghĩa:
;

Với giả thiết nào của k thì dãy nhận k giá trị 0,1,...,k-1

[QUANVU]

Bài này lâu quá không ai trả lời.Chắc nó cũ rồi à?

3rd APMO 1991
Problem 4

A sequence of values in the range 0, 1, 2, ... , k-1 is defined as follows: a1 = 1, an = an-1 + n (mod k). For which k does the sequence assume all k possible values?

Solution

Let f(n) = n(n+1)/2, so an = f(n) mod k. If k is odd, then f(n+k) = f(n) mod k, so the sequence can only assume all possible values if a1, ... , ak are all distinct. But f(k-n) = f(n) mod k, so there are at most (k+1)/2 distinct values. Thus k odd does not work.

If k is even, then f(n+2k) = f(n) mod k, so we need only look at the first 2k values. But f((2k-1-n) = f(n) mod k and f(2k-1) = 0 mod k, so the sequence assumes all values iff a1, a2, ... , ak-1 assume all the values 1, 2, ... , k-1.

Checking the first few, we find k = 2, 4, 8, 16 work and k = 6, 10, 12, 14 do not. So this suggests that k must be a power of 2. Suppose k is a power of 2. If f® = f(s) mod k for some 0 < r, s < k, then (r - s)(r + s + 1) = 0 mod k. But each factor is < k, so neither can be divisible by k. Hence both must be even. But that is impossible (because their sum is 2r+1 which is odd), so each of f(1), f(2), ... , f(k-1) must be distinct residues mod k. Obviously none can be 0 mod k (since 2k cannot divide r(r+1) for 0 < r < k and so k cannot divide f® ). Thus they must include all the residues 1, 2, ... k-1. So k a power of 2 does work.

Now suppose h divides k and k works. If f(n) = a mod k, then f(n) = a mod h, so h must also work. Since odd numbers do not work, that implies that k cannot have any odd factors. So if k works it must be a power of 2.