leejseo의 블로그

Theorem. $A$가 $[n]$의 몇몇 부분집합들로 이루어진 집합이라고 하자. 모든 $A$의 원소는 크기가 $r$이고, 임의의 두 $x, y \in A$에 대해 $x \cap y \neq \emptyset$이다. 이 때, $A$의 크기는 $\pmatrix{ n-1 \\ r-1 }$ 이하이다. (이 때, $ n \geq 2r$이다.) Proof. 이 정리에 대한 증명은 단순한 더블카운팅으로 가능하다. $[n]$과 $A$가 주어졌다고 가정하자. 이제, 우리는 원주상에 $[n]$의 원소들을 cyclic order로 배열을 하고, $A$에서 길이가 $r$인 구간들에 대해 생각할 것이다. 예를 들어, $n = 6$이고 $r = 2$이고, cyclic order $(1, 5, 4, 2, 3, 6)$을 택한 경우..

문제. 양의 정수 $N$이 다음 두 조건을 만족하면 $n$-좋은 수 라고 하자.(조건 1) $N$은 $n$개 이상의 서로 다른 소수로 나누어진다.(조건 2) $N$을 나누는 서로 다른 $n$개의 양의 정수 $1, x_2 , x_3 , \cdots , x_n$이 존재하여 $1 + x_2 + \cdots + x_n = N$을 만족한다.이 때, $n \geq 6$이면, $n$-좋은 수가 언제나 존재함을 보여라. 풀이.이 문제 또한 전형적인 귀납법을 사용하면 풀리는 문제이다. 1) Base Case: 6-좋은 수의 경우에는 $N = 2 \cdot 3 \cdot 7 \cdot 13 \cdot 43 \cdot 139$로 두면, 6-좋은 수가 되어 성립한다. 2) 어떤 양의 정수 $n$이 존재하여 $k$ 좋은 수라고..

문제. 어떤 $999 \times 999$ 크기의 체스판에 어떤 칸들은 흰색으로, 다른 칸들은 빨간색으로 칠해져 있다. $T$가 다음을 만족하는 순서쌍 $(C_1 , C_2 , C_3 )$의 개수라고 하자:1) $C_1 $과 $C_2$는 같은 행에 있고, $C_2$와 $C_3$는 같은 열에 있다.2) $C_1$과 $C_3$는 흰색이고, $C_2$는 빨간색이다.이 때, $T$의 최댓값을 구하여라. 풀이.이 문제는 전형적인 Double Counting으로 Bound를 잡아주는 문제임을 쉽게 유추할 수 있다. Claim. $n \times n$ 크기의 체스판에서 $\frac{4}{27} n^4 $이 $T$의 upper bound 이다.Proof. $i$행 에서의 빨간 칸의 개수를 $a_i$, $j$열 에서의 ..