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

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국11. 왜 같은 조건일까? (가정 추가)

2017.10.31

같이 풀어볼까?

네이버밴드 구글플러스

 

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

 

0이 아닌 정수 계수 \LARGE a_{1}, \:a_{2}, \:a_{3},\cdots ,a_{n}으로 이뤄진 방정식 \LARGE a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\cdots +a_{n}x_{n}=0을 생각하자.

다음 두 조건이 동치임을 보여라.

 

동치: 조건 1이 참이면 조건 2도 참, 조건 2가 참이면 조건 1도 참일 때 두 조건이 '동치'라고 한다. 

 

조건

1. 각 \LARGE x_{i}가 0 또는 1이고, 모든 \LARGE x_{i}들이 다 0은 아닌 해를 가진다.

2. 자연수의 집합 \LARGE N을 유한 개의 색으로 어떤 방식으로 칠해도, 한 가지 색깔로 이루어진 해 \LARGE x_{1}, \:x_{2},\cdots ,x_{n}이 적어도 하나 존재한다.

 

 

※알립니다

'조건2가 참이면 조건 1이 참이다'를 shine 친구가 가장 먼저 증명했습니다. 

인천 오일러 친구가 '조건1이 참이면 조건2가 참이다'를 증명!

11번 문제도 최.종.해.결.입니다!!!smiley

 

그동안은 소질문 여러 개로 이뤄진 문제에서 일부 질문이 해결됐을 때만 '부분해결' 스티커를 붙였습니다. 이 문제는 질문 1개로 이뤄졌기때문에 절반이 증명됐다고 하더라도 부분해결 스티커를 붙이지는 않을게요. 조건1이 참이면 조건2가 참임이 증명되면 곧바로 '해결' 스티커를 붙이도록 하겠습니다. 

