수학 2

완전제곱수 배열에서의 등차수열

완전제곱수 배열($1,4,9,16, ...$)에서 적당히 수를 뽑아서 등차수열을 만들 수 있을까? 유한한 수열의 예를 들면 $1^2$,$5^2$,$7^2$은 1,25,49로 항의 개수가 3개이고 공차가 24인 등차수열이다. 그렇다면 항의 개수가 무한한 수열은 어떨까? 답은 '만들 수 없다'이다. 이를 귀류법을 이용해 증명해보자. 먼저 $a_1^2,a_2^2,a_3^2$ 가 등차수열을 이룬다고 하자. ($a_1,a_2,a_3$는 임의의 증가하는 자연수 배열) 두 항 사이의 공차는 같아야 하므로 $a_2^2-a_1^2=a_3^2-a_2^2$ $(a_2-a_1)(a_2+a_1)=(a_3-a_2)(a_3+a_2)$ 이때, $a_2+a_1a_3-a_2$가 성립한다. 이제 $a_1^2,a_2^2,a_3^2,\dot..

수학 2021.10.30

채색다항식

-그래프 정점(vertex) 집합과 간선(edge) 집합으로 이루어진 수학적 구조 -채색 그래프에서 같은 간선을 공유하는 정점을 서로 다른 색으로 칠하는 것 -그래프 $G$의 채색다항식 $=C_k(G)$ $k$개의 서로 다른 색을 사용하여 인접하는 두 정점은 같은 색이 아니게끔 그래프 $G$의 정점에 색칠하는 경우의 수 -채색수(chromatic number) $=\chi ( G)$ $C_k(G)\neq 0$ 을 만족하는 최소의 자연수 $k$값 ($C_k(G)$를 0에 가장 가깝게 하는 $k$) 영그래프 : 간선이 없는 그래프 영그래프의 채색다항식 $C_k(G)=K^n$ (인접한 정점이 없으므로 각 정점마다 k가지의 채색이 가능하다.) 영그래프의 채색수 $\chi ( G)$ $ = 1 $ (1가지의 색 ..

수학/조합 2021.07.18