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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대8. 고른 순서쌍 찾기

2017.08.04

같이 풀어볼까?

네이버밴드 구글플러스

양의 정수 n\ (n\ge 2)이 주어져 있습니다. 두 정수 a, bn으로 나눈 나머지가 서로 같으면 a \equiv b \pmod n 이라고 표기하겠습니다. 또한 an으로 나눈 나머지를 a\ (\text{mod } n)이라고 나타내겠습니다.

 

정수로 이루어진 순서쌍 (a_1, a_2,\dots, a_n)이 다음 성질을 만족하면 '고른 순서쌍'이라고 정의합니다 : b_1+b_2+\cdots+b_n \equiv 0 \pmod n을 만족하는 정수로 이뤄진 임의의 순서쌍 (b_1,b_2,\dots,b_n)에 대해, 일대일 대응 함수 \sigma : \{1,2,\dots,n\} \to \{1,2,\dots,n\}가 존재해
a_{\sigma(1)}b_1+a_{\sigma(2)}b_2+\cdots+a_{\sigma(n)}b_n \equiv 0 \pmod n … 조건 (1)을 만족한다.

, 순서쌍 (a_1, a_2,\dots, a_n)의 순서를 적당히 바꿔 순서쌍 (b_1,b_2,\dots,b_n)과 쌍마다 곱한 뒤, 이를 모두 더한 값이 n의 배수가 되면 고른 순서쌍이라고 정의합니다.

 

문제 1  순서쌍 (a_1, a_2,\dots, a_n)이 고른 순서쌍이면 a_1+a_2+\cdots+a_n \equiv 0 \pmod n조건 (2)를 만족함을 보이세요.

 

문제2 양의 정수 n이 홀수면, 위의 조건 (2)를 만족하는 순서쌍 가운데 고르지 않은 순서쌍이 항상 존재함을 보이세요.

 

이제 양의 정수 n은 항상 짝수라고 가정하겠습니다.

문제3 위의 조건 (2)를 만족하는 순서쌍 (a_1, a_2,\dots, a_n)\vert \{a_1\ (\text{mod } n), \,a_2\ (\text{mod } n),\dots, \, a_n\ (\text{mod } n)\}\vert=2를 만족하면 고른 순서쌍임을 보이세요.

 

문제4 위의 조건 (2)를 만족하는 순서쌍 (a_1, a_2,\dots, a_n)\{a_1\ (\text{mod } n),\,a_2\ (\text{mod } n),\,\dots, \, a_n\ (\text{mod } n)\}=\{0,\,1,\,n-1\}을 만족하면 고른 순서쌍임을 보이세요.

 

(참조) 위의 조건 (2)를 만족하는 순서쌍 (a_1, a_2,\dots, a_n){\color{Blue} }{\color{Blue} }은 항상 고른 순서쌍이라는 주장이 Bialostocki Conjecture(비알로스토키 추측)입니다. 만약 짝수 n{\color{Blue} }이 8이하면 이 가설은 참이라고 알려져 있습니다.

