본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대55. 해의 개수
수학동아 2021.07.06 11:52 조회 814

양수 a_{1}, a_{2},\cdots, a_{k}와 실수 a가 주어져 있을 때, 다음과 같은 방정식을 생각합니다.

a_{1}x_{2}+a_{2}x_{2}+\cdots +a_{k}x_{k}=a                           (1)

이 방정식의 해 (x_{1}, x_{2},\cdots ,x_{k}) 중에서 각각의 x_{i}가 모두 1 또는 −1인 해의 개수에 대하여 알고 싶습니다. 구체적으로, 해의 개수가 항상 2^{k}/\sqrt{k} 이하라는 사실을 증명하고 싶습니다. 다음과 같은 과정을 거쳐서 이 문제를 풀고자 합니다.

 

문제 1. 임의의 실수 y_{1}, y_{2},\cdots ,y_{k}와 양의 정수 q에 대하여, 다음의 부등식을 만족시키는 q 이하의 적당한 자연수 d와 정수 n_{1}, n_{2}, \cdots ,n_{k}가 존재함을 보이세요. 

\left | y_{i}-\frac{n_{i}}{d} \right |\leq \frac{1}{dq^{1/k}}

 

1번의 결과를 사용하여, 문제에서 주어진 양수 a_{1}, a_{2},\cdots, a_{k}를 음이 아닌 정수로 바꾸고자 합니다. 음이 아닌 정수 m_{1}, m_{2},\cdots ,m_{k}가 주어졌을 때, 정수 am_{1}x_{1}+m_{2}x_{2}+\cdots +m_{k}x_{k}의 형태로 나타내는 방법의 수를 r(a)라고 합시다. (단, x_{i}는 모두 1 또는 −1입니다.)

 

문제 2. 만약 r(a)\leq 2^{k}/\sqrt{k}이 항상 성립함을 증명한다면, 방정식 (1)의 해의 개수가 2^{k}/\sqrt{k}이라는 사실이 증명됨을 보이세요.

1, 2번을 통해서 주어진 문제에 나오는 수를 모두 정수로 바꾸어 생각할 수 있음을 알 수 있습니다. 이제, 다음 부등식을 증명하면 문제 풀이가 완료됩니다.

 

