주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국13. 선분 색칠하기

2018.01.02

같이 풀어볼까?

네이버밴드 구글플러스

 

국가수리과학연구소의 13번째 문제입니다. 

 

어떤 자연수 \large n \large k에 대해 \large 1부터 \large n까지의 자연수와 \large 1부터 \large k까지 번호가 적힌 색이 있다고 하자. \large 1\large n사이에 있는 임의의 서로 다른 두 자연수 \large i\large j (\large i< j)에 대해 \large i\large j를 선으로 연결한 뒤, 모든 선을 \large 1부터 \large k까지의 색 중 하나로 칠하자.

자연수 \large m(\large m\geq 2)\large k가 고정돼 있을 때, 다음 조건을 만족하는 가장 큰 자연수 \large n은 무엇일까?

 

 

[조건]

\large 1부터 \large n까지의 자연수 중 \large m개의 서로 다른 자연수 \large a_{1}, a_{2}, \cdots, a_{m}을 작은 수부터 큰 수까지 순서대로 선택해도, 각 자연수를 잇는 선분 \large a_{1}a_{2}, a_{2}a_{3}, \cdots, a_{m-1}}a_{m}의 색 번호가 순서대로 증가하거나 같은 값을 가질 수 없다. 

 예) 1, 2, 2, 3, 3, 5, 5 (X) / 1, 2, 2, 2, 1, 2, 2, 3 (O)

 

 