댓글 44

  • shine 2017.08.06 14:18:00

    문제 1은 b_{1}=b_{2}=\cdots =b_{n}=1인 경우를 보면 자명합니다.

    좋아요1 댓글수0
  • shine 2017.08.06 15:12:45

    문제 2

    n이 홀수일때 _{}1+2+\cdots +n=\frac{n(n+1)}{2}\equiv 0(mod\: n) 이므로 (a_{1},a_{2},\cdots ,a_{n})=(1,2,\cdots ,n) 이 조건 (2)를 만족한다. 만약 이것이 고른 순서쌍이라면 (b_{1},b_{2},\cdots ,b_{n})=(1,-1,0,0,\cdots 0,0) 에 대해, 일대일 대응 함수 \sigma :\left \{ 1,2,\cdots ,n \right\}\rightarrow \left \{ 1,2,\cdots ,n \right\}가 존재해 a_{\sigma (1)}-a_{\sigma (2)}\equiv 0(mod \: n), 즉 a_{\sigma (1)}\equiv a_{\sigma (2)}( mod \: n) 이어야 한다. 하지만 (a_{1},a_{2},\cdots ,a_{n})의 모든 수들이 n으로 나누었을 때 나머지가 서로 다르므로 이를 만족할 수 없다. 그러므로 (1,2,\cdots ,n)는 조건 (2)를 만족하는 순서쌍 가운데 고르지 않은 순서쌍이 된다.

    좋아요0 댓글수2
    • 구머 2017.08.22 16:03:08

      shine님 혹시 수식 어떻게 쓰셨는지 알려주실 수 있으신가요?ㅜㅜ

      좋아요0
    • shine 2017.08.23 14:55:54

      폴리매스 뉴스에서 사용법 확인 가능합니다.

      좋아요0
  • steve 2017.08.13 14:41:04

    문제 4번 풀이 입니다.

    \alphak(mod n)=0 를 만족하는 \alphak들만 있으면  순서쌍(\alpha1,\alpha2,\alpha3,····)는 고른 순서쌍이다.

    하지만 n으로 나눴을 때 나머지가 1과  n-1인 \alphak들도 있기 때문에 순서쌍(\alpha1,\alpha2,\alpha3,····)이 고른 순서쌍이 되려면 나머지가 1인 \alphak의 개수는 나머지가 n-1인 \alpha k의 개수와 같아야 한다.

    그런데 \alpha1+\alpha2+\alpha3+····+\alphan 을 n 으로 나눴을때 나머지가 0 이여야 하기 때문에  n으로 나눴을때 나머지가 1인 \alphak 의 개수 는 나머지가 n-1인 \alpha k  의 개수와 같다.

    즉,순서쌍 (\alpha1,\alpha2,\alpha3,····)은 고른 순서쌍이다.

     

     

     

    좋아요0 댓글수1
    • shine 2017.08.14 09:48:39

      "고른 순서쌍이 P를 만족한다." 와 "이 순서쌍이 P를 만족한다." 가 성립해도 "이 순서쌍이 고른 순서쌍이다." 는 성립한다는 보장이 없습니다.

      고른 순서쌍임을 보이려면 조건(1)이 성립함을 보여야합니다. 

      좋아요1
  • steve 2017.08.14 19:40:30

    네,맞습니다.고치겠습니다.

    n 으로 나누었을때 나머지가 1인 ak들에 곱해질 bk들 의 합=c  라고 정의합시다.또,나머지가 n-1인  ak에 곱해질 bk  의 합을 d라고 합시다.

    조건1을 만족하려면   1•c+ (n-1)•d=0 (mod n)이여아 합니다.정리해보면 nd+c-d=0(mod n)이되고,nd는 n 의 배수이기  때문에 빼면 c-d=0(mod n) 가 됩니다.

    즉,   c=d(mod n) 를 만족하면 순서쌍  (a1,a2,a3,···) 이 고른 순서쌍이 됩니다.

    좋아요0 댓글수0
  • steve 2017.08.18 19:04:05

    c=d(mod n)이 아니게 된다고 해도 ak들의 순서쌍의 순서를 바꿔서 같게 할 수 있으니 (아무리 다 나머지가 다르게 하려고 해도 같은 나머지인 ak들이 있고,n=짝수이기 때문에 나머지가 같게 할수 있다.) 4번 중명됨!

    좋아요0 댓글수2
    • 구머 2017.08.19 19:04:37

      구체적인 증명 부탁합니다.

      좋아요0
    • 여백 패르마 2017.08.19 20:06:19

      닉네임을 steve에서 여백 페르마로 바꾸었습니다. 양해부탁드립니다.

      그리고 구머 님 말씀대로 지금 더 덯붙이려고 하고 있습니다. 조언 감사합니다!

      좋아요0
  • 여백 패르마 2017.08.20 20:42:47

    4번은 증명 못해도 3번은 할수 있을 것 같습니다.

    ak들이 모두2(mod n)일때 ak들의 순서쌍은 고른 슌서쌍입니다.또,모두 나머지가 n-2(-2)(mod n)이면 ak들의 순서쌍은 고른 순서쌍이다.

    이번에는 2와 -2 나머지가 섞인 경우를 생각해보자.b1~bc의 수들은 2에 곱해젔고 bc+1~bn의 수는 n-2와 곱해졌다고 가정하자.그러면 b1~bc의 합의 4배는 n의 배수여야 한다고 나온다.또,b1~bc의 합의 두배는 bc+1~bn의 합의 두배와 n으로 나눴을때의 나머지가 같다.그렇기 때문에 b1~bc의 합은 bc+1~bn의 합과 n의 배수만큼 차이나야  한다.(원래 n/2의 배수이지만 n의 배수는 n/2의 배수이다.)그둘의 합중 더 작은것을 x라고 하자.그러면 나머지 합은 x+na(a는 상수.)이다.그 둘의 합은 2x+na이다.그 합이 n의 배수이니 2x는 n의 배수이다.위에 4x는 n의 배수이여야 그 순서쌍은 고른 순서쌍이라고 했다.그런데 2x는 n의 배수이다.즉 ,그 순서쌍은 고른 순서쌍이다.

    좋아요0 댓글수6
    • 여백 패르마 2017.08.20 20:43:37

      미흡한 부분이 있을 수도 있으니, 문제 있는 부분은 댓글 남겨주세요. 문제 있는 부분은 고치도록 하겠습니다. 채크 부탁드립니다!

       

      좋아요0
    • shine 2017.08.21 11:51:31

      음... 착각하시는 것 같은데 집합 A에 대해 \left | A \right |는 A의 원소의 갯수를 나타내는 기호입니다.

      그러니 \left | \left \{ a_{1}(mod \: n),a_{2}(mod \: n),\cdots , a_{n}(mod \: n)\right \} \right |=2가 뜻하는 것은 a_{1},a_{2},\cdots a_{n} 의 n으로 나눈 나머지가 두 종류가 나온다는 것이지 나머지가 2 또는 n-2 가 나온다는 말이 아니지요.

      좋아요0
    • 구머 2017.08.22 16:01:26

      게다가 저 풀이도 좀 그렇네요. 우선 4(b1+...+bc)가 n의 배수여야 한다는 것은 (a1,a2,...,an)이 고른 순서쌍일 때 성립하는 것인데, 아직 (a1,a2,..an)이 고른 순서쌍이라는 것이 증명되지 않은 상태에서 저 조건은 사용이 불가능합니다. 또, (b1+b2+...+bc)와 (bc+1+...+bn)이 mod n에서 같다고 하셨는데, (b1+b2+...+bc)의 합은 mod n에서 0, (bc+1+....+bn)은 mod n에서 n/2일때는 성립하지 않습니다.

      좋아요0
    • 여백 패르마 2017.08.27 15:33:57

      그 문제는 ak들의 순서를 바꾸면 됩니다

      좋아요0
    • 구머 2017.08.27 17:15:46

      2(b1+b2+...+bc)-2(bc+1+...+bn)이 왜 n의 배수인지가 이해되지 않습니다. 혹시 (a1,a2,...an)이 고른 순서쌍이라고 가정해서 이런 결과가 나오신건가요?

      (만약 그런것이라면 이 풀이는 순환논리에 빠지게 됩니다)

      좋아요0
    • 여백 패르마 2017.08.28 18:56:25

      앗 그렀네요!

      좋아요0
  • 여백 패르마 2017.08.27 15:32:05

    아마도 4번 증명 가능할것같습니다.

    C와d(위위의 댓글 참고)중 더 작은 것을 x이라고 하고,나머지를 (고른 순서쌍이라고 가정하면) x+na라고 하자.그런데 모든 짝수는 둘의 합인 2x+na로 나타낼 수 있다.즉,언제나 c와 d의 차가 n위 배수가 되도록 할수 있다.(그러지 않는다고 해도 ak의 순서를 바꿔서 그렇게 되게 할수 있다.)

     

    좋아요0 댓글수2
    • shine 2017.08.27 16:07:42

      그런데 모든 짝수는 둘의 합인 2x+na로 나타낼 수 있다. 에서

      언제나 c와 d의 차가 n의 배수가 되도록 할수 있다. 가 어떻게 도출되는 것인지 설명해주실 수 있나요?

      좋아요0
    • 구머 2017.08.27 18:09:50

      그러지 않는다고 해도 ak의 순서를 바꿔서 그렇게 되게 할수 있다. 이 부분은 엄밀한 증명이 필요합니다.

      좋아요0
  • 구머 2017.08.27 19:19:25

    1-3 반쪽짜리 풀이:먼저 편이상 \equiv기호를 ==라고 합시다. 그리고, 임의의 자연수 a와 b의 최소공약수를 gcd(a,b)라고 합시다.

    (a_1, a_2,\dots, a_n)의 구성원소가 x, x+c라고 둡시다. 그리고 x+c가 t개 있다고 가정합시다. 이때, (a_1, a_2,\dots, a_n)이 고른 순서쌍임을 보이는 문제는 (c,c,c,..c,0,0,...0)이 고른 순서쌍임을 보이는 문제와 동치입니다.(c가 t개 있음) 이때, 문제의 조건 (2)에 의해 ct==0(mod n)이 성립하고, c==0(mod \frac{n}{(n,t))})를 만족합니다. 또, (a_1, a_2,\dots, a_n)이 고른 순서쌍이라면 (b_1,b_2,\dots,b_n)중 t개를 뽑은 임의의 집합 {bf(1),bf(2).....bf(t)}에 대해, c{bf(1)+...bf(t)}가 n의 배수가 되어야 하고, 이는 b_{f(1)}+b_{f(2)}+\cdots +b_{f(t)}==0(mod (n,t))일 때 잘 성립합니다. 즉, 임의의 t에 대해 b_{f(1)}+b_{f(2)}+\cdots +b_{f(t)}==0(mod (n,t))인 함수 f가 존재한다....(i)를 보이면 됩니다. 그런데 임의의 n에 대해, p가 n의 약수일때 b_{f(1)}+b_{f(2)}+\cdots +b_{f(t)}==0(mod p)인 f가 존재한다....(ii)를 보이면 (i)는 성립합니다. 왜냐하면 (ii)가 성립한다고 가정하고, (n,t)=p라고 하면, (ii)에 의해 총합이 mod (n,t)에 대해 0인 p개의 bi들을 뽑을 수 있고, 남은 n-p 또한 p의 배수이므로 다시 p개의 bi들을 뽑을 수 있습니다. 이런식으로 p개씩 계속 뽑아주면 총합이 mod (n,t)에 대해 0인 t개의 bi들을 뽑을 수 있습니다.//

    이제 (ii)를 증명할 것입니다. 우선 p\leq \sqrt{n}인 경우에는 비둘기집 원리에 의해 (mod p)를 기준으로 같은 수들이 p개 이상 존재합니다. 이 수들을 전부 고르면 그들의 총합은 mod p에 대해 0과 같습니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.08.27 19:26:41

    shine 님 모든 짝수 가 2x+na로 나타낼 수 있다는 것은 x를 구할 수 있다는 것이고 구머님께서 말씀 하신것을 증명하면 (4)번을 증명한다는 것입니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.08.27 20:08:11

    구머님이 말씀하신 부분은 0~ n-1의 수들중 임의의 숫자n개를 뽑을 때 (모든 숫자는 무한개 있습니다.)언제나 두 수를 모은 순서쌍 중 첫번째순서쌍의 합을 n으로 나눴을때의 나머지와 두번째의 합을  n으로 나눴을때의 나머지가 같게 만들 수 있다는 문제와 동치입니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.09.03 18:04:56

    c=d라는 것을 증명가능할것 같습니다.

    먼저, ak 들을 n으로 나눈 나머지가 순서쌍 (1,2,3,4,···,n)이라고 합시다.그러면 더하면 n의 배수이 되는 짝들을 c,d로 정하면 됩니다.(예를 들어 1과 n-1,또는 2와 n-2와 3과 n-3가 있다.)

    그리고 그 수들중 하나를  바꿨다고 합시다.그러면 순서쌍의 수들중 하나와 같게되니 그 수를 다른 팀(c,d )에 넣고 그다음 합이 n의 배수가 되는 것들을 넣으면 됩니다.

    그 수들중 몇개를 바꿨다고 합시다.그러면 그 바꾼 수들과 같은 수를 다른 팀에 넣고 합이 n의 배수인 것들을 넣으면 됩니다.

    예) (1,2,3,4,5,6,7,8)change into (1,2,3,4,4,6,7,8)이라고 가정.그러면 c =(1,4,7),d=(2,4,6)이다.

    즉 4번 증명 끝!

    좋아요0 댓글수6
    • 여백 패르마 2017.09.03 18:14:33

      초등학교 4학년이어서 아직 부족한 부분이 있을 수 있습니다.

      위의 증명 과정 중에는 고칠 부분이 있을 수도 있으니, 댓글 달아주시길 바랍니다.

      고칠 점은 최대한 빠른 시일 내로 수정하겠습니다.

      감사합니다~~ : )

      좋아요0
    • 구머 2017.09.03 18:32:48

      (1,2,3,4,5,6,7,8)에서 원소 개수가 3개인 집합 2개를 뽑는다 하면 여백 페르마님의 풀이가 적용이 안될듯 한데요..

      좋아요0
    • 구머 2017.09.03 18:34:01

      그리고 1+2+3+...+8은 36, 즉 8의 배수가 아닙니다

       

      좋아요0
    • 여백 패르마 2017.09.03 18:45:44

      그렇군뇨!그럴때는 이러는것이 나을것 같습니다.

      먼저,c에 2개의 수로 이루어진 순서쌍을 넣습니다.그리고, c에 있는 순서쌍의 수들의 합보다 1더큰수가 합인 2개의 수로 이루어진 순서쌍을 d에 넣습니다.

      그런후 1차가 나는 수 2개를 찾아 큰 수는 c에 넣고 작은 수는 d에 넣으면 됩니다.(않되면 다른 순서쌍과 수들로 해보고,진짜 않되면 1을 2로 바꾸고 2도 않되면 3으로,등등등으로 하면 될것 입니다.원소의 개수가 홀수개일때 사용가능할것같습니다.)

      좋아요0
    • 여백 패르마 2017.09.03 18:50:16

      그리고 1~8까지 모든 수를 c,d에 넣을것이 아니니 1부터 8까지 모두 더하는 것을  따질 필요가 없다고 생각합니다.

      좋아요0
    • 구머 2017.09.03 23:48:37

      일단 패르마 님이 2017.09.03 18:45:44에 썼던 덧글의 아이디어를 이렇게 정리합시다: 원소가 3개이고 총합이 같은 집합이 존재한다. 이들을 c,d에 넣고 남은 원소들을 원래 방법대로 넣는다. 우선 이 부분도 당연히 증명이 필요하며, 설령 총합이 같은 집합이 있다고 해도 나머지 남은 숫자들로 남은 집합을 메울 수 있다는 것도 증명해야 합니다.(왜냐하면 c,d에 먼저 빠진 원소들 때문데 원래 패르마 님이 썻던 방법이 정상적으로 작용되지 않을 수도 있거든요) 또, 제일 처음 했던 풀이에서 (1,2,...,8)에서 2이 1, 6이 5로 변형, 3이 4로, 8이 5로 변형됬다고 하면, (즉, {1,1,4,4,5,5,7,5}) 패르마 님의 원래 방법도 먹히지 않습니다.

       

       

      좋아요0
  • 여백 패르마 2017.09.17 21:42:00

     

     

     

     

     

     

     

     

     

     

     

    죄송합니다  가로로 되버렸네요... 어쩔 수 없었습니다.

    좋아요0 댓글수10
    • 여백 패르마 2017.09.17 22:04:43

      제 증명에는 오류가 있을 수 있습니다.

      그래서 오류를 찾으신 분께는 댓글로 알려주시길 바랍니다.

      오류 정정하기 위해서 필요합니다. 감사합니다.

      좋아요0
    • 구머 2017.09.17 22:46:25

      3번: 합이 mod n에서 0인 원소 개수 c개의 집합은 애초에 무한개가 아니고(mod n 관점에서), 설령 무한개라고 해도 (b1,b2,.....bn)중에서 그 무한개의 집합의 부분집합이 포함되어 있어야 함을 증명해야 합니다.

       

      문제와 관련은 없는 내용이지만, 수학자 하디는 리만 가설을 증명하다가 무한개의 영점이 일직선 위에 있다는 것을 증명하였지만, 그게 모든 영점이 일직선 위에 있다는 것을 의미하는 것은 아닙니다. 지금 여백 페르마님이 생각한 오류와 비슷한....경우입니다

      좋아요0
    • 구머 2017.09.17 22:51:12

      4번 화질이...심각합니다. 읽을 수가 없어요 ㅜㅜ

       

      좋아요0
    • 여백 패르마 2017.09.18 18:40:27

      화질은 어쩔수 없을듯 합니다.그리고 '하디의 리만가설'문제는 이렇게 하면 될것 같습니다.평균이 n/c인 {bc}들의 개수는 모든 {bk}들의 개수와 일대응 대응을 하기 때문에 언제나 {bk}들 사이에 존재합니다.(리만가설에서는 일대일 대응이 아니기 때문에 틀린거구요)

      좋아요0
    • 여백 패르마 2017.09.18 18:41:39

      화질은 고치겠습니다.

      좋아요0
    • 구머 2017.09.18 23:23:33

      에..?1대1대응한다고요?

       

      좋아요0
    • 여백 패르마 2017.09.19 14:09:45

      왜나하면 기수가 같기 때문이지요

      좋아요0
    • 구머 2017.09.19 16:42:08

      근데 {Bc}의 개수가 유한개 아닌가요..?(mod n)

      좋아요0
    • 여백 패르마 2017.09.19 22:16:16

      {bk}들의 합의 수들의 경우만 유한한것 입니다.

      좋아요0
    • 구머 2017.09.19 23:41:32

      {Bc}들의 총 개수는 n^c개로, 유한합니다. 그러므로 {Bc}들의 집합 중 총합이 0인 집합도 유한합니다.(mod n)

      좋아요0
  • 여백 패르마 2017.09.18 19:54:01

    다시 찍었습니다.

    좋아요0 댓글수1
    • 구머 2017.09.18 23:28:04

      실례겠지만...그냥 컴퓨터로 타이핑해줬으면 합니다.. 

      좋아요0
  • 여백 패르마 2017.09.19 14:11:52

    수식 쓰는 방법이 이해가 않되서....(시그마도 아래 써야 하는 기호들 어떻하죠?)

    좋아요0 댓글수0