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

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

 

이진수 1011을 우리가 잘 알고 있는 십진수로 나타내면 1   imes 2^3+0   imes2^2+1   imes2^1+1   imes2^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마다 다를 수 있다) 이때, ⊃ {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의 필요충분조건을 찾아라.

 

※ 알립니다 ※

 

소문제 3번 내용 중 일부를 다음과 같이 수정합니다.

= { k 보다 크거나 같은 자연수}    →    ⊃ { k 보다 크거나 같은 자연수}

 

☆ 알립니다2 ☆

 

1번 문제는 퍼즐-scratch 친구가, 2, 3, 5번은 리프 친구, 4번은 수돌이 친구가 해결했습니다.

6번 문제 해결에 도전해서 최종 해결로 만들어 주세요~!^^

 

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

      몇 번 문제의 풀이인가요?

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

      1번 풀이입니다.

      좋아요0
    •  
      김우현 기자 Lv.4 2019.11.10

      퍼즐-Scratch 친구, 소문제 1번 최종 정답입니다. :)

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

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

      좋아요0
    •  
      리프 Lv.6 2019.10.02

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

      좋아요0
    •  
      리프 Lv.6 2019.10.03

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

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

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

      45풀이입니다

      좋아요0
    •  
      김우현 기자 Lv.4 2019.10.25

      주정훈 멘토 확인 결과,

       

      ① 4번 문제 정답입니다! 교수님께 최종 검토 요청드릴게요!

      ② 5번 문제는 ab사이에 끼워넣는 숫자의 개수와 cd사이에 끼워넣는 숫자의 개수가 같아야한다는 조건에 맞는지 다시 한 번 검토 부탁해요!

      좋아요0
    •  
      김우현 기자 Lv.4 2019.11.10

      수돌이 친구, 4번 문제 최종 정답입니다! :)

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

      수정된 3번 풀이입니다.

      좋아요0
  •  
    리프 Lv.6 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.6 2019.10.05

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    손성민 Lv.4 2019.10.05 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
  •  
    RedHood Lv.2 2019.10.09

    ㅑㅎㅇ햐

    댓글 작성하기 좋아요0 댓글수1
  •  
    리프 Lv.6 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 댓글수6
    •  
      퍼즐-Scratch Lv.4 2019.10.10

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

      좋아요0
    •  
      리프 Lv.6 2019.10.11

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

      좋아요0
    •  
      리프 Lv.6 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가 존재'가 되야 하는 것 아닌가요? 제가 잘못 이해한 것이라면 알려주세요.

      좋아요1
    •  
      김우현 기자 Lv.4 2019.10.25

      주정훈 멘토 확인 결과,

       

      ① 1, 2번 문제는 잘 풀었습니다. 교수님께 최종 확인 요청드릴게요!

      ② 3번 문제는 리프 친구가 지적한 부분에 오류가 있는지 파악한 뒤 다시 알려드리겠습니다. 

      좋아요0
    •  
      김우현 기자 Lv.4 2019.11.10

      소문제 1, 2번 문제 최종 정답입니다.

      소문제 1번은 퍼즐-Scratch 친구가 먼저 풀었으니, 2번에 관해서만 최종 정답자로 인정할게요!

       

      소문제 3번은 지적해주신대로 오류가 있었네요. 문제 본문에 수정 사항을 적용했으니 참고 부탁드려요. 오류가 발생해 정말 죄송합니다!

      좋아요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
  •  
    부분해결
    리프 Lv.6 2019.12.10

    이 문제 묻힌 것 같지만 그냥 올립니다.

    3번은 1과 1을 어떤 자연수 N이상의 길이로 연결할 수 있기 때문에 N+1이상의 모든 자연수가 S의 원소가 되서 성립하게 됩니다.

    더 자세한 설명이 필요하다면 답글 달아주세요.

    댓글 작성하기 좋아요0 댓글수4
    •  
      최기자 Lv.4 2020.02.05

      주정훈 멘토가 검토한 결과 3번 문제를 잘 풀었다고 합니다. 나머지 문제에도 도전해 보세요!^^

      좋아요0
    •  
      리프 Lv.6 2020.02.10

      5번은 해결이 된건가요? 공지에는 수돌이님이 해결했다고 적혀있는데 댓글보면 아닌거 같아서...

      좋아요0
    •  
      수학동아 2020.02.19

      미안합니다! 5번 문제는 수돌이 학생이 푼 것에서 확인이 필요한 부분이 있네요. 담당자가 바뀌면서 착오가 있었습니다.

       

      5번 문제만 해결하면 최종 해결이 될 것 같아요~!

      좋아요0
    •  
      리프 Lv.6 2020.02.23

      6번 제가 풀었다고 적혀있는데 제가 올린거는 S의 필요조건만 몇 가지 적은 거라서 사실 푼 게 아닙니다. 수정해주셨으면 좋겠네요 (정리하면 5,6번 미해결인 것 같습니다.)

      좋아요0
  •  
    해결
    리프 Lv.6 2020.02.28

    5번 풀이입니다.

     

    다음 조건을 만족하는 자연수 k_1의 존재성을 먼저 보이자.

    조건: k_1, k_1+1이 모두 S의 원소이다.

    증명: 1에서 1, 10에서 1을 동일한 길이로 연결하자. 그러면 k_1, k_1+1이 모두 S의 원소가 되는 k_1이 존재함을 알 수 있다.

     

    이제, 귀납적으로 다음과 같은 값들을 정의하자.

    p_1=100...01 (0이 k_1개), q_1=100...01 (0이 k_1+1개)

     

    k_n(p_{n-1}, p_{n-1}),(q_{n-1}0,q_{n-1})을 동시에 연결할 수 있는 길이

    p_np_{n-1}에서 p_{n-1}로 k_n개의 0으로 연결한 수

    q_nq_{n-1}0에서 q_{n-1}로 k_n개의 0으로 연결한 수

     

    이때, p_n의 i번째 1과 i+1번째 1 사이에 있는 0의 개수를 차례대로 나열한 순서쌍을 생각해보면

    \left ( k_1,k_2,k_1,k_3,k_1,k_2,k_1,... ,k_1\right )이 된다는 것을 알 수 있다.

    정확히는 v_2(i)=r일 때, i번째 원소는 k_{r+1}이 됨을 수학적 귀납법으로 쉽게 보일 수 있다. (증명 생략)

     

    또한, 동일한 형태의 순서쌍을 q_n에 대해 생각해보면 p_n의 각 원소에 1씩 더한 순서쌍이 된다는 것을 알 수 있다.

    (증명: 수학적 귀납법으로 생각해보면 q_{n-1}0과 q_{n-1}을 k_n개의 0으로 연결했을 때 q_{n-1}부분은 귀납가설에 의해 조건을 만족하고 q_{n-1}과 q_{n-1} 사이에는 k_n+1개의 0이 있으므로 수학적귀납법이 성립한다.)

     

    이제, p_n과 q_n을 m개의 0으로 연결한 이진수를 생각하자. 이때, p_n의 1번째 1과 q_n의 1번째 1의 자릿수 차이를 t라고 정의하자.

    p_n의 2번째 1과 q_n의 2번째 1의 자릿수 차이를 생각해보면 p_n의 2번째 1은 1번째 1보다 자릿수가 k_1+1만큼 감소했는데 q_n은 k_1+2만큼 감소했으므로 자릿수 차이가 t+1이 된다는 것을 알 수 있다. (q_n의 순서쌍의 임의의 원소가 p_n보다 1씩 크기 때문에 일어나는 현상이다.)

    동일한 이유로, p_n의 i번째 1과 q_n의 i번째 1의 자릿수 차이는 t+i-1이 됨을 알 수 있다.

    따라서, t,t+1,t+2,...,t+2^n이 모두 S의 원소이므로, 임의의 자연수 n에 대해 어떤 자연수 m이 있어서 m, m+1, ... , m+n이 모두 S의 원소가 된다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      수학동아 2020.03.20

      김다인 멘토의 검토 결과 정답인 것 같다고 합니다! 수고 많았어요~! 다만 사소한 오타가 있다고 하네요.

      "시작할 때 k_1+1, k_1+2 \in S라 잡아야 될 것 같네요! 그래야 0의 개수가 k_1, k_1+1개가 됩니다~"라고 합니다.
       

      좋아요0
    •  
      리프 Lv.6 2020.03.20

      ㅇㅎ 오타가 있었네요 ㅋㅋ 알려주셔서 감사합니다

      좋아요0
  •  
    리프 Lv.6 2020.03.02
    확인요청중

    4번 풀이가 비댓이라서 풀이 올려봅니다.

     

    a,b,c,d의 자릿수를 각각 x,y,z,w라 하고 일반성을 잃지 않고 x+y가 z+w보다 크거나 같다고 하자.

    a와 b, c와 d를 각각 길이 n으로 연결할 수 있으려면 n+1이상, x+y+n-1이하에 있는 특정 수들이 S의 원소가 되어야 한다. (a에 속한 1과 b에 속한 1의 자릿수 차이를 분석해보면 쉽게 알 수 있습니다.)

    이때 조건에 의해 임의의 자연수 n에 대해 S의 원소 중 n+1개의 연속한 수가 존재한다고 했으므로, 어떤 x+y-1개의 연속한 수가 S의 원소로 존재할 것이다.

    이러한 x+y-1개의 연속한 수 중 최솟값이 n+1이 되도록 n을 잡으면 a에서 b, c에서 d로 길이 n으로 연결할 수 있음을 확인할 수 있다.

     

    일단 풀이의 핵심적인 부분들만 요약해서 적었고 설명이 더 필요하다면 답글 달아주세요

    댓글 작성하기 좋아요1 댓글수3
    •  
      수학동아 2020.03.20

      김다인 멘토가 검토한 결과 다음과 같은 의견을 줬습니다.^^

       

      " x+y >= z+w라는 조건이 어디에서 쓰였는지 궁금합니다. 그리고 길이 n으로 a에서 b, c에서 d로 어떻게 연결한건지 잘 보이지가 않네요!"
       

      좋아요0
    •  
      리프 Lv.6 2020.03.20

      a와 b, c와 d를 길이 n으로 연결하기 위해서는 a와 b에 대해서 봤을 때 n+1이상, x+y+n-1이하의 모든 수가 S의 원소가 되면 충분하다는 것을 알 수 있습니다. (왜냐하면 a와 b에서 생기는 자릿수 차이의 최댓값은 x+y+n-1이고, c와 d에서 생기는 자릿수 차이의 최댓값은 z+w+n-1인데 x+y>=z+w이기 때문입니다.)

      따라서, x+y-1개의 연속한 수가 S의 원소로 존재함을 보이면 충분한데 이는 문제의 조건에 의해 성립하므로 a와 b, c와 d를 적당한 길이 n이 존재하여 n개의 0으로 연결할 수 있습니다.

       

      그리고 문제 6번 아직 미해결인데 해결이 붙었네요... 수정해주셨으면 합니다.

      좋아요0
    •  
      리프 Lv.6 2020.05.22

      혹시 4번 풀이 정답 여부를 알 수 있을까요?

      좋아요0
  •  
    파스칼 Lv.3 2020.03.27

    6번이 남았다고 해서 한번 도전해보았습니다.

    이진수 a의 x째 자리를 a(x)라 하고, 모든 0이 아닌 이진수 a에 순서쌍 (n,A)를 부여하겠습니다. 이때 n은 음이 아닌 정수이고 A는 집합인데, n은 k<n인 모든 양의 정수 k에 대해 a(k)=0이고 a(n)=1을 만족하는 정수입니다. 최소원의 성질에 의해 0이 아닌 a에서 이런 n이 반드시 존재합니다. 또한 A는 a의 모든 a(i)=a(j)=1을 만족하는 i,j에 대해 |i-j|의 집합입니다. 이때 a가 S와 어울리는 이진수일 필요충분조건이 A⊆S임을 알 수 있습니다. 

    a와 b가 각각 (p, A), (q, B)를 순서쌍으로 가질 때, a와 b를 길이 n으로 연결한 이진수가 c면 c의 순서쌍을 (r, C)라 할 때 A⊆C, B⊆C, (n+p)∈C, x∈A에 대해 (x+p+1)∈C, x∈A이고 y∈B인 모든 x, y에 대해 (x+y+2+n)∈C입니다. 또 위의 언급된 모든 원소 외에는 C의 원소가 없습니다. 이때 (p, {0})을 순서쌍으로 갖는 모든 이진수는 S와 어울리는 이진수입니다. 즉 이 수를 a로 놓고 생각하면, 문제의 조건을 만족하는 모든 S에 대해 n보다 크거나 같은 모든 정수는 S의 원소입니다. 반대로, S가 n보다 크거나 같은 모든 정수를 포함한다면, S와 어울리는 두 이진수 a, b에 대해 A, B의 모든 원소가 S의 원소입니다. 즉 a,b를 길이 n으로 연결한 이진수 c에 대해서도 C의 원소 중 n보다 작은 원소가 될 수 있는 원소는 A 또는 B의 원소로 S의 원소임에서, C는 S의 부분집합입니다. 따라서 S의 필요충분조건은 {i | n≦i, i∈Z}⊆S 입니다.

    댓글 작성하기 좋아요0 댓글수3
    •  
      구머 Lv.4 2020.03.27

      안타깝게도 반례가 존재합니다! "S:모든 짝수의 집합"일 때 반례가 됨을 쉽게 확인할수 있습니다.

       

      좋아요0
    •  
      리프 Lv.6 2020.03.27

      마지막 부분에서 1000...0과 어떤 이진수를 연결할 때 길이 n으로 연결할 수 있으므로 n이상의 모든 자연수가 S의 원소가 된다고 하신 것 같은데 n은 고정된 값이 아니라 a와 b의 값에 따라 달라질 수 있는 값입니다. 그래서 오류가 생긴 것 같군요. 아마도 파스칼님의 풀이는 2,3번의 내용과 비슷한 것 같습니다.

      좋아요0
    •  
      파스칼 Lv.3 2020.03.27

      n을 고정된 값으로 잘못 이해했네요. 감사합니다.

      좋아요0
  •  
    다시 도전
    파스칼 Lv.3 2020.03.28

    다시 풀었습니다.

    이진수 a의 x째 자리를 a(x)라 하고, 모든 0이 아닌 이진수 a에 순서쌍 (n,A)를 부여하겠습니다. 이때 n은 음이 아닌 정수이고 A는 집합인데, n은 k<n인 모든 양의 정수 k에 대해 a(k)=0이고 a(n)=1을 만족하는 정수입니다. 최소원의 성질에 의해 0이 아닌 a에서 이런 n이 반드시 존재합니다. 또한 A는 a의 모든 a(i)=a(j)=1을 만족하는 i,j에 대해 |i-j|의 집합입니다. 이때 a가 S와 어울리는 이진수일 필요충분조건이 A⊆S임을 알 수 있습니다. 

    m개의 음이 아닌 정수를 원소로 갖는 집합 M이, M의 몇 개의 원소 a_{1}, a_2, a_3,... a_k에 대해 a_{1}, a_2, a_3,... a_k 중 하나 이상의 원소를 모두 더한 값으로만 이루어진 집합이라면 M을 k-완전집합이라고 부르겠습니다. 예를 들어, {1,2,3,4,5,6}은 1, 2, 3중 하나 이상의 원소를 모두 더한 값인 1, 2, 3, 3(=1+2), 4(=1+3), 5(=2+3), 6(=1+2+3)을 모두 포함하고, 이들 외에 원소가 없으므로 3-완전집합입니다.

    S의 부분집합 중 m-완전집합 M이 있다면, 모든 p에 대해 (p, M)을 순서쌍으로 갖는 이진수 a가 존재하고, a는 S와 어울리는 이진수입니다. 즉 k-완전집합 M{a_{1}, a_2, a_3,... a_m}⊆S이고 l-완전집합 N{b_1, b_2, ..., b_n}⊆S인 모든 집합 N, M에 대해 모든 양의 정수 p,q에 대해 (p,M)과 (q,N)을 연결할 수 있어야 하므로, 모든 두 양의 정수 i≦k와 j≦l에 대해 a_i+b_{j}+n+1∈S를 만족하는 양의 정수 n이 무한히 많아야 합니다. 

    또한 이런 모든 집합 S는 조건을 만족함을 보이겠습니다. 두 이진수 a(p,M), b(q,N)을 연결할 때, M, N집합의 정의에 의해 M과 N은 모두 완전집합입니다. 이때 a_i+b_{j}+n+1∈S라면 a와 b를 길이 n-p로 연결 (n-p개의 수를 모두 0으로 해서 연결)한 이진수에 대해 a의 한 자리인 1과 b의 한 자리인 1 사이의 거리는 모두 S 집합의 원소이고, a나 b 둘 중 하나에서만 두 개의 1을 골랐을 때 둘 사이의 거리는 원래 S의 원소였으므로 이 이진수도 S에 어울리는 이진수가 됩니다. 그런데 이런 n이 무한히 많으므로 n-p가 양수인 n이 반드시 존재합니다.

    따라서 S와 어울리는 임의의 두 이진수 a,b마다 a에서 b로 연결할 수 있도록 하는 S의 필요충분조건은 모든 S의 부분집합인 k-완전집합 M{a_{1}, a_2, a_3,... a_m}, l-완전집합 N{b_1, b_2, ..., b_n}과 모든 두 양의 정수 i≦k와 j≦l에 대해, a_i+b_{j}+n+1∈S를 만족하는 양의 정수 n이 무한히 많은 것입니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      리프 Lv.6 2020.03.28

      S와 어울리는 이진수 a에 대한 순서쌍 (n,A)에서 집합 A를 편의상 a의 자릿수 집합이라 부르겠습니다.

      파스칼님의 풀이를 보면 자릿수 집합이 항상 완전집합이라고 생각하시고 푸신 것 같은데 자릿수 집합은 어떤 원소들의 합들로 구성되기는 하지만 완전집합이라고 보장할 수는 없습니다.

      예를 들어, 1101001과 같은 이진수를 보면, 가장 가까운 1들의 자릿수 차이는 각각 1,2,3이고, 자릿수 집합의 원소들은 이들의 합으로 표현되지만 1+3이 존재하지 않으므로 완전집합은 아닙니다.

      혹시 제가 파스칼님의 풀이를 잘못 이해하고 있는 것이라면 알려주시기 바랍니다.

      좋아요0
    •  
      파스칼 Lv.3 2020.03.28

      잘못 생각했네요. 완전집합의 정의를 다음과 같이 수정하겠습니다.

      '(0,M)을 순서쌍으로 갖는 이진수가 존재할 때, 이 이진수의 i번째 자리와 j번째 자리가 둘 다 1이며 i≦j이고 i<x<j인 모든 정수 x에 대해 x번째 자리가 0인 i,j를 생각하자. 이때 j-i의 집합이 {a_1, a_2, ...,a_k}라면, M을 k-완전집합이라고 정의한다.'

      좋아요0
    •  
      리프 Lv.6 2020.03.28

      풀이에 별다른 오류는 없는 것 같은데 제가 보기에는 'a와 b를 연결할 수 있다' 라는 명제를 약간만 변형해서 적은 것 같아서 이게 정답으로 인정될지는 잘 모르겠네요... 저는 문제의 의도를 'S가 조건을 만족하는 집합인지 판별하는 간단한 방법을 찾아라' 이렇게 이해하고 있어서요...

      출제자가 무엇을 의도하고 낸 문제인지 잘 모르겠네요

      좋아요0
    •  
      최기자 Lv.4 2020.04.16

      검토가 늦어져서 미안해요!

       

      김다인 멘토 역시 리프 군의 의견에 동의한다고 하네요. 조근 더 간단한 필요충분조건을 찾아 주면 좋겠어요!

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911