Permutations of the positive integers with restrictions on the sequence of differences. II

Peter John Slater and William Yslas Vélez

Vol. 82 (1979), No. 2, 527–531

DOI: 10.2140/pjm.1979.82.527

Abstract

In this paper we discuss the following conjecture:

Conjecture: Let D = {D₁,⋯,D_n}, D ⊂ N, N the set of positive integers. Then there exists a permutation of N, call it (a_k : k ∈ N) such that {|a_k+1 −a_k| : k ∈ N} = D iff (D₁,⋯,D_n) = 1.

We also consider the following question:

Question: For what sets D = {D₁,⋯,D_n} does there exist an integer M ∈ N and a permutation {b_k : k = 1,⋯,M} of {1,⋯,M} such that {|b_k+1 − b_k| : k = 1,⋯,M − 1} = D.

We answer the conjecture and the following question in the affirmative if the set D has the following property: For each D_r ∈ D there is a D_s ∈ D such that (D_r,D_s) = 1.

Mathematical Subject Classification 2000

Primary: 05A05

Milestones

Received: 20 January 1978

Revised: 6 November 1978

Published: 1 June 1979