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

leejseo의 블로그

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

leejseo의 블로그

검색하기 폼
  • 분류 전체보기 (81)
    • 블로그 소개 (0)
    • 정보과학 (38)
      • 간략한 글 (1)
      • 알고리즘 (9)
      • 암호학 (0)
      • BOJ 풀이 (7)
      • 올림피아드 (11)
      • CodeJam (2)
      • Codeforces (7)
    • 수학 (31)
      • 간략한 글 (1)
      • 올림피아드 (16)
      • 이산수학 (9)
      • 고등학교 수학 (4)
    • 일상 (12)
  • 방명록

수학/이산수학 (9)
테셀레이션

합동인 볼록 다각형으로 평면을 빈틈없이 채우는걸 테셀레이션이라고 합니다. 이때, 서로 다른 두 면은 변을 공유하지 않거나, 정확히 하나의 변을 "완전히" 공유해야 합니다. 예를 들어, 아래는 볼록 오각형을 이용한 테셀레이션입니다. 그렇다면, 볼록 $n$각형으로 평면을 테셀레이션 하는건 언제 가능할까요? $n = 3, 4, 6$일 때는 정 $n$각형을 활용하면 됩니다. $n = 5$인 경우에는 위의 그림과 같이 하면 됩니다. 이 글에서는 $n \ge 7$일 때, 볼록 $n$각형으로 테셀레이션을 하는 것이 불가능함을 보일 것입니다. 먼저, 볼록 $n$각형을 활용한 테셀레이션이 주어져 있다고 합시다. 일반성을 잃지 않고, 각 면의 넓이가 $1$이라고 가정할 수 있습니다. 이들은 정점과 변, 그리고 면 모두가 ..

수학/이산수학 2019. 11. 22. 03:56
두 가지 조합기하 문제들

관심을 가지고 있는 조합기하 분야의 전형적인 극단(Extremal) 문제들을 모아보았다. 전부 open problem이다. 아직 잘 정리된 글은 아니다. 1. Happy Ending Problem Problem. 평면 상의 점들의 집합 $P$가 general position 에 있다. 이는, $P$의 어느 세 점도 하나의 직선 위에 있지 않음을 의미한다. 이 때, $P$가 볼록 $n(\ge 3)$각형이 포함함이 보장되는 $|P|$의 최솟값을 구하여라. 이 문제에서 $|P|$의 최솟값을 $ES(n)$이라 표기하자. 작은 $n$에 대해 $ES(n)$의 값을 구해보자. $ES(3) = 3$이고, $ES(4) = 5$, $ES(5) = 9$이다. 사실, $ES(4)$와 $ES(5)$의 값 또한 자명한 결과는 아..

수학/이산수학 2019. 11. 15. 10:07
이분그래프가 될 조건

Theorem. 그래프 $G$가 이분그래프임과 $G$가 홀수 길이의 사이클을 포함하지 않음은 동치이다. Proof. $G$가 이분그래프이면 홀수 길이의 사이클을 포함하지 않음은 명백하다. $G$가 홀수 길이의 사이클을 포함하지 않는다고 하자. $G$가 여러개의 컴포넌트로 이루어져 있다면, 각 컴포넌트를 따로 고려해주면 된다. 따라서, $G$가 연결그래프임을 가정할 수 있다. 이제, $G$가 연결그래프이므로, $G$의 spanning tree $T$를 잡을 수 있다. $T$ 상의 아무 정점에서나 시작해서 dfs를 하며 2-coloring을 해줄 수 있다. 만약, $G$의 어느 간선이 색이 같은 두 정점 $u, v$를 잇는다면, $T$ 상의 $u, v$를 잇는 경로와 해당 간선으로 이루어진 사이클은 길이가 ..

수학/이산수학 2019. 9. 6. 08:02
고정된 크기의 클릭의 수

그래프 상의 고정된 크기의 클릭의 수에 대하여 아래와 같이 아름다운 관계식이 성립한다. Theorem. 그래프 $G = (V, E)$에 대하여 크기가 $n$인 클릭의 수를 $a_n$으로 표기하고, $b_n = \sqrt[n]{n! a_n}$으로 정의하자. 이 때, $\{b_n\}_{n > 0}$은 감소수열이다. proof.$P(k)$를 임의의 $G$에 대하여 $b_1, b_2, \cdots , b_k$가 감소한다 로 정의하고, $k$에 대한 수학적 귀납법을 적용하자.먼저, $a_1 \geq a_2$가 됨은 매우 명확하다.$P(k)$가 참이라 가정하고, 임의의 $G = (V, E)$가 주어졌다고 하자.$|V| = n$이라 할 때, 각각의 정점을 $[n]$의 원소에 대응시켜 표현하자. 다음과 같이 표기법을 ..

