2-distance increasing map

어제 저녁에 고등과학원 동료들과 얘기하다가, 중학생도 이해할 수 있는 미해결 문제를 하나씩 내놓았다. 다음은 나와 같은 연구실을 쓰는 이** 박사의 문제.

먼저, Hamming distance를 정의하자. n개의 성분으로 이루어진 두 개의 tuple (a_1, a_2, ..., a_n)와 (b_1, b_2, ..., b_n)에 대하여, a_i≠b_i인 성분의 개수를 두 tuple 사이의 Hamming distance로 정의한다. 이후로 간단히 "거리"라고 부르자. 예를 들어, (1,0,0,0)과 (1,1,0,1)은 두 번째, 네 번째 성분이 다르므로 거리, 즉 Hamming distance는 2가 된다.

이제 0과 1로만 이루어지고 길이가 n인 tuple들의 집합을 X라 하고, 1, 2, ..., n을 하나씩 써서 만든 tuple들의 집합을 Y라 하자.

그러면 X의 원소의 개수는, n개의 자리에 0과 1을 넣는 방법이 각각 두 가지이므로, 2^n 개가 된다. 한편 Y의 원소의 개수는, 1부터 n까지를 나열하는 방법의 수와 같으므로, n! 개가 된다.

어떤 함수 f:X-->Y에 대하여, X의 임의의 두 원소 a, b 사이의 거리보다 f(a), f(b) 사이의 거리가 크거나 같을 때, 이 함수를 distance preserving이라 한다. n이 4보다 크거나 같을 때 이런 함수가 존재하다는 것이 알려져 있다.

만약 f(a)와 f(b) 사이의 거리가 a와 b 사이의 거리보다 적어도 1이 더 크면, 이때는 1-distance increasing이라 한다. 물론 두 원소 사이의 거리가 n보다 더 커질 수는 없으므로, a와 b 사이의 거리가 n일 때는 f(a)와 f(b) 사이의 거리도 n이 되는 것으로 생각한다. n이 4보다 크거나 같을 때, 이런 함수가 존재할 뿐만 아니라, 이런 함수를 구성하는 알고리듬까지 알려져 있다.

자, 이제 질문.

f(a)와 f(b) 사이의 거리가 a와 b 사이의 거리보다 적어도 2가 더 크게 하는 함수 f는 존재할까? 그리고 그런 함수는 어떻게 만들 수 있을까?
물론 a와 b 사이의 거리가 n-1, n일 때는 f(a)와 f(b) 사이의 거리도 n이 되는 것으로 생각한다.