본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 대34. 두 이진수 붙이기
수학동아 2019.10.01

이진법에서는 숫자 0과 1만을 사용하여 수를 표현하고, 자리가 하나씩 올라감에 따라 자리의 값이 2배씩 커진다.

 

이진수 1011을 우리가 잘 알고 있는 십진수로 나타내면 1\times 2^3+0\times2^2+1\times2^1+1\times2^0=8+2+1=11이 된다. 이 이진수의 첫째(일의 자리), 둘째(2^1의 자리), 셋째(2^2의 자리), 넷째(2^3의 자리) 자리의 숫자는 각각 1, 1, 0, 1이다.

 

자연수 집합 \mathbb{N}=\left \{ 1, 2, 3,\cdots \right \}의 부분집합 S가 있을 때, 다음 조건을 만족하는 이진수를 S와 어울리는 이진수라고 하자.

 

"이진수의 i번째 자리와 j번째 자리 (단, i\geq j)가 둘 다 1이면, i=j이거나 i-j가 S의 원소다."

 

예를 들어, S=\left \{ 1 \right \}인 경우에는 S와 어울리는 이진수는 0, 1, 10, 100, \cdots과 더불어 11, 110, 1100, \cdots의 꼴 밖에 없음을 관찰할 수 있다. 한편 111은 S와 어울리는 이진수가 아니다. 첫째 자리와 셋째 자리의 차이가 2인데, 2는 S의 원소가 아니기 때문이다.

 

다른 예로, S가 모든 짝수의 집합인 경우를 생각해 보자. 0, 1, 10, 10101, 10100010 들은 모두 S와 어울리는 이진수임을 쉽게 알 수 있다. 11이나 101001은 S와 어울리지 않는 이진수다.

 

두 S와 어울리는 이진수 a와 b가 있다고 하자. a와 b 사이에 0과 1을 합쳐 n개 넣어서 S와 어울리는 이진수를 만들 수 있으면, 길이 n으로 a에서 b로 연결할 수 있다고 부르자. 위 예에서 S가 모든 짝수들의 집합이고, a=10, b=1이라 하면, 모든 짝수 길이로 a에서 b로 연결할 수 있고 (10001, 1000001, \cdots ), 모든 홀수 길이로 b에서 a로 연결할 수 있음을 확인할 수 있다. (1010, 100010, \cdots )

 

1. S가 유한집합이면, 홀수인 이진수는 유한개밖에 없음을 보여라.

 

2. 자연수 k에 대해 집합 S={k보다 크거나 같은 자연수}를 생각하자. 두 S와 어울리는 이진수 a와 b가 있을 때, 자연수 N이 존재해서 N보다 긴 모든 길이로 a에서 b로 연결할 수 있음을 보여라.

 

3. (문제 2의 역) 임의의 두 S에 어울리는 이진수 a와 b마다, 자연수 N이 존재해서 N보다 긴 모든 길이로 a에서 b로 연결할 수 있다고 하자. (N은 a와 b마다 다를 수 있다) 이때,  S={k보다 크거나 같은 자연수}의 형태가 되는 k가 항상 있음을 보여라.

 

4. 집합 S가 다음을 만족한다고 하자.

"임의의 자연수 n에 대해서, 어떤 자연수 m이 있어서 m, m+1, \cdots, m+n이 모두 S의 원소다."

이때, 임의의 네 이진수 a, b, c, d에 대해, 어떤 자연수 n이 있어서 길이 n으로 a에서 b로 연결할 수 있고, 또 길이 n으로 c에서 d로도 연결할 수 있음을 보여라.

 

5. 문제 4의 역은 성립할까?

 

6. S와 어울리는 임의의 두 이진수 ab마다 (어떤 n에 대해 길이 n으로) a에서 b로 연결할 수 있는 S의 필요충분조건을 찾아라.

 

※ 공지사항 ※

정답 확인 요청 시 비밀 댓글로 올리는 친구가 많네요!

