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

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가 참이다'를 증명하면 이 문제도 해결!

 

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

댓글 30

  • 구머 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

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

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

     

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

     

     Proof) 위 방정식의 모든 정수 계수들의 집합을 A라 합시다. 이때 집합 A의 임의의 부분합을 e, 집합 A의 모든 원소들의 합에서 e를 뺀 값을 j라 합시다. 그러면 조건 1의 동치로 e 또는 j가 0이라는 명제를 얻습니다. 이때 귀류법을 사용합시다. 그렇다면  'e 또는 j가 0이라면 자연수의 집합 \LARGE N을 유한 개의 색으로 잘 칠하면 한 가지 색깔로 이루어진 해 \LARGE x_{1}, \:x_{2},\cdots ,x_{n}존재하지 않는다.' 라는 명제를 얻게 됩니다. 따라서 조건 1이 참이고 조건2의 부정도 참이라면 모순이 발생함을 보입시다.

     잘 칠했을 때 같은 색으로 칠해진 서로 다른 두 자연수 k,l 과 집합 A의 임의의 원소 a_{d}에 대해 a_{d}\times l + (e+ j- a_{d})\times k \neq 0이 아니라면 조건 2의 부정도 거짓입니다. 그러므로 조건 1이 참이고, 위 식도 참이라고 가정합시다. 위 식을 정리하면 a_{d} \neq \frac{(e+j)k }{k-l}입니다. 이때  a_{d}가 0이 아닌 임의의 정수이므로 결론적으로 (e+j)k \not\equiv 0 (mod (k-l))이어야 합니다. 이때 조건 1이 참이므로 e또는 j가 0입니다. 편의상 e= 0이라 합시다. 그러면 jk \not\equiv 0 (mod (k-l)) 이 됩니다. 이때 j를 k-l의 배수 또는 0으로 잡으면 위 식이 항상 성립하지 않습니다. 어떤 색으로 칠해진 수가 1개만 존재한다면 자연수의 집합의 모든 원소들을 유한한 색깔 1개씩만 사용해서 색칠 할 수 없습니다.  따라서 조건 1이 참일때 조건 2도 참입니다.

     

    전체적인 증명 과정에 대한 요약:

     

    1. 조건 1에 대한 동치 명제로 <위 방정식을의 정수계수를 2덩어리로 잘 나누면 한 덩어리의 합을 0으로 만들수 있다.> 를 얻는다.

    2. 조건2의 부정을 하여 <자연수의 집합을 유한 개의 색으로 잘 칠하면 한가지 색으로 이루어진 해가 존재하지 않는다.> 를 얻는다.

    3. 2에서 얻은 명제가 참이라면 무조건 참인 명제를 얻는다.((e+j)k \not\equiv 0 (mod (k-l)), 이 명제가 거짓이면 조건 2의 부정은 무조건 거짓이다.)

    4. 1과 2에서 얻은 명제가 동시에 성립한다고 가정한다. 이때 1과 3에서 얻은 명제가 동시에 참이 아니라면 1과 2에서 얻은 명제도 동시에 참일 수는 없다.

    5. 1과 3에서 얻은 명제가 동시에 참이라고 가정했을때 나머지 한 부분합을 적절히 잡으면 모순이 생긴다.

    6. 따라서 1과 2에서 얻은 명제가 동시에 참이 아니므로 조건 1이 참이면 조건 2도 참이다.

     

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

       오류 검토 해 주실 분~

      좋아요0
    • 수학상자 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.02 18:54:39

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

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

    -묻힌 문제 구조대 올림-

    좋아요1 댓글수0