Introduction to Graph Theory · Problem 4.2

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · digraph-cycles-number-theory

Problem

Let

p

be a prime number. Let

(a_1, a_2, a_3, \ldots)

be a sequence of integers that is periodic with period

p

(that is, that satisfies

a_i = a_{i+p}

for each

i > 0

). Assume that

a_1 + a_2 + \cdots + a_p

is not divisible by

p

. Prove that there exists an

i \in \{1, 2, \ldots, p\}

such that none of the

p

numbers

a_i,\ a_i + a_{i+1},\ a_i + a_{i+1} + a_{i+2},\ \ldots,\ a_i + a_{i+1} + \cdots + a_{i+p-1}

(that is, of the

p

sums

a_i + a_{i+1} + \cdots + a_j

for

i \leq j < i + p

) is divisible by

p

. [Remark: This would be false if

p

was not prime. For instance, for

p = 4

, the sequence

(0, 2, 2, 2, 0, 2, 2, 2, \ldots)

would be a counterexample.] [Hint: Use Exercise 4.1 (a). What is the digraph, and why does it have a cycle?]