문제 3. 임의의 정수 a와 음이 아닌 정수 m_{1}, m_{2},\cdots ,m_{k}에 대하여, r(a)\leq 2^{k}/\sqrt{k}임을 보이세요.

  •  
    A math Lv.6 2021.07.12 12:28

    q^{1/k}은 q^{\frac{1}{k}}을 말하는 거겠죠?

    댓글 작성하기 좋아요0 댓글수1
  •  
    A math Lv.6 2021.07.14 15:07

    k개의 정수 n_{1} --- n_{k}는 q보다 작아야 해요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      A math Lv.6 2021.07.14 15:08

      아니면 d만 q보다 작아야 해요?

      좋아요0
    •  
      A math Lv.6 2021.07.14 15:24

       

      아. n_{1}---n_{k}가 p 이하가 되면 안 되는구나. 

      좋아요0
  •  
    Scubed Lv.6 2021.07.16 00:04

    (1)

    우선, 0\leq y_i< 1일 때만 조사하면 된다는 것을 보입시다.

    만약 \left | y_i \right |\geq 1이라면, y_i=a_i+b_ia_i는 정수, 0\leq b_i< 1로 둘 수 있습니다.

    그렇다면, 

    y_i-\frac{n_i}{d}=a_i+b_i-\frac{n_i}{d}

    가 됩니다.

    여기서, 그러면 n_i=da_i+c_ic_i는 정수로 둘 수 있습니다.

    대입하면 

    y_i-\frac{n_i}{d}=a_i+b_i-\frac{n_i}{d}=a_i+b_i-a_i-\frac{c_i}{d}=b_i-\frac{c_i}{d}

    가 됩니다. 이를 통해 y_i의 정수부분은 n_i를 적당히 조절함으로써 무기력하게(독립변수라고 해야 하나요? 쨌든 영향을 안 준다는 의미에요) 만들 수 있습니다.

    그럼 이제 0\leq y_i< 1일때를 봅시다.

    (i) 0< y_i< 1

    우선 준 식을 조금 정리하겠습니다. 식을 d에 관해서 정리하니

    \frac{n_i}{y_i}-\frac{1}{y_iq^{1/k}}\leq d\leq \frac{n_i}{y_i}+\frac{1}{y_iq^{1/k}}

    로 나오게 됩니다. 여기서 0< y_i< 1이라는 사실을 이용하면 자명하게도 됩니다.

    (ii) y_i=0

    대입하고 정리하면

    n_i\leq \frac{1}{q^{1/k}}

    이 됩니다. n_i=0이면 되겠군요.

    따라서, d,n은 존재합니다.

     

    (제 풀이가 이상하다고 생각하실 수 있는데 저도 처음엔 그렇게 생각했습니다. 하지만, 0\leq y_i< 1에서 d,n이 있으면 나머지 경우에서도 모두 d,n이 있으므로 0\leq y_i< 1일 때만 따진 것입니다. 실제로 \left | y_i \right |\geq 1이 되어버리면 위의 풀이(i)의 논리가 성립하지 않는 경우가 많습니다. 하지만 근의 존재 유무를 묻는 것이기 때문에 저는 이 풀이과정만으로도 충분하다고 생각합니다.)

     

    혹시 풀이에 틀렸거나, 접근 방법 자체가 잘못되었다거나, 아니면 보충이 필요한 부분 등 잘못된 부분이 있으면 너그러운 마음으로 진심을 담은 조언을 부탁드립니다.

    댓글 작성하기 좋아요1 댓글수8
    •  
      A math Lv.6 2021.07.16 19:01

      제가 나름 생각해 (1)번을 정리했을 땐 모든 임의의 0보다 크고 1보다 작은 k개의 실수(그러니까 \small y_{1} ... y_{k})와 모든 임의의 양의 정수 q에 대해 어떤 한 q 이하인 양의 정수 d가 있어 \small dy_{1}, dy_{2}, ... dy_{k}의 소수부분이 모두 \small \frac{1}{\sqrt[k]{q}} 이하이거나 모두 \small 1 - \frac{1}{\sqrt[k]{q}} 이상이게 할 수 있는가?

      라는 게 되는데...

      좋아요0
    •  
      A math Lv.6 2021.07.16 21:03

      음... 그런데 왜 저 부등식이 자명하게 된다는 거예요? 저는 잘 모르겠네요. 

      위에 제가 대댓글 단 것도 자세히 보면 Scubed 님과 같은 말이 나오긴 하는데(그러니까 y_{1}...y_{k}가 0보다 크고 1보다 작을 땐 n_{i}가 0일 때와 -1일 때만 생각하면 되고, 그러면 위에서 제가 한 말이 돼요. ), 저는 계속 저 부등식이 왜 성립하는지 1일 반 정도(?) 생각하고 있었거든요. 혹시 증명했다면 알려주세요. (그럼 괄호 1번 푼 거고. )

      좋아요0
    •  
      Scubed Lv.6 2021.07.16 23:58

      흠...솔직히 저는 그냥 그 부등식이 자명하게 느껴지기는 한데요......

      증명을 해야 한다면 해야죠. 저도 증명 한번 생각해볼게요.

      좋아요0
    •  
      Scubed Lv.6 2021.07.17 00:12

      식을 변형해보았는데요,

      \left \lfloor \frac{n_i}{y_i}+\frac{1}{y_iq^{1/k}}\right \rfloor-\left \lfloor \frac{n_i}{y_i}-\frac{1}{y_iq^{1/k}}\right \rfloor\neq 0

      이 되는 정수n_i가 언제나 존재한다는 것이군요.

      이걸 정의역이 실수인 함수로 조금 변형시키니

      f(x)=\left \lfloor \frac{\left \lfloor x \right \rfloor}{y_i}+\frac{1}{y_iq^{1/k}}\right \rfloor-\left \lfloor \frac{\left \lfloor x \right \rfloor}{y_i}-\frac{1}{y_iq^{1/k}}\right \rfloor\neq 0

      이 되는 x가 언제나 존재한다는 것이네요. 참고로 d는 앞의 것이니 앞의 것은 양수여야 합니다. 그러므로 x는 1이상이어야 합니다.

      그러면은 f(x)가 {x\geq 1}에서 항상 0이 되지 않는다는 것을 보이면 됩니다.

      미분을 쓰고 싶지만 최대정수함수는 도함수가 없군요!

      이렇게 할 수 있을까요??? 아니면 다른 방법을 찾아야 할까요?????

       

      +만약 이 함수를 쓰려면 이 함수가 상수함수가 아니라는 것만 증명하면 됩니다

      좋아요0
    •  
      A math Lv.6 2021.07.17 15:18

      음... 그런데 사실 x는 dy_{i}거나 dy_{i} + 1이에요. 이 말은 n_{i}가 dy_{i}의 정수부분이거나 dy_{i}의 정수부분 + 1이라는 건데 그렇지 않으면 준 식은 성립하지 않아요. 

      좋아요0
    •  
      A math Lv.6 2021.07.18 10:12

      그런데 사실 이렇게 하는 건 소용없어요. 위~의 부등식이 성립하는지 증명하는 것이긴 한데, y_{1}에서 y_{k}까지의 실수들에 대해 공통인 d가 존재하는 지 묻는 거니까 이렇게 하는 건 소용없어요. 

      좋아요0
    •  
      Scubed Lv.6 2021.07.18 20:50

      우선은 n_i=\left \lfloor dy_i \right \rfloor or \left \lfloor dy_i \right \rfloor+1인건 맞고, 그러면 어차피 y_i가 달라지니까 d랑 n도 달라질 수밖에 없으니 d가 항상 같다고 할 수는 없지 않나요?

      좋아요0
    •  
      A math Lv.6 2021.07.22 20:25

      d가 항상 같을 수는 없지만 각각의 y_{1}, y_{2}, .... y_{k}의 경우에 대해서 y_{1}, y_{2}, .... y_{k}에 대해 모두 같은 d를 말하는 거예요. 

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911