댓글 56

  • 구머 2017.11.01 18:25:23

    뭔가 복숭아 문제 고른 순서쌍 문제와 유사한것 같네요

    좋아요0 댓글수1
    • 수학동아 2017.11.02 15:07:09

      아..아니에요! 고른 순서쌍 문제와 달리 modulo 연산이 없고, 다른 아이디어로 풀어야 하는 문제라구욧 >_<

      좋아요0
  • 누군가 2017.11.02 22:36:49

    a_1=1,a_2=-1 로 두면(1\cdot x_1+(-1)\cdot x_2=0x_1=x_2 일 때만 조건2가 성립합니다.  이렇게 x_n들이 같아도 된다면

    조건1을 만족시킬 때 x_i 가 1이 었던a_n 들에게 똑같은 x_n을 주면 나머지(조건1에서 x_i=0인) a_n들이 모두 양수거나 음수라면 조건2를 절대 만족 시킬 수 없습니다..(자연수 집합에 0을 포함한다면 0을 대입하면 되겠지만 그러면 별로 의미가 없는 문제니까....)제한조건이 더 붙어야 할 것 같습니다...

    좋아요0 댓글수0
  • shine 2017.11.03 16:28:57

    보일 것: 조건 2가 참이면 조건 1도 참이다.

     

     

    증명

    명제의 대우가 참이면 명제 또한 참이다. 그러니 다음 명제를 보이자.

    [방정식의 각 x_i가 0 또는 1인 해는 모든 x_i들이 0일 때로 유일할 때,

    자연수의 집합을 유한 개의 색으로 잘 칠하면 한 가지 색깔로 이루어진 해가 없게 할 수 있다.]

     

    우선 모든 a_1,a_2,\cdots ,a_n의 부분합과 서로소인 소수 p를 잡자. 

    그리고 함수 f:N\rightarrow \left \{ 1,2,\cdots ,p-1 \right \}을 다음과 같이 정의하자.

    [자연수 a에 대해 \frac{a}{p^k}가 정수가 되는 최대의 정수 k에 대하여, f(a)는 \frac{a}{p^k}를 p로 나눈 나머지이다.]

    이때 자연수의 집합 N을 함수 f의 함수값에 따라 p-1개의 색으로 칠하면, 한 가지 색깔로 이루어진 해가 존재하지 않음을 보이자.

    1 이상 n-1 이하인 임의의 자연수 k를 잡아 f(x)=k인 색을 보자.

    귀류법: 이 색으로만 이루어진 해 \left ( x_{1},x_{2},\cdots ,x_{n} \right )=\left ( b_{1},b_{2},\cdots ,b_{n} \right )가 존재한다고 가정하자.

    i) b_{i}들 중 적어도 하나가 p의 배수가 아닐 때

    a_1 b_1+a_2 b_2+\cdots +a_n b_n\equiv 0(mod\: p) 이다.

    b_1,b_2,\cdots ,b_n\equiv 0 ,k(mod\: p)이므로, 

    (a_i들 중 몇개의 합)\times k\equiv 0(mod\: p)이다.

    그런데 k는 p와 서로소이므로 a_i들 중 몇개의 합\equiv 0(mod\: p),

    이는 p가 모든 a_1,a_2,\cdots ,a_n의 부분합과 서로소임에 모순된다.

    따라서 이 경우에 해당하는 해는 존재하지 않는다.

    ii) b_{i}들 모두 p의 배수가 일때

    \frac{gcd\left ( b_{1},b_{2},\cdots ,b_{n} \right )}{p^r}이 정수가 되게 하는 최대의 정수 r에 대해,

     \left ( x_{1},x_{2},\cdots ,x_{n} \right )=\left ( \frac{b_{1}}{p^r},\frac{b_{2}}{p^r},\cdots ,\frac{b_{n}}{p^r} \right )또한 해이다. 

    이 해에 대해 i)과 같은 방법을 적용하면 모순을 이끌어 낼 수 있다.

     

     

    두 경우 모두 모순이니, 이 색으로만 이루어진 해가 없다.

    이 색이 1 이상 p-1 이하인 임의의 자연수 k에서 f(x)=k인 색이므로,

    모든 색에서 이것이 성립한다. 

    증명완료

     

     

    좋아요1 댓글수6
    • shine 2017.11.03 16:29:11

      작성 중 입니다.

      좋아요0
    • shine 2017.11.05 19:55:04

      수정했습니다.

       

      좋아요0
    • 수돌이 2017.11.06 00:04:38

      역시 한발 늦었었네

      좋아요0
    • 고은영 기자 2017.11.10 18:11:58

      shine 님, 조건 2가 참이면 조건 1도 참이 되는 증명을 잘 해주셨습니다. smiley

      좋아요1
    • 구머 2017.11.10 21:11:19

      그나저나 shine이 부분해결을 했는데 그렇게 안 뜨네요.

      좋아요1
    • 수학동아 2017.11.14 13:41:20

      문제가 여러 개의 질문으로 이뤄졌을 경우, 일부 질문이 해결되면 부분해결 표시를 해왔습니다. 이 경우는 질문 1개로 이뤄져있고, 그 질문을 해결하는 중이기 때문에 부분해결 표시는 하지 않아도 될 것 같아요! smiley 나머지가 해결되면 곧바로 해결 스티커를 붙이려구요.

      좋아요1
  • 수돌이 2017.11.05 13:08:11

    2번에서 자연수 집합->정수 집합으로 바꿔야 할 것 같은데요

    a_1=1 a_2=0이라 하면 자연수해가 나오지 않는지라

    1은 만족하지만 2는 만족하지 않습니다.

    좋아요0 댓글수1
    • 수학동아 2017.11.06 10:34:00

      수돌이 님 안녕하세요:) 문제에 '정수 계수는 0이 아니다'라는 가정을 추가했습니다. 혼란을 드려 죄송해요(ㅜㅜ). 이 가정을 반영해서 풀어주세요~>_<

      좋아요0
  • 수돌이 2017.11.05 13:29:11

    ~1->~2 증명

    방정식은 각 x_i가 0 또는 1이고, 모든 x_i들이 다 0은 아닌 해를 가지지 않는다

    (동치) a_1,a_2,...,a_n중 몇 개를 잘 더해서 0을 만들 수 없다.

     

    아주 큰 소수(모든 a_i들의 절댓값의 합보다 크게) P를 생각하고 다음과 같이 정수 집합을 색칠합니다.

    0이 아닌 각 정수 n에 대해, n을 P로 나누어 떨어지지 않을 때까지 나눈 다음 그 때 P로 나눈 나머지에 따라

    색 C1,C2,...,C(P-1)을 부여합니다.

    0은 색 C(P)를 부여합니다. 그러면 0은 쓸 수 없겠죠.

     

    자 이제 같은 색으로 칠해진 x_i로만 이루어진 해가 존재한다고 가정합시다.

    x_i 각각을 소인수분해했을 때 P의 지수가 가장 낮은 것이 있을 것입니다. 그 수를 b라 합니다.

    자 이제 이 방정식을 mod p^(b+1)로 봅시다. 그러면 x_i들은 mod p^(b+1)로 0 또는 k*p^b 일 것입니다

    이 k들은 모두 같습니다. 왜냐하면 위 조건에 의해서 색이 모두 같기 때문이죠.

    따라서 이 방정식의 값이 0이 되려면 mod p^(b+1)로도 0이 되어야 합니다. 그러면 이 방정식은 다음과 같이 변형됩니다.

    k*p^(b+1) (선택된 몇 개의 a항들의 합) + 0*(나머지 몇 개의 a항들의 합) = 0 mod(p^(a+1))

    따라서 선택된 몇 개의 a항들의 합은 p의 배수가 되어야 합니다. 

    p가 모든 a_i들의 절댓값의 합보다 크게 잡았으므로 0이 되어야 합니다. 그런데 a_1,a_2,...,a_n중 몇 개를 잘 더해서 0을 만들 수 없으므로 모순.

    따라서 2 조건도 만족하지 않습니다.

    좋아요0 댓글수1
    • 고은영 기자 2017.11.10 18:43:11

      shine 님이 비밀 글 설정 상태로 답을 작성하는 도중에 수돌이 님이 댓글을 다셨군요! 아쉽게 한 발 늦었지만 수돌이 님도 '조건 2가 참이면 조건 1이 참이다'를 잘 증명하셨습니다. 

      좋아요0
  • 수학장 2017.11.22 21:57:06

    색으로 칠한다는 게 무슨 뜻이죠?

    좋아요0 댓글수0
  • 수학자 2018.01.28 11:56:20

    Van der Waerden's theorem이라는 정리가 좀 도움이 될 수도 있겠네요.

    "임의의 정해진 자연수 \small r,k에 대해서, 어떤 자연수 \small N이 존재하여, \small 1부터 \small N까지를 \small r가지의 다른 색깔로 칠했을 때, 등차수열을 이루며 같은 색깔로 칠해진 길이 \small k인 수열이 존재한다."

    https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

     

    좋아요1 댓글수2
    • 수학장 2018.01.28 13:30:46

      1부터 N까지 r개의 색으로 적절하게 색칠하는 건가요 아니면 임의로 색칠하는 건가요

      좋아요0
    • 수학자 2018.01.28 21:18:13

      임의의 색칠에 대해서 존재한다는 것입니다. 어떻게 칠하더라도 등차수열이 나온다는 점에서 강력한 정리입니다.

      좋아요1
  • 인천 오일러 2019.01.02 16:10:10

     

    증명할 명제: 조건 1이 참이면 조건 2도 참이다. 

     

     Proof) 위 방정식의 모든 정수 계수들의 집합을 A라 합시다. 이때 f 를 집합 A의 합이 0이 되는 공집합이 아닌 부분집합이라고 합시다. 집합 A의 모든 원소들의 합에서 f를 뺀 값을 j라 합시다.

     

     편의상 부분합중 0이 되는 부분을 이루는 계수들을 방정식의 뒷부분으로 미룹시다. n=2일  때 조건에 의해 a_{1}+a_{2}=0입니다. 그런데 이 경우 x_{1}=x_{2}일 때 조건1을 만족시키는 임의의 정수 계수 a_{1},a_{2} 에 대해 어떻게 칠해도 같은 색으로 칠해진 해가 존재하게 됩니다. n>2일 때, 합이 0이 되는 정수 계수들증 일부를 잘 더해 e, -e로 만들수 있습니다. 합을 e, -e 로 이루는 정수 계수의 미지수들을 각각 x_{1},x_{2}로 전부 같게 하고 나머지 정수 계수들의 미지수들을 x_{3}로 같게 하여 방정식을 ex_{1} +jx_{3} =ex_{2}로 재구성합니다.이때 편의상 e, j가 양수라 합시다.(j가 음수라면 방정식을 변형하여 ex_{2}-jx_{3}=ex_{1}로 바꾸어 줍니다. j0이라면 x_{1}=x_{2}일 때 어떻게 칠해도 같은 색으로 칠해진 해가 존재하게 됩니다.  ) 이때 x_{1}=X,  x_{2}=X+jY,  x_{3}=eY은 자연수 X,Y 값에 상관없이 항상 해입니다. 그리고 어떻게 색칠해도  X,eY,X+jY가 모두 같은 색인 자연수 X,Y 가 존재합니다.*(이 정리는 따로 증명이 되어 있습니다만 정리의 이름을 알 수가 없어 첨부합니다.)

     

    따라서  f=0이고  2 이상의 모든 자연수 n에 대해  방정식 a_{1}x_{1}+a_{2}x_{2}\cdots a_{n}x_{n} =0 에서 어떻게 칠해도 같은 색으로 칠해진 해가 존재합니다. 따라서 모든 경우에서 어떻게 칠해도 같은 색으로 칠해진 해가 존재하므로   f=0이면 자연수의 집합 \LARGE N을 유한 개의 색으로 어떻게 칠해도 한 가지 색깔로 이루어진 해가 존재합니다. 즉, 조건 1이 참이면 조건 2도 참입니다. 

     

     *원명제 :임의의 자연수 l,m,n에 대해 m개의 색으로 자연수 집합을 칠했을 떄 적당한 자연수 X,Y가 존재하여, X, nY,X+Y,X+2Y\cdots X+(l-1)Y의 색이 같다.  여기서 n=e,  l\geq j+1로 하면 위 조건을 만족하는 자연수 X,Y가 존재합니다.

     

    덧붙여서, 이 문제는 Rado's theorem이라는 정리와 관련 있음을 자료 검색하다 발견했습니다. 위 *의 증명과 Rado's theorem의 내용이 궁금하신 분은 첨부된 파일을 참고하여 주세요.(Gregory E. W. Taylor 라는 분이 작성한 문서입니다.) /resources/comment/2019/02/312080c7eb5c65976cbb786715441d6c.pdf

     

    좋아요0 댓글수36
    • 인천 오일러 2019.01.03 16:31:45

       오류 검토 해 주실 분~

      좋아요2
    • 수학상자 2019.01.04 15:43:53

      잘 모르겠네요...

      좋아요0
    • 인천 오일러 2019.01.09 19:18:17

       혹시 너무 틀리면 검토를 안 해주시나요...?

      좋아요0
    • 김우현 기자 2019.01.10 09:22:33

      인천 오일러 친구의 풀이는 현재 검토 중!

      출제자 검토에 앞서 다른 친구들의 의견을 들어보기 위해 조금 늦게 요청한 점 양해 부탁드려요!smiley

      좋아요0
    • 김우현 기자 2019.01.10 17:52:05

      문제를 출제한 백진언 연구원도 친구들의 의견을 기다려보는 게 좋겠다고 해요!

      그 사이 인천 오일러 친구도 혹시 생각하지 못한 오류가 없는지 검토해 보는 건 어떨까요??laugh

      좋아요0
    • 인천 오일러 2019.01.10 18:07:26

      좋아요0
    • Gauss_J 2019.01.13 00:17:10

       인천 오일러님 죄송한데 논리 구조 같은 것을 간단하게 설명덧붙여 주시면 안 될까요? 복잡해서요.

      좋아요0
    • 인천 오일러 2019.01.13 11:38:20

       추가했습니다.

      좋아요0
    • Gauss_J 2019.01.13 20:30:53

       오 감사해요

      좋아요0
    • 수학자 2019.01.19 13:05:09

      흥미로운 접근입니다. 다만, 임의로 잡을 수 있는 것과 없는 것을 구분할 필요가 있을 것 같습니다.

      1. 집합 A의 임의의 원소 a_d를 잡았는데, a_{d}가 0이 아닌 임의의 정수에 대해 a_{d} \neq \frac{(e+j)k }{k-l}가 성립하는 것은 아닙니다.

      2. "j를 k-l의 배수 또는 0으로 잡으면"이라 되어 있는데, j는 집합 A의 모든 원소들의 합으로 정해지는 값입니다.

      좋아요0
    • 인천 오일러 2019.01.19 16:23:49

       수학자님,  감사합니다.  그걸 놓쳤네요. 수정할 방안을 찾아보겠습니다.

      좋아요0
    • 인천 오일러 2019.01.30 22:42:15

       수정을 해 보았습니다. 오류 검토 부탁드립니다.

      좋아요0
    • 1975fanboi 2019.01.31 00:08:27

      인천 오일러님 x_1 + x_2 - x_3 = 0에 대해 귀납법이 잘 되지 않는 거 같습니다 (x1과 x2를 묶으면 조건 1을 만족하지 않고, x1, x3 / x2, x3을 묶으면 문제의 가정인 계수가 0이 아니라는 것과 맞지 않습니다)

      좋아요0
    • 인천 오일러 2019.01.31 20:31:24

      저도 갑자기 그 생각이 나서 내용을 추가하려 합니다. 감사합니다.

      좋아요0
    • 인천 오일러 2019.02.01 00:51:08

       보완을 해 보았습니다.

      좋아요0
    • 인천 오일러 2019.02.01 10:13:41

      다시 보니까 모든 방정식의 경우들이 n=3의 경우로 치환할 수 있네요. 더 간단한 풀이가 있었네...

      좋아요0
    • 인천 오일러 2019.02.01 15:42:27

       간단한 풀이: 방정식을 ex_{1}+ jx_{3}= ex_{2}로 변형하면 위에서 증명한 것과 같이 어떻게 칠해도 한 가지 색으로 이루어진 해가 존재한다.

      좋아요0
    • 초코Pi 2019.02.01 21:55:33

       완벽한 것 같습니다.

      좋아요0
    • 초코Pi 2019.02.02 22:34:36

       근데 제가 신입이라 그러는데 보통 풀이 검토에 얼마나 걸리나요? 출제 기관마다 다르나요?

      좋아요0
    • 인천 오일러 2019.02.03 18:31:01

       기간은 경우에 따라 다르지만 언젠가는 답변해 주십니다!

      좋아요0
    • 인천 오일러 2019.02.05 19:39:17

       더 간단한 풀이로 고쳤습니다.

      좋아요0
    • 초코Pi 2019.02.09 21:14:33

       혹시 인천 오일러님 방법으로 조건 2->조건 1도 증명할 수 있지 않을까요?

      좋아요0
    • 인천 오일러 2019.02.11 21:00:19

       저 풀이는 적어도 1개의 해가 존재한다는 것을 보이기 위해 그 쪽으로 집중한 풀이라 어렵지 않을까 라고 생각합니다. 하지만 잘 응용하면 될 것도 같습니다.

      좋아요0
    • 초코Pi 2019.02.12 22:47:07

      아 그러네요

      좋아요0
    • 초코Pi 2019.02.19 21:39:09

      이 문제 풀이 올리신지 1달 다 되어가는데 검토 안 해주시나요? 개인적으로 맞는지 궁금해서요.

      좋아요0
    • 김우현 기자 2019.02.20 14:22:03

      기다리게 해서 미안해요.crying

      처음 올렸던 풀이를 계속해서 잘 보완했군요. 인천 오일러 친구의 풀이는 연구원님께서 오늘 내로 직접 댓글을 달아줄 예정입니다!

      좋아요0
    • 출제자(국) 2019.02.20 18:13:20

      출제자입니다. 먼저 인천 오일러 친구와 초코Pi 친구에게 답이 늦어져서 미안해요 ㅜㅜ 피드백을 5일 전에 준비했는데요, 폴리매스 계정 설정이랑 그 외 다른 일들로 전달하지 못했네요. 전반적으로 문제를 잘 푸셨습니다! 이로서 인천 오일러 친구가 남은 부분을 해결했구요, 준비한 피드백 내용이에요:

      1. 풀이를 서술할 때 A의 임의의 부분합을 f라고 해서 약간 혼동이 왔습니다. 보통 '임의'라 함은 특정한 하나의 합이 아니라 모든 합의 가능성을 고려하는 것이기 때문에, '임의'라는 말은 f또는 j가 0이라고 하는 특수한 상황과 맞지 않습니다. 대신 'f를 합이 0이 되는 A의 공집합이 아닌 부분집합이라고 하자' 라고 하면 더욱 명료해집니다.

      2. 논리를 전개할 때 j가 0이 될 수 있는 가능성을 고려해야 합니다. 지금 풀이에서는 j가 0이 아닌 경우만을 고려했는데요, j가 0이 될 수 있는 경우엔 A의 모든 계수의 합이 0이기 때문에 모든 x_i들을 같은 수로 잡으면 쉽게 해결됩니다. 쉽게 해결할 수 있는 경우지만 완전한 풀이를 위해서는 언급해야 해요.

      무엇보다 수학을 공부할 때는 끈기가 중요한데, '인천 오일러' 친구가 문제에 끈기를 가지고 문제를 고민했기에 문제를 해결할 수 있었던 것 같아요! 논리 전개와 서술에 있어 좀 더 엄밀하고 명료하게 서술할 수 있다면 더욱 더 실력을 상승시킬 수 있을 것 같습니다. 문제 해결 축하드려요!

      좋아요0
    • 출제자(국) 2019.02.20 18:20:28

      한가지 첨언하자면, 이 문제는 '수학자' 친구가 올린 더 약한 정리인 Van der Waerden's theorem만을 가지고도 해결할 수 있습니다. Rado's theorem이 Van der Waerden's theorem으로 증명되니 (첨부파일의 증명이 그렇습니다) 구분하는 것이 크게 의미있지는 않지만, 원래 의도는 '인천 오일러' 친구가 적은대로 방정식을 단순화시킨 뒤 Van der Waerden's theorem으로 증명을 하는 방식이었어요. '인천 오일러' 친구가 올려주신 자료는 문제에서 묻는 동치 결과를 훨씬 일반화한 정리 (Theorem 4.0.1)를 증명하기 위해 Rado's theorem을 Chapter 4에서 씁니다.

      좋아요0
    • 인천 오일러 2019.02.20 18:31:36

      네, 감사합니다!

      좋아요0
    • 초코Pi 2019.02.20 20:50:57

      오~ 인천 오일러님 축하해요! 저는 Van der Waerden's theorem로 푸는 법을 찾아봐야겠네요

      좋아요0
    • 인천 오일러 2019.02.20 21:59:53

       감사합니다. 저도 연구하려합니다. 같이 힘내요!

      좋아요0
    • 김우현 기자 2019.02.21 11:31:01 비밀댓글
      비밀댓글 입니다.
    • 인천 오일러 2019.02.21 12:03:07 비밀댓글
      비밀댓글 입니다.
    • 인천 오일러 2019.02.25 16:34:47 비밀댓글
      비밀댓글 입니다.
    • 김우현 기자 2019.02.27 13:57:13 비밀댓글
      비밀댓글 입니다.
    • 인천 오일러 2019.02.28 15:26:59 비밀댓글
      비밀댓글 입니다.
  • 김우현 기자 2019.01.02 18:54:39

    오랜만에 댓글이 달렸습니다!

    인천 오일러 친구가 나머지 한 쪽 방향 증명을 올려줬어요. 친구들이 풀이를 검토해 주세요!surprise

    -묻힌 문제 구조대 올림-

    좋아요1 댓글수0