댓글 39

  • 여백 패르마 2018.01.02 16:57:26

    두 선을 선분으로 잇는다고요???

    좋아요0 댓글수1
    • 수학장 2018.01.02 22:00:05

      1부터 n까지의 모든 자연수를 연결하고 그 선분을 색칠합니다. 그 다음 조건을 만족하는 n의 최댓값을 구하는 겁니다. (m,k는 고정됨)

      좋아요0
  • 수학장 2018.01.02 18:09:22

    질문 있는데요 m이 1일 때는 선분이 아예 없고 m이 2일 때는 색이 1개인데 이럴 때는 각각 어떻게 해야 하는 거죠?

    좋아요0 댓글수3
    • 구머 2018.01.02 18:11:37

      1일 때는 잘 모르겠고 2일때는 선분의 색의 개수 k가 답이 될것 같습니다

      좋아요0
    • 수학장 2018.01.02 20:15:56

      m이 2일 때는 조건을 만족하지 않지 않나요?

      좋아요0
    • 김우현 기자 2018.01.03 09:31:36

      m\geq 2라는 조건을 추가했습니다!  m= 1일 때는 선분이 만들어지지 않지요. 조건을 빠뜨려서 죄송합니다!

      좋아요0
  • 수학장 2018.01.02 21:49:46

    점의 개수가 n인 완전그래프의 선분에 색칠하는 것 같네요. 최소 한 번만 감소하면 된다고 생각하면 되는데, 접근이 쉽지가 않네요.

    좋아요0 댓글수0
  • 수학장 2018.01.02 23:23:01

    선분 a_{1}a_{2}, ...., a_{m-1}a_{m}의 색번호가 단 한번만이라도 감소해도 조건을 만족하므로 이렇게 풀어봅시다.

    1. m을 고정시킨 후에, 그 m에 따라 선분 중 하나가 반드시 어떤 특수한 집합 안의 선분 두개의 연결 중 하나와 만나게 합시다.

    2. 특수한 집합 안에 반드시 들어가야만 하는 연결의 최솟값을 n의 크기별로 구한 후, 그에 맞는 k의 최솟값을 구합니다. 

    3. k의 최솟값이 고정된 k의 값보다 작게 하는 n의 최댓값이 문제의 답이 됩니다.

    이 문제를 풀려면 일단 설명 안의 '특수한 집합'이 무엇인지부터 알아내야 할 것 같습니다. 이때 특수한 집합이란, 모든 원소가 선분 2개로 이루어진 집합이며, 이 때 그 선분 2개를 작은 것부터 크기순으로 놓으면, 항상 감소하게 색을 칠해야 합니다. 그러면 모든 임의의 a_{1}, a_{2},...., a_{m}에 대해 이 집합의 원소가 들어가므로 반드시 어떤 연결 중 1개는 감소하게 됩니다.  아이디어 괜찮나요?

    좋아요0 댓글수3
    • RVEA 2018.01.15 21:20:31

      그러면 m을 3으로 보신다는 건가요? 집합에서 선분이 두개일려면 m이 3이여야 될것같은데...아니면 제가 잘못생각한건가요...ㅎㅎ

      좋아요0
    • 수학장 2018.01.15 21:44:33

      좀 표현이 애매하긴 한데,

      선분 2개의 연결이 모여있는 집합을 말하는 것입니다. 만약, m이 4여도, 선분 2개의 연결은 {{1,2},{2,4}}나 {{1.3},{3,4}}등 여러 가지가 았을 수 있습니다. 그런데, n에 대하여 m이 고정되어 있을 때 어떤 점을 골라도 이 특수한 집합의 원소 중 한 개는 들어가게 하는 것입니다. 그런데 제가 생각해봐도 방법이 좀 복잡한 것 같네요 .....  다른 방법을 생각해보는 게 더 나을 것 같아요

      좋아요0
    • RVEA 2018.01.16 20:45:58

      아 그런 말씀이셨군요...음....일단 알겠습니다.

      좋아요0
  • muse 2018.01.03 12:17:13

    이런 연결 두 개를 생각해 봅시다.

    a_1a_2a_3a_4\cdots a_n

    a_1a_3a_4a_5\cdots a_{n+1}

    이 경우에 다음이 성립하면 안 됩니다. 편의상 a_1, a_2 둘을 이은 변이 가지는 색을 c_{1, 2}라고 하겠습니다.

    c_{1, 2}\leq c_{2, 3}\leq c_{3, 4}\leq \cdots \leq c_{n-1, n}

    c_{1, 3}\leq c_{3, 4}\leq c_{4, 5}\leq \cdots \leq c_{n, n+1}

    이 두 식은 모두 거짓이어야 합니다.

    이 두 식을 합치면 무엇이 나올까요?

    좋아요0 댓글수1
    • 수학장 2018.01.03 12:29:40

      그러게요 무엇이 나올까요 잘 모르겠는데요

      좋아요0
  • Mathdragon 2018.01.04 19:54:21

    색번호가 순서대로 증가하거나 같은 값을 가질 수 없다는 말은 a1a2, a2a3, a3a4 등이 서로 같은 값을 가지면 안되니까 두번째 예시도 틀린 것 아닌가요?

    좋아요0 댓글수2
    • 수학장 2018.01.04 20:45:13

      그런 뜻이 아닙니다. a_{1}a_{2}, a_{2}a_{3}, ....등이 순차적으로 증가하거나 같으면 안됩니다. 즉, 한 번이라도 감소하는 부분이 있다는 것은 조건을 만족하는 겁니다. 같거나 증가하는 게 있다고 틀린 게 아닙니다.

      좋아요0
    • 김우현 기자 2018.01.08 10:00:04

      표현이 애매했군요! 수학장 님 말씀대로 수열의 일부분이 증가하거나 같은 값을 가지는 건 괜찮습니다. 수열 전체 값의 변화를 놓고 봤을 때, 같은 값에 머물거나 증가하는 추세만 아니면 된다는 뜻입니다. 평지나 오르막길로만 구성돼 있으면 안 되고 한 번즘은 내리막길이 있어야 하는 것이지요~ :)

      좋아요0
  • RVEA 2018.01.16 21:20:46

    음....m과 k를 무한대라고 치면 어떨까요

    m이 무한대면 n안에 m이 포함되니 자연적으로 n도 무한대가 된다....?

    으어....저만 어렵나요.....m이고정이라...무한대라고 볼수가 없을것 같은데....

     

     

    좋아요0 댓글수2
    • 수학장 2018.01.16 22:45:06

      '무한'이라는 개념 자체가 어떤 '수'로 보기는 어렵습니다. 하지만 m과k가 무한대로 간다면 n이 무한대로 가는 건 맞는데, 그걸 통해 알 수 있는게 뭘까요? 제 생각에는 없는 것 같습니다. 일단 m과 k에 2,3,4,..... 등을 대입해서 n의 최댓값을 찾고, 규칙을 찾아보면 어떨까요?

      좋아요0
    • RVEA 2018.01.16 22:50:56

      엄....그렇죠....무한대가 특정하게 고정된 수가 아니니까....너무 어렵네요.....

      좋아요0
  • 수학장 2018.01.16 23:14:00

    일단 m이 2일 때는 k 값에 상관없이 n은 존재하지 않는 것 같습니다. k가 1일 때도 마찬가지입니다.

    좋아요0 댓글수5
    • 수학장 2018.01.16 23:22:27

      m이 3, k가 2일 때는 n의 최댓값이 3입니다. 그런데, 이걸 풀면서 뭔가를 발견했는데, 일단 점의 순서쌍 {a,b,c}가 있을 때, ab가 색 2이고 bc가 색 1이어야 합니다. 그런데 만약 bc가 다른 순서쌍 {b,c,d}처럼 앞에 존재하는 쌍이 있다면, 조건이 성립되지 않는다는 겁니다. 이거는 m이 3이고, k가 2일 때에 한정되어 있지만 확장시키면 문제를 푸는 데 괜찮은 아이디어가 될 것 같아서 써봤습니다.

      좋아요0
    • 수학장 2018.01.17 09:55:15

      m=3 일 때 n의 최댓값은 k+1입니다. 점에 대한 순서쌍 {1,2,3}, {2,3,4}, {3,4,5},....{n-2,n-1,n}이 있을 때, 선분 12, 23의 색은 감소해야 합니다.(점 a와 점b를 이은 선분의 색을 간단하게 ab라 하겠습니다.)그리고 선분 23, 34도 감소해야 합니다. 또, 선분 34,45도 감소해야 합니다. 이걸 반복하다 보면, 12>23>34>45>....>(n-1)n이 됩니다.(여기서 12,23,34 등은 숫자가 아닙니다.) 즉, k는 n-1보다 크거나 같아야 합니다. 즉, n의 최댓값은 k+1이라는 것을 알 수 있습니다. 대각선으로 간다는 것은, 몇 개의 점을 건너 뛴 다는 것이기에, n의 최댓값에 영향을 주지 않습니다.

       

      대각선을 무시해도 된다는 점을 이용하면 문제를 풀 수 있을 것 같습니다.

      좋아요0
    • RVEA 2018.01.17 14:08:17

      m이 4와 5일떄도 찾아내서 규칙만 찾아내면 연립해서 풀수있을것 같은데....

      좋아요0
    • RVEA 2018.01.17 14:21:07

      음....그러면 m=4일때도 k+1이 되지 않을까요 {1,2,3,4} {2,3,4,5}....{n-3,n-2,n-1,n]이라고 잡으면 같은 방법으로... 처음 선분을 13이라고 잡으면 13>34>45>......>(n-1)n이 되지 않나요

      그러면 m=4일떄도 최댓값이 k=n+1이 되는데...

      좋아요0
    • 수학장 2018.01.17 16:33:10

      RVEA님 m이 4 이상이면 선분은 3갠데 한번만 감소하면 되기 때문에 k+1보다 클 겁니다.

      좋아요0
  • 수학장 2018.01.17 22:29:04

    m이 4면 두가지 색으로도 n이 6일 때까지 칠할 수 있습니다. 점a, 점b를 이은 직선의 색을 [a][b]라고 하면

    [1][2]=2 [1][3]=2 [1][4]=1 [2][3]=2 [2][4]=1 [2][5]=1 [3][4]=1 [3][5]=1 [3][6]=1 [4][5]=2 [4][6]=1 [5][6]=1로 두가지 색으로 칠할 수 있습니다. m이 3이었을 때는 2가지 색으로 n위 최댓값은 3인걸로 보아 m보다 n이 더 빨리 커지는 것 같습니다. 그리고 저번 댓글에 제가 대각선은 무시해도 될 것 같다고 했는데, 아무리 생각해봐도 증명은 못 하겠고, 확신도 안 들어요. 그 말은 확실해지기 전까지는 신경쓰지 말아주세요. n이 7 이상일 때는 안 해봤는데, 두 가지 색으로 될까요?

    좋아요0 댓글수5
    • Liter 2018.01.18 11:49:30

      [1][2]=2이고 [2][4]=1인이유를 설명해주실수 있으신가요.....

      좋아요0
    • 수학장 2018.01.18 15:51:36

      꼭 저렇게 해야 하는 건 아니고요 제가 찾은 답은 저거예요

      어떤 4개의 점을 골라도 색이 계속 증가하거나 같은 값을 가지지 않습니다

      좋아요0
    • RVEA 2018.01.18 18:30:32

      [2][4]에서 [3][6]까지 색이 계속 1인데 오류난것 아닌가요 [3][4]가 2가 되어야 되지 않을까요

      좋아요0
    • 수학장 2018.01.18 18:56:33

      [3][4]가 2가 되면 {1,2,3,4}를 뽑았을 때 색은 2,2,2로 조건을 만족하지 않습니다.

      여기서는 어떤 조합으로 수를 뽑든 계속 증가하거나 같은 추세를 보이지 않습니다. 답은 맞는 것 같은데요.

      좋아요0
    • RVEA 2018.01.19 11:37:40

      아 그렇네요 제가 잘못생각한것같습니다

      좋아요0
  • 수학장 2018.01.18 19:06:18

    m이 4이고, k가 2면 n은 6이 최대인 것 같습니다. 근데, 경우의 수가 많아서 증명해봐야겠어요. 그리고, m이 3일 때는 대각선과 상관 없이 k+1은 맞는 것 같습니다. 대각선 무시하면 안 된다고 해서 이것까지 틀렸다고 할 까봐 부가 설명했습니다.

    좋아요0 댓글수2
    • 데카르트 2018.01.19 10:10:41

      n>k이라면n에 포함되지만 k에 포함되지 않는 수가 i,j로 결정되면 이 수를 만족하는 k의 값,즉 두 점을 연결할 수 있는 색이 존재하지 않습니다.

      따라서 k>n이거나 k=n인데 n을 만족하는 i,j의 값이 가장 클때 k값으로 선을긋고 j와 i-1을 k와 중복되지 않는 값으로 이으려면 

      k>n일 수밖에 없습니다.

      좋아요0
    • 수학장 2018.01.19 10:43:22

      문제를 잘못 이해하신 것 같은데요?

      좋아요0
  • muse 2018.01.23 11:18:12

    (오류 제보)

    사각형 채우기 문제 댓글이 안 내려갑니다.

    빠른 수정 부탁드립니다.

    좋아요0 댓글수4
    • 수학장 2018.01.23 20:45:56

      맨 아래로 내려가면 1페잊 2페에지 3페이지 있는데요

      좋아요0
    • 구머 2018.01.23 22:17:49

      그니까 1페이지에서 2페이지로 넘어가야 하는데 댓글 내용이 안 바뀌는 거죠

      좋아요0
    • 수학장 2018.01.23 22:48:38

      어 진짜네요? 한 번 수학동아에 문의해볼게요

      좋아요0
    • 조가현 기자 2018.01.24 09:15:54

      댓글 오류 확인했습니다. 현재 사이트 수정 중에 있습니다.

      빠른 시일 안에 사이트가 제대로 운영될 있도록 힘쓰겠습니다.

      불편을 드려 죄송합니다.

      좋아요0