달력

2

« 2020/2 »

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
2007. 10. 25. 11:27

2-distance increasing map Math2007. 10. 25. 11:27

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

먼저, 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이 되는 것으로 생각한다.



 

'Math' 카테고리의 다른 글

천부경(天符經)  (5) 2007.10.31
답은 100  (5) 2007.10.31
2-distance increasing map  (10) 2007.10.25
막장으로 치닫는 ㅇㅈㅇ  (15) 2007.10.23
걱정되는 스펀지  (31) 2007.10.08
격자 곱셈의 원리  (1) 2007.10.03
Posted by puzzlist

댓글을 달아 주세요

  1. 하얀까마귀 2007.10.25 19:32  댓글주소  수정/삭제  댓글쓰기

    중학생도 이해할 수 있으려면 일단 용어부터 중학생 수준으로 하셔야.. ^^

  2. skcho 2007.10.25 20:28  댓글주소  수정/삭제  댓글쓰기

    중학생도 이해할 수 있겠는데요?
    pomp님께서 용어의 뜻을 잘 풀어서 써주셨으니까요.

  3. thisknow 2007.10.26 19:33  댓글주소  수정/삭제  댓글쓰기

    permutation group을 잘 이용해야 될 듯 합니다만,
    잘 안되는군요.
    1-distance increasing 은 2-clcye을 이용하면,
    만들수 있을것 같고,
    2-distance increasing 은 n=4 일때는 불가능하다는
    것밖에 못보이겠네요.

    X 의 원소 (0,0,0,0)과 거리가 2 이상인것은 11개,
    Y 의 원소 (a,b,c,d)와 거리가 4 인것은 9개이므로,
    (0,0,0,0)이 (a,b,c,d)와 대응되었다고 하면,
    (0,0,0,0)과 거리가 2 이상인 것들은 모두
    (a,b,c,d)와 거리가 4 인것에 대응되어야 하는데,
    갯수 부족.

  4. 동생 2007.10.29 14:26  댓글주소  수정/삭제  댓글쓰기

    바둑 고쳤다

  5. Favicon of http://www.cyworld.com/? BlogIcon genius 2007.10.30 00:51  댓글주소  수정/삭제  댓글쓰기

    처음 와봤는데.. 굉장히 난잡하군요..

    이거 풀면.. 뭐 주나요??

    잘못하다가.. 수학계에 염증을 느끼는

    부류로 전락해버릴까봐서.. 살짝 걱정되네요..

    후훗..

  6. 동생 2007.10.30 21:16  댓글주소  수정/삭제  댓글쓰기

    바둑 또 고쳤다

  7. 지나가던..^^ 2007.11.01 20:24  댓글주소  수정/삭제  댓글쓰기

    mapping 자체를 만들어 내라는건가요?? 존재하지 않는다면 증명하거나??? ^^ 이런문제 풀려면 뭘 공부해야하나요?? 추상대수??이산수학??