본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대55. 해의 개수
수학동아 2021.07.06 11:52 조회 2498

대한수학회 55번

 

해의 개수

 

 

문제 출제자 : 이지운 KAIST 수리과학과 교수

 

 

양수 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}임을 보이세요.

  •  
    Amath Lv.8 2021.07.12 12:28

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

    댓글 작성하기 좋아요0 댓글수1
  •  
    Amath Lv.8 2021.07.14 15:07

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

    댓글 작성하기 좋아요0 댓글수2
    •  
      Amath Lv.8 2021.07.14 15:08

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

      좋아요0
    •  
      Amath Lv.8 2021.07.14 15:24

       

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

      좋아요0
  •  
    Scubed Lv.7 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 댓글수9
    •  
      Amath Lv.8 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
    •  
      Amath Lv.8 2021.07.16 21:03

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

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

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

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

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

      좋아요0
    •  
      Scubed Lv.7 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
    •  
      Amath Lv.8 2021.07.17 15:18

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

      좋아요0
    •  
      Amath Lv.8 2021.07.18 10:12

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

      좋아요0
    •  
      Scubed Lv.7 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
    •  
      Amath Lv.8 2021.07.22 20:25

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

      좋아요0
    •  
      김다인(멘토) Lv.15 2021.11.22 01:28

      0<y_i<1 부분이 자명하지 않습니다..!! 다시 도전해보세요~!

       

      다인 멘토 드림

      좋아요0
  •  
    Anonym Lv.5 2022.02.05 05:08 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    Anonym Lv.5 2022.02.13 15:15

    문제 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}}

     

    문제에 대해 해결은 하지 못했습니다. 이런 식으로 풀이전개를 해봤습니다. 임의의 실수 y_{1}, y_{2},\cdots ,y_{k}를 정수와 소수점 자리 부분들로 생각하면 다음과 같이 표현가능하고

     

    y_{i}=Y_{i}+\alpha _{i}\;s.t\; Y_{i}\; is\; integer\; and\; 0\leq \alpha _{i}< 1

     

    이에 문제 1의 부등식을 만족시키는  n_{1},n_{2},\cdots ,n_{k}는 다음과 같이 표현 가능합니다.

     

    n_{i}=dY_{i}+\beta _{i}\;s.t\; \beta_{i} \:is \: integer\; and\; 0\leq\beta _{i}\leq d

     

    따라서 문제1은 다음과 같이 쓸 수 있습니다.

     

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

     

        \left | \alpha_{i}-\frac{\beta _{i}}{d} \right |\leq \frac{1}{dq^{\frac{1}{k}}}

     

    여기서 수학적 귀납법을 이용하여 증명하려 합니다. "q에 대하여 1부터 k까지 위 부등식을 만족한다면 k+1에 대해서도 만족한다."는 것을 보이고 싶습니다.

     먼저 다음 식을 정의하겠습니다.

     

    S_{k}=\left \{ \alpha _{1},\alpha _{2},\cdots \alpha _{k} \right \}

    d_{S_k,q}=\left \{ d\; \mid \; \beta _{i},d \; s.t\;\alpha _i\in S_{k},\; \left | \alpha_{i}-\frac{\beta _{i}}{d} \right |\leq \frac{1}{dq^{\frac{1}{k}}}\;for\; i=1,2,\cdots ,k \right \}

     

    d_{S_{k},q}는 0이상 1이하의 k개의 임의의 실수에 대하여 1번문제의 부등식을 성립되는 d의 집합들입니다. 하지만 0이상 1이하의 k+1개의 임의의 실수에 대해서는 q^{1/k}\rightarrow q^{1/k+1}로 바뀜으로 다음식을 생각할 수 있습니다.

     

    D_{S_k,q}=\left \{ d\; \mid \; \beta _{i},d \; s.t\;\alpha _i\in S_{k},\; \left | \alpha_{i}-\frac{\beta _{i}}{d} \right |\leq \frac{1}{dq^{\frac{1}{k+1}}}\;for\; i=1,2,\cdots ,k \right \}

    I_{d,q}=\left \{ x\; \mid d\; is \; nonnegative \; integer,\;0\leq x\leq 1\; and\; \left | x-\frac{i}{d} \right |\leq \frac{1}{dq^{\frac{1}{k+1}}}\;for\; i=0,1,\cdots ,d \right \}

     

    이는 d_{S_{k},q}\rightarrow D_{S_{k},q} 으로 추가적인 d가 생겨 확장됩니다. 따라서  d_{S_{k},q}\subseteq D_{S_{k,q} 을 만족할 것 입니다. 그리고 I_{d,q} 는 0이상 1이하의 선상에 \frac{1}{d},\; \frac{2}{d},\; \cdots ,\; \frac{d-1}{d},\; \frac{d}{d}=1의 점들에서 반지름 \frac{1}{dq^{\frac{1}{k+1}}}의 범위를 만족하는 점들의 집합입니다.  여기서 

     

    \bigcup_{d\in D_{S_{k},q}} I_{d,q} =\left \{ \bigcup_{d\in d_{S_{k},q}} I_{d,q} \right \}\bigcup\left \{ \bigcup_{d\in D_{S_{k},q}-d_{S_{k},q}} I_{d,q} \right \}

    \alpha _{i}\in \bigcup_{d\in d_{S_{k},q}} I_{d,q} \; for\; i=1,2,\cdots ,k

    을 알 수 있고   [0,1]-\bigcup_{d\in d_{S_{k},q}} I_{d,q}\subseteq \bigcup_{d\in D_{S_{k},q}-d_{S_{k},q}} I_{d,q}를  만족한다면 즉  [0,1]\subseteq \bigcup_{d\in D_{S_{k},q}} I_{d,q} 이 된다면 기존의 d_{S_{k},q} 에서 d\in D_{S_{k},q}-d_{S_{k},q}를 추가하여 d_{S_{k+1},q}을 만들어 k+1에 대해서 성립 할 수 있습니다. 실제로 

     

    for\; q=9,k=1,k+1=2\;and\; \frac{2}{5}<\alpha _1=29/70< \frac{3}{7}

    then,

     d_{S_{k=1},q=9}=\left \{ 5,7 \right \},\; D_{S_{k=1},q=9}=\left \{ 2,3,5,7,8,9 \right \}

     

    로 나와 [0,1]\subseteq \bigcup_{d\in D_{S_{k=1}, q=9}} I_{d,q=9}를 만족하여 k+1=2에 대해서도 문제1의 부등식이 됨을 알 수 있었습니다. 여기서 진행을 어떤 식으로 해야할지 모르겠습니다. 피드백 부탁드리겠습니다. 감사합니다.

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    부분해결
    Anonym Lv.5 2022.02.21 06:06 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      유태영 멘토 Lv.3 2022.02.23 09:52

      좋은 접근입니다.

      풀이상에서 d는 N^k이하라는 조건만을 얻을 수 있으므로 d가 q 이하라는 조건을 만족하기 위해 조금 더 조작이 가해져야 합니다.

      좋아요0
    •  
      Anonym Lv.5 2022.02.23 15:22 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    다시 도전
    Anonym Lv.5 2022.02.21 08:12 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    부분해결
    Anonym Lv.5 2022.02.21 18:30 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      유태영 멘토 Lv.3 2022.02.23 10:31

      좋은 풀이입니다.

      2번 문제의 풀이과정에서 대응되는 mi들을 구할 수 있다고 했는데 이 관계가 잘 대응됨을 보여야 할 것 같습니다.

      3번 증명은 아주 좋습니다.

      여담으로 서술 과정에서 k=2p가 아닌 k=2l이 조금 더 나은 변수명 선택으로 보여집니다.

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

  • ☎문의 02-6749-3911