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

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

댓글 14

  • 구머 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 나머지가 해결되면 곧바로 해결 스티커를 붙이려구요.

      좋아요0
  • 수돌이 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