수학/이산수학 2018. 4. 11. 16:53
Projective Plane의 Blocking Set의 크기

문제. Order가 $n$인 Projective Plane $(\mathcal{P}, \mathcal{L})$이 주어졌다고 가정하자. 이 때, 몇몇 점들의 집합 $A$가 - 어떠한 직선도 포함하지 않고,- 모든 직선과 교차점을 가지면$A$를 $(\mathcal{P}, \mathcal{L})$의 Blocking Set이라 한다. $|A| = m$이라 할 때, $m \geq n + \sqrt{n} + 1$임을 보여라. 증명.집합 $S$를 $A$에 속하지 않는 점 $p$와 $A$에 속하는 서로 다른 두 점 $q, q^{\prime}$으로 이루어진 순서쌍 $(p, q, q^{\prime})$ 가운데 세 점이 일직선 상에 있는 것들의 모임으로 정의하자. 이제, $|S|$의 상한과 하한을 구해볼 것이다. 편의상, ..

수학/이산수학 2018. 2. 3. 23:00
2N개의 점들

문제. 평면 상에 어느 세 점도 일직선 상에 있지 않은 $2N$개의 점들이 있다. 이들 중 $N$개의 점은 빨간색, 나머지 $N$개의 점은 파란색으로 칠해져 있다고 한다. 빨간 점과 파란 점을 하나씩 짝지어 총 $N$개의 선분을 그으려 한다. 이 때, $N$개의 선분들이 서로 교차하지 않도록 하는 것이 가능함을 보여라. 풀이를 진행하기에 앞서, 그림의 퀄리티에 대한 양해를 부탁드립니다. 풀이 1. $N$에 대해 귀납법을 적용하자. $N=1$인 경우, 명확하다. $N=n-1$인 경우 성립한다고 가정하자.이제, $n$개의 빨간 점과 $n$개의 파란 점이 있다고 하자. 만약, 이들의 볼록껍질 상에 빨간 점과 파란 점이 모두 존재한다면, 인접한 빨간 점과 파란 점을 이어주면, 귀납 가설에 의해 증명이 종료된다...

수학/이산수학 2018. 1. 1. 21:57
그들 사이의 거리

문제. 평면 상에 놓인 $n$개의 점들로 구성된 집합 $A$가 있다. 다음을 증명하여라.$$ | \left \{ (a, b) \in A^2 : d(a, b) = 1 \right \} | \leq O(n^{3/2}) $$ 풀이.각각의 $a \in A$에 대하여 $a$로 부터 거리가 1인 점의 수를 $f(a)$로 정의하자. 그러면, 평면상에서 (서로 다른 두 점으로 부터) 거리가 모두 1인 점의 수가 많아야 2개라는 사실에 착안하여 다음의 부등식을 얻을 수 있다.$$ \sum_{a \in A} {f(a) \choose 2} \leq {n \choose 2} $$따라서,$$ \sum_{a \in A} f(a)^2 \leq n(n-1) + \sum_{a \in A} f(a)$$를 얻게 되고, 코시-슈바르츠 부등..

수학/이산수학 2017. 9. 18. 17:25
Erdős–Ko–Rado 정리

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)$을 택한 경우..

수학/이산수학 2017. 7. 29. 01:54
간단한 poset을 이용하는 문제

문제. 수직선 상에서 $n$개의 구간(interval) $I_1 , I_2 , \cdots , I_n$이 있는데, 그 가운데서 어떻게 $k$개를 뽑든지 교집합이 공집합이 아닌 2개의 구간이 존재한다고 한다. 이 때, $k-1$개의 실수들의 집합 $S$가 존재해서 모든 $1 \leq i \leq n$에 대하여 $I_i \cap S$가 공집합이 아니게 할 수 있음을 보여라. 풀이.먼저, 이 구간들 사이의 관계 $\prec$를 다음과 같이 정의하자: 두 구간 $I$, $J$에 대하여 $I \prec J$임은 $\forall x \in I , \forall y \in J, x < y$를 만족하는 것으로 정의하자. 문제의 조건으로 인해 우리는 길이가 $k$ 이상인 chain을 찾을 수 없다. 즉, maximal ..

수학/이산수학 2017. 7. 27. 06:18
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • 테셀레이션
  • 두 가지 조합기하 문제들
  • 제 1회 Uni-CODE 에디토리..
  • 연인 관계의 수에 대한 짧..
Total
24,299
Today
22
Yesterday
17

Blog is powered by Tistory / Designed by Tistory / Managed by Jongseo Lee