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

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가 참임이 증명되면 곧바로 '해결' 스티커를 붙이도록 하겠습니다. 

댓글 18

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

      좋아요0
    • 구머 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

     

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

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

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

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

      좋아요0