다른 친구들이 풀이를 함께 보고 검토할 수 있도록 공개 댓글로 올려주세요!laugh

 

  •  
    퍼즐-Scratch Lv.4 2019.10.01 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      퍼즐-Scratch Lv.4 2019.10.01 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      리프 Lv.5 2019.10.02

      몇 번 문제의 풀이인가요?

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2019.10.02

      1번 풀이입니다.

      좋아요0
  •  
    리프 Lv.5 2019.10.02 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      리프 Lv.5 2019.10.02

      1, 2, 3번의 풀이입니다.

      좋아요0
    •  
      리프 Lv.5 2019.10.02

      아 지금 보니 3번 문제를 잘못 이해해서 잘못 풀었네요 곧 수정한 풀이 올리겠습니다.

      좋아요0
    •  
      리프 Lv.5 2019.10.03

      2번 풀이 2번째 줄에서 'a와 b를 k개 이상의'를 'a와 b를 (k-1)개 이상의' 로 수정하고

      마지막 줄 k를 k-1로 수정합니다.

      좋아요0
  •  
    수돌이 Lv.2 2019.10.02 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      수돌이 Lv.2 2019.10.02

      45풀이입니다

      좋아요0
  •  
    리프 Lv.5 2019.10.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      리프 Lv.5 2019.10.03

      수정된 3번 풀이입니다.

      좋아요0
  •  
    리프 Lv.5 2019.10.04

    6번 풀이는 아니지만 풀이에 도움이 될 수도 있어서 한 번 올려봅니다.

     

    일단 조건으로부터 다음과 같은 사실들을 알 수 있습니다.

     

    1. S는 무한집합이다.

     

    증명) S가 무한집합이 아니라고 가정하자. (귀류법)

    그러면 S의 원소 중 제일 큰 원소 X가 존재할 것이다.

    이때, S와 어울리는 두 이진수를 다음과 같이 잡자.

    a=1000...0_{(2)}b=1_{(2)} (단, a에 있는 0은 총 X개)

    이때, 문제 조건에 의해 a와 b를 길이 n으로 연결할 수 있음을 알 수 있다.

    연결된 이진수를 보면 1의 자릿수의 차 중 가장 큰 값이 X+n+1인데 이는 S의 원소가 되어야 하므로 X가 가장 큰 원소라는 가정에 모순이다.

    따라서, S는 무한집합이다.

     

    2. S와 어울리는 임의의 두 이진수 a, b에 대하여 a와 b를 길이 n으로 연결할 수 있을 때, n이 될 수 있는 자연수는 무한히 많다.

     

    증명) 1번과 비슷한 방식으로 증명할 수 있습니다.

    S와 어울리는 어떤 두 이진수 a, b가 존재하여 a와 b를 길이 n으로 연결할 수 있는 자연수 n의 값이 유한하다고 가정하자. (귀류법)

    자연수 n중 가장 큰 값 N에 대하여 a와 b를 길이 N으로 연결한 이진수를 c라고 하자.

    이때, c와 b는 S와 어울리는 이진수이므로 문제 조건에 의하여 어떤 m이 존재하여 길이 m으로 연결할 수 있다는 것을 알 수 있다.

    c와 b를 길이 m으로 연결한 이진수를 보면 이는 a와 b를 어떤 자연수 N'으로 연결한 형태와 동일하다는 것을 알 수 있다.

    따라서, a와 b를 길이 N'으로 연결했는데 N'>N이므로 모순이다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    리프 Lv.5 2019.10.05

    이 문제 검토는 언제쯤 되나요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    손고슴 Lv.4 2019.10.05 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      가u스 Lv.5 2019.10.05

      몇번 풀이인가요?

      좋아요0
  •  
    RedHood Lv.2 2019.10.09

    ㅑㅎㅇ햐

    댓글 작성하기 좋아요0 댓글수1
  •  
    리프 Lv.5 2019.10.10
    확인요청중

    정답확인요청 중에는 공개댓글 전환이 불가능해서 다시 올립니다.

     

    1, 2, 3번 문제의 풀이입니다.

     

    1번 문제

    풀이) 주어진 집합 S=\left \{ a_1,a_2,...,a_n \right \}에 대하여 (단, a_i는 자연수, i는 1\leq i\leq n인 정수)

    S에 어울리는 이진수 중 홀수는 반드시 1번째 자리가 1임을 알 수 있다.

    따라서, 1이 올 수 있는 자리는 (a_i+1)째 자리 밖에 없고 S에 어울리는 홀수인 이진수는 2^{a_n}개이므로 유한하다.

     

    2번 문제

    풀이) 자연수 N의 존재성만 보이면 충분하다.

    a와 b를 k개 이상의 0을 넣어 연결하면 이 이진수는 S에 어울리는 이진수가 됨을 알 수 있다. (임의의 두 1에 대해 자릿수의 차가 k 이상이기 때문에)

    따라서, N=k일때 조건을 만족하므로 이러한 자연수 N이 반드시 존재함을 알 수 있다.

     

    3번 문제

    풀이) S에 어울리는 두 이진수 1과 1에 대해 1과 1을 N이상의 모든 길이로 연결이 가능하다고 하자.

     

    1과 1을 연결했을때, 어떤 자연수 k\leq N이 존재하여 자릿수의 차가 k인 두 1이 존재할 경우, 1과 1을 (k-1)개의 0으로 연결할 수 있기 때문에 모순이다.

    따라서, S의 원소 중 N미만의 원소는 존재하지 않는다.

    한편, N이상의 임의의 정수 n에 대해 n의 길이로 연결이 가능하므로, n+1은 S의 원소가 된다. 따라서, S는 N+1이상의 모든 자연수의 집합이 되므로 k=N+1임을 알 수 있다.

     

    댓글 작성하기 좋아요0 댓글수4
    •  
      퍼즐-Scratch Lv.4 2019.10.10

      제가 잘못 이해한 것일 수도 있는데, 3번 문제 풀이에서 1과 1 뿐만 아니라 S와 어울리는 모든 이진수 a와 b에 대해 살펴봐야 하는 것 아닌가요?

      좋아요0
    •  
      리프 Lv.5 2019.10.11

      저는 N이하의 자연수가 S의 원소가 될 수 없음을 1과 1에 대해서 귀류법을 사용하여 모순을 유도하려고 했는데 다시 보니 오류가 있는 것 같네요. 수정 후 풀이 다시 올리겠습니다.

      좋아요0
    •  
      리프 Lv.5 2019.10.11

      그런데 3번에서 예를 들어 S={5이상의 자연수}U{2} 여도 임의의 S에 어울리는 두 이진수에 대해서 4 이상의 길이로 연결이 가능한데 그러면 반례가 되지 않나요?

      아니면 이때는 k=2로 생각하라는 뜻인 거인지 잘 모르겠네요

      만약 전자가 맞다면 반례가 존재하고, 후자가 맞다면 자연수의 부분집합에서 최소원소를 잡을 수 있음은 자명한데 문제가 약간 이상한 부분이 있는 것 같네요

       

      만약 제가 문제 이해를 잘못했다면 댓글로 알려주시기 바랍니다

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2019.10.11

      그러게요. 3번 문제에서  'S={k보다 크거나 같은 자연수}의 형태가 되는 k가 존재'가 아니라 'S\supset \{ n\in \mathbb{N}\, |\, n\geq k \}를 만족하는 자연수 k가 존재'가 되야 하는 것 아닌가요? 제가 잘못 이해한 것이라면 알려주세요.

      좋아요0
  •  
    퍼즐-Scratch Lv.4 2019.10.10

    위에 올렸던 1번 풀이입니다. 

     

    1. S가 유한집합이라면 최댓값 M이 존재합니다. 이진수가 홀수려면 그 일의 자리가 1이여야 하고, 그 이진수가 n자리 수일 때 n-1이 S의 원소여야 합니다. (i=n, j=1) 즉 n-1≤M이고, n≤M+1입니다. 따라서 S와 어울리는 홀수인 이진수는 2^{M+1}보다 작아야 하므로 개수는 유한합니다. 

     

    풀이 비댓 바로 밑 비댓이 오류를 수정한 비댓이었는데, 그것까지 적용해서 올립니다. 

    댓글 작성하기 좋아요0 댓글수0
  •  
    김우현 기자 Lv.4 2019.10.12

    지금까지 달린 모든 풀이는 주정훈 멘토가 검토 중입니다.

    코멘트가 오는대로 알려줄게요!

    댓글 작성하기 좋아요0 댓글수0