HMMT 二月 2019 · 团队赛 · 第 2 题

HMMT February 2019 — Team Round — Problem 2

[ 20 ] Let N = { 1 , 2 , 3 , . . . } be the set of all positive integers, and let f be a bijection from N to N . Must there exist some positive integer n such that ( f (1) , f (2) , . . . , f ( n )) is a permutation of (1 , 2 , . . . , n )?

解析

[ 20 ] Let N = { 1 , 2 , 3 , . . . } be the set of all positive integers, and let f be a bijection from N to N . Must there exist some positive integer n such that ( f (1) , f (2) , . . . , f ( n )) is a permutation of (1 , 2 , . . . , n )? Proposed by: Michael Tang Answer: No Consider the bijection f defined by ( f (1) , f (2) , f (3) , f (4) , . . . ) = (2 , 4 , 6 , 1 , 8 , 3 , 10 , 5 , 12 , . . . ) , which alternates between even and odd numbers after the second entry. (More formally, we define f ( n ) = 2 n for n = 1 , 2, f ( n ) = n + 3 for odd n ≥ 3 and f ( n ) = n − 3 for even n ≥ 4.) No such n can exist for this f as the largest number among f (1) , f (2) , . . . , f ( n ) is more than n for all n : for k ≥ 2, the maximum of the first 2 k − 1 or 2 k values is achieved by f (2 k − 1) = 2 k + 2. (Checking n = 1 and n = 2 is trivial.)