램지 이론: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Monsieur Lichan (토론 | 기여) 편집 요약 없음 |
Monsieur Lichan (토론 | 기여) 잔글편집 요약 없음 |
||
4번째 줄:
램지 이론의 실마리가 되는 두 정리로는 다음을 들 수 있다:
*[[판데르바르던의 정리]](Van der Waerden's theorem): 어떠한 자연수 c, n이 주어지더라도, 연속하는 V개의 자연수를 c개의 색으로 어떻게 칠하더라도 한가지 색으로 이루어진 길이 n의 [[등차수열]]이 존재하도록 하는 자연수 V가 존재한다.
*[[헤일스-주에트 정리]](Hales-Jewett theorem): 어떠한 자연수 c, n이 주어지더라도 H차원 n×n×...×n 초입방체의 셀들을 c개의 색으로 나누어칠할 때, 속해있는 모든 셀이 같은 색으로 칠해진 길이 n의 줄이 최소 1개는 존재하도록 하는 자연수 H가 존재한다. 즉, 여럿이 하는 n렬 [[틱택토]] 게임은 충분히 큰 차원에서 플레이한다면 n이 아무리 크거나 플레이어가 아무리 많아도 절대 무승부로 끝나지 않는다. Hales-Jewett 정리는 Van der Waerden's 정리를 함의한다.
== 같이 보기 ==
| |||