A Jump of Size mm

Problem

Let A ⁣:a1,a2,…,a2mA \colon a_1, a_2, \ldots, a_{2m} be a permutation of 1,2,…,2m1, 2, \ldots, 2m, where m∈N∗m \in \mathbb{N}^* and m⩾3m \geqslant 3. Say AA has property PP if there is at least one i∈{1,2,…,2m−1}i \in \{1, 2, \ldots, 2m-1\} with ∣ai−ai+1∣=m|a_i - a_{i+1}| = m.

1. For m=3m = 3, decide whether the sequences B ⁣:1,5,3,4,6,2B \colon 1, 5, 3, 4, 6, 2 and C ⁣:6,5,2,4,1,3C \colon 6, 5, 2, 4, 1, 3 have property PP. 2. Suppose the subsequences {a2n−1}\{a_{2n-1}\} and {a2n}\{a_{2n}\} (n=1,2,…,mn = 1, 2, \ldots, m) are both arithmetic, with a1=1a_1 = 1 and a2m=2a_{2m} = 2. Prove that for every even mm, the sequence AA does not have property PP. 3. Among all permutations of 1,2,…,2m1, 2, \ldots, 2m, let SS be the number of sequences with property PP and TT the number without it. Prove that S>TS > T for every m⩾3m \geqslant 3.

Answer

Solution

Difficulty9/10
Topicscombinatorics, Arithmetic Progression, Counting, sequences, Casework

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments
Log in to join the discussion.

No comments yet.