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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대23. 환상의 조합

2018.10.31

같이 풀어볼까?

네이버밴드 구글플러스

양의 정수 n에 대하여,

 

 

라 정의하자. 집합 \mathbb{Z}^{n}의 원소

 

X_{1} = (x_{11}, x_{12},..., x_{1n}), X_{2} = (x_{21}, x_{22},..., x_{2n}), X_{k} = (x_{k1}, x_{k2},..., x_{kn})

 

가 다음 성질을 만족하면 "(d_{1}, d_{2},..., d_{n})-환상의 조합"이라고 부른다. (단, d_{i}는 양의 정수):

 

임의의 1\leq i\leq n에 대하여, x_{1i} + x_{2i} +...+ x_{ki}는 d_{i}의 배수이다.

 

다음 n개의 양의 정수 d_{1}, d_{2},..., d_{n}에 대하여, 다음 성질을 만족하는 최소의 양의 정수 t를 U(d_{1}, d_{2},..., d_{n})이라 정의하자:

 

다음 성질 : 원소의 개수가 t개인 집합 \mathbb{Z}^{n}의 임의의 부분집합에는 항상

"(d_{1}, d_{2},..., d_{n})-환상의 조합"이 반드시 존재한다.

 

예를 들어, U(d) = d임을 매우 쉽게 보일 수 있다.

 

(i) U(d_{1}, d_{2},..., d_{n}) \geq d_{1} + d_{2} + \cdots + d_{n} - n + 1이 성립함을 보여라.

(ii) 임의의 소수 p에 대하여, U(p, p,..., p)를 구하여라.

(iii) 양의 정수 d, a에 대하여, U(d, da) = da + d - 1임을 보여라.

(iv) 양의 정수 d, a, b에 대하여, U(d, da, dab)를 구하여라.

 

 

댓글 13

  • 수학장 2018.10.31 22:06:46

    일단 문제가 이해가 안 가는 분들은 U(d)=d라는 것부터 보입시다. 그러다 보면 이해 되실 겁니다.

    좋아요0 댓글수5
    • 수학장 2018.10.31 22:23:17

      다음 성질에서 무슨 말이지 하실 수도 있는데 제 해석으로는 원소의 개수가 t개인 "집합 Z^n의 임의의 부분집합"에는..... 이라는 걸로 보입니다. 즉 Z^n의 원소의 개수가 t개가 아니고 부분집합의 원소의 개수가 t개라는 것입니다.

      좋아요0
    • 수학장 2018.10.31 22:30:33

      즉 U(d)=d를 증명하라는 것은 d개의 임의의 정수 중 몇 개의 수를 더했을 때 d의 배수가 되게 할 수 있는가?를 증명하라는 것인데 본문제가 아니므로 증명은 생략합니다.

      좋아요0
    • Kid Milli 2018.11.02 20:41:25

      ㄴㄴ '원소 개수가 k개인 Zn'의 임의의 부분집합입니다

      좋아요0
    • 수학장 2018.11.02 21:42:26

      그러면 모든 부분집합에 환상의 조합이 존재해야 되는데 그러면 말이 안 되는데요

      라고 했으니 \mathbb{Z}^n은 저 순서쌍을 모두 모아놓은 집합 같습니다.

      그리고 환상의 조합이라 함은 집합 내의 모든 원소를 더했을 때 나오면 환상의 조합이라는 게 아니고 그냥 집합의 원소 중 어떤 것을 골라서 더했을 때 저 조건을 만족하면 환상의 조합이라고 부르는 것이라고 해석됩니다.

      좋아요0
    • Kid Milli 2018.11.02 22:31:07

      ㅇㅋ 제가 틀린듯

      좋아요0
  • 뉴턴의 사과 2018.11.07 19:05:41

    1번은 U(d_{1}, d_{2},...,d_{n})<d_{1}+d_{2}+\cdots +d_{n}-n+1일 수 없다는 것을 보이면 될것 같은데욥.

    좋아요0 댓글수3
    • 수학장 2018.11.07 21:08:26

      별로 안 어려워요. U(d_1,d_2,...d_n)=d_1+d_2+...+d_n-n일 때 반례를 하나만 찾아주면 되는 거라

      좋아요0
    • 여백 패르마 2018.11.11 16:12:06

      반례를 한 개만 찾는다고 해도 1번을 푸는 것은 아닙니다. 

      좋아요0
    • 수학장 2018.11.11 21:20:18

      맞습니다. 일반적인 반례 하나만 찾으면 됩니다.

      좋아요0
  • 유끌리드 기하학 2018.11.16 21:09:51

    U(d)=d 증명은 매우 쉽게 할 수 있습니다.
    즉, d개의 정수 중 임의의 몇 개를 선택해서 d의 배수가 나올 수 있음을 증명하는 것입니다.

    d개의 정수를 a1, a2, ... ,ad라고 하고, 집합 N을 {a1, a1+a2, ... ,a1+a2+...+ad}으로 정의합니다.
    그 다음, 경우를 두 가지로 나눕니다.
    ① N의 원소 중 d의 배수가 있을 때: 당연히 성립합니다.
    ② N의 원소 중 d의 배수가 없을 때: N의 d개의 원소들을 k1~kd라고 합니다. ki≡kj (mod d)를 만족하는 1 이상 d 이하의 서로 다른 i, j가 반드시 존재합니다. (일반성을 잃지 않고 i>j라고 가정) 즉, ki-kj가 d의 배수가 되게 하는 i, j가 존재합니다. 정리하면, aj+1+aj+2+...+ai는 d의 배수입니다. 따라서 a1~ad중 임의의 몇 개를 선택한 합이 d의 배수인 경우는 존재합니다.

    좋아요0 댓글수2
    • 여백 패르마 2018.11.16 21:51:27

      아닙니다. d개일 때가 최소임을 증명해야 완벽합니다. 

      좋아요0
    • 수학장 2018.11.18 20:05:53

      d-1개일 때는 모든 d값이 1과 d를 법으로 합동일 때 성립하지 않으니까 불가능합니다. d가 최소입니다.

      좋아요0