Ore's theorem은 그래프에 해밀턴 회로가 존재할 조건과 관련된 정리이다. Statement를 바로 쓰면 다음과 같다. \(n \ge 3\)개의 정점으로 구성된 단순그래프 \(G\)에서, 모든 비인접(non-adjacent) 정점 \(x, y\)에 대해 \(\deg x + \deg y \ge n\)이 성립하면, \(G\)에는 해밀턴 회로가 존재한다. 여담으로 좀 더 강한 조건인 Dirac's theorem (모든 정점의 차수가 \(n/2\) 이상)도 있는데, 딱히 Ore's theorem 증명에 비해 쉬운지는 잘 모르겠다. 스포일러 방지선 Step 1. \(G\) is connected 두 정점 \(x\), \(y\)가 이미 인접(adjacent)한 경우에는 상관이 없다. \(x\)와 \(y\)가..

PS에 적당한 시간을 할애하기 위해서, 트위치에서 어려운 문제를 푸는 방송을 시작했다. 방송을 할 때마다 Write-up을 써볼 생각이다. 처음으로 푼 문제는 JAG Spring Contest 2013 I번으로 출제된 The J-th Number이다. 켠왕을 걸 정도로 어려운 문제는 아니었던 것 같지만 11번 틀렸다(...) BOJ 문제 요약 \(N\)개의 빈 배열이 있는데, 여기에 \(M\)개의 삽입 쿼리를 먼저 수행한 뒤 \(Q\)개의 구간 쿼리에 답해야 한다. 삽입 쿼리 : \(a\)번 이상 \(b\)번 이하의 배열에 원소 \(v\)를 삽입한다. 구간 쿼리 : \(s\)번 이상 \(e\)번 이하의 모든 배열에서 \(j\)번째로 작은 수를 출력한다. 이 수가 존재함은 보장된다. 스포방지선 풀이 1. ..

통계학 과목 기말고사 범위에 대해 공부한 내용을 블로그로 옮기기로 한다. 모비율의 추정, 가설 검정 사실 "이산자료의 분석"이라고 하면 뭘 어떻게 분석한다는 건지 감이 1도 오지 않는다. 결국 이 단원에서 하는 모든 짓들은 모비율을 몰라서 생기는 일이라고 보면 된다. 어떤 확률사건(실업, 후보 선호)이 있을 때, 모비율은 곧 실업률, 후보 지지율과 같이 모집단 내에서 특정 속성 "P"를 가진 개체의 비율을 의미한다. 문자로는 \(p\)라고 쓰고, 당연히 모비율의 추정량은 \(\hat{p}\)라고 쓴다. 그럼 \(n\)개의 개체가 있을 때 속성 "P"를 가진 개체의 개수 \(X\)는 자연히 \(B(n,p)\)를 따른다. 따라서 \(\displaystyle \hat{p} = \frac{X}{n}\)은 기댓값..

문제 링크 Community Something appears to not have loaded correctly. artofproblemsolving.com 문제. \(n = p_{1}^{e_{1}}p_{2}^{e_{2}} \cdots p_{k}^{e_{k}}\)에 대해 \(\lambda(n)\)은 \((-1)^{e_1 + e_2 + \cdots e_k}\)로 정의된다. (Liouville's function) 다음을 증명하여라: (a) \(\lambda(n) = \lambda(n+1) = 1\)인 \(n\)이 무한히 많다. (b) \(\lambda(n) = \lambda(n+1) = -1\)인 \(n\)이 무한히 많다. 아이디어가 상당히 기초적이면서도 재밌다. 풀이. ...더보기 (a) 편의를 위해, ..

문제 링크 2019-03 Simple spectrum - KAIST Math Problem of the Week Suppose that \( T \) is an \( N \times N \) matrix \[ T = \begin{pmatrix} a_1 & b_1 & 0 & \cdots & 0 \\ b_1 & a_2 & b_2 & \ddots & \vdots \\ 0 & b_2 & a_3 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & … mathsci.kaist.ac.kr \(N \times N\) 실수 행렬 \(T\)가 다음과 같고, 모든 \(b_i > 0\)일 때 \(T\)는 서로 다른 \(N\)개의 eigenvalue를 가짐을 보여라. $$ T = \be..

문제 링크 2019-02 Simplification of an expression with factorials - KAIST Math Problem of the Week For any positive integers m and n, show that \[ C_{n,m} = \frac{(mn)!}{(m!)^n n!} \] is an integer. Recommend on Facebook Tweet about it Print for later Tell a friend Related mathsci.kaist.ac.kr POW라는 걸 믿을 수 없을 정도로 쉬운 문제가 나와버렸다. 스포방지 안할래... 문제. 모든 자연수 \(n,m\)에 대해, 다음이 정수임을 보여라. $$ C_{n,m} = \frac{(nm)!..