해피 엔딩 문제는 평면 위의 일반적인 위치에 있는 점들의 집합에서 볼록 다각형을 이루는 부분 집합을 찾는 문제이다. 1935년 에르되시와 세케레스는 충분히 큰 점들의 집합이 볼록 N각형을 이루는 부분집합을 갖는다는 것을 증명했고, f(N)을 볼록 N각형을 포함하는 최소 점의 개수로 정의했다. N=3, 4, 5에 대한 f(N)의 값은 알려져 있으며, N>6인 경우 f(N)의 값은 알려져 있지 않다. 에르되시-세케레스는 f(N) = 1 + 2^(N - 2)라는 추측을 제시했지만, 2016년에는 f(N) ≤ 2^(N + o(N))임이 증명되었다. 또한, 빈 볼록 다각형의 존재에 대한 문제도 연구되었으며, 빈 육각형의 존재는 증명되었지만, 빈 칠각형을 포함하지 않는 점 집합이 존재한다.
더 읽어볼만한 페이지
이산기하학 - 최근접 이웃 탐색 최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다.
이산기하학 - 보로노이 다이어그램 보로노이 다이어그램은 거리 공간에서 점 집합을 기반으로 공간을 분할하는 기하학적 구조이며, 각 점까지의 거리가 가장 가까운 공간 영역인 보로노이 셀들의 집합을 의미하고 다양한 분야에서 활용된다.
램지 이론 - 램지의 정리 램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
램지 이론 - 비둘기집 원리 비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
에르되시 팔 - 에르되시 수 에르되시 수는 수학자 폴 에르되시와 공동 연구를 통해 연결된 정도를 나타내는 척도로, 에르되시 본인은 0이며 공동 연구자는 1, 그 외 연결되는 사람들은 숫자가 증가하는 방식으로 정의되고 학문적 영향력을 가늠하는 척도로 사용된다.
에르되시 팔 - 에르되시-그레이엄 추측 에르되시-그레이엄 추측은 n보다 크거나 같은 두 정수의 최소공배수가 2n보다 작거나 같게 하는 상수 c가 존재한다는 추측으로, 어니스트 크루트에 의해 증명되었으며, 관련된 상수 c의 하계에 대한 연구가 진행되었다.
해피 엔딩 문제
정리 정보
이름
해피 엔딩 문제
로마자 표기
Haepi ending munje
관련 분야
조합론, 기하학
내용
평면 위의 점들의 배열에서 특정 조건을 만족하는 부분집합의 존재성을 증명하는 문제
관련 인물
에르되시 팔, 세케레시 죄르지
정리 내용
내용
평면 위에서 일반 위치에 있는 임의의 점 다섯 개의 집합은 볼록 사각형을 이루는 점 네 개의 부분집합을 갖는다.
2. 더 큰 다각형
Erdős영어와 세케레스는 평면 위에서 일반적인 위치에 있는 점들의 집합이 충분히 클 때, 그 부분집합으로 볼록 N각형을 항상 만들 수 있다는 정리를 증명했다. 이를 에르되시-세케레스 정리라고 한다.
이와 관련하여, 평면 위의 일반 위치에 있는 점 M개의 집합이 볼록 N각형을 포함해야 하는 최소 M을 f(N)으로 표시한다.
f(3) = 3이다. (자명)
f(4) = 5 [16]
f(5) = 9 [17] (볼록 오각형이 없는 8개의 점 집합은 볼록 오각형이 없는 8개의 점 집합과 같다.)
f(6) = 17 [18]
N > 6인 모든 경우, f(N)의 값은 알려져 있지 않다.
에르되시-세케레스 정리에 대한 증명은 수열의 단조 부분 수열에 대한 에르되시-세케레스 정리를 증명하는 것과 같은 논문에 실렸다.[19]
에르되시와 세케레스는 N = 3, 4, 5에 대해 알려진 f(N) 값을 기반으로, 원래 논문에서 모든 N ≥ 3에 대해 f(N) = 1 + 2N - 2이라는 추측을 제시했다. 하지만, 이후에 명백한 예를 구성하여 f(N) ≥ 1 + 2N - 2임을 증명했다.[19]
N ≥ 7일 때 알려진 가장 좋은 상한은 f(N) ≤ 2N + o(N)이다.[20]
2. 1. 에르되시-세케레스 정리
1935년 에르되시와 세케레스는 다음과 같은 일반화된 명제를 증명했다.[19]
: 임의의 양의 정수 N에 대해, 일반적인 위치에 있는 평면상의 충분히 큰 유한 점 집합은 볼록 다각형의 꼭짓점을 형성하는 N개의 점의 부분 집합을 갖는다.
이 증명은 수열의 단조 부분 수열에 대한 에르되시-세케레스 정리와 같은 논문에 실렸다.[19]
''f''(''N'')을 일반적인 위치에 있는 임의의 M개의 점 집합이 반드시 볼록 N각형을 포함해야 하는 최소 M으로 정의하면, 다음과 같은 사실이 알려져 있다.
N
f(N)
설명
3
3
자명하다.
4
5
[16]
5
9
[17] 볼록 오각형이 없는 8개의 점 집합이 존재하므로, f(5) > 8 이다. 증명의 어려운 부분은 일반적인 위치에 있는 모든 9개의 점 집합이 볼록 오각형의 꼭짓점을 포함한다는 것을 보이는 것이다.
6
17
[18]
N > 6인 경우 ''f''(''N'')의 값은 알려져 있지 않다. 에르되시와 세케레스(1935)의 결과에 따르면, 모든 양의 정수 N에 대해 ''f''(''N'')는 유한하다.
에르되시와 세케레스는 N = 3, 4, 5에 대해 알려진 ''f''(''N'') 값을 기반으로 원래 논문에서 모든 N ≥ 3에 대해 f(N) = 1 + 2N - 2 이라고 추측했다. 그들은 나중에 명백한 예를 구성하여 f(N) ≥ 1 + 2N - 2임을 증명했다.[19]
N ≥ 7일 때 알려진 가장 좋은 상한은 f(N) ≤ 2N + o(N)이다.[20]
2. 2. 에르되시-세케레스 추측
1935년 에르되시와 세케레스는 원래 논문에서 모든 에 대해 라는 추측을 제시했다.[19] 이들은 나중에 명백한 예를 들어 임을 증명했다.[6] 일 때 알려진 가장 좋은 상한은 이다.[20]
일반 위치에 있는 충분히 큰 점 집합에서 다른 점을 포함하지 않는 "빈" 볼록 다각형이 존재하는지에 대한 문제를 다룬다.
해피 엔딩 문제에 대한 원래 해를 적용하면, 일반 위치에 있는 5개의 점은 빈 볼록 사각형을 가지며, 10개의 점은 빈 볼록 오각형을 가진다는 것을 보일 수 있다.[21] 그러나 빈 볼록 칠각형을 포함하지 않는 충분히 큰 일반 위치에 있는 점들의 집합이 존재한다.[22]
빈 육각형의 존재에 대한 문제는 오랫동안 열려 있었지만, 2007년과 2008년에 각각 니콜라스(Nicolás)와 게르켄(Gerken)이 증명하였다.
3. 1. 빈 볼록 사각형과 오각형
일반 위치에 있는 점들의 충분히 큰 집합에서, 다른 점을 포함하지 않는 "빈" 볼록 사각형이나 오각형 등이 존재하는지에 대한 질문을 할 수 있다. 해피 엔딩 문제에 대한 원래의 해는 일반 위치에 있는 5개의 점이 빈 볼록 사각형을 가지며, 일반 위치에 있는 10개의 점은 빈 볼록 오각형을 가진다는 것을 보여준다.[21] 그러나 빈 볼록 칠각형을 포함하지 않는 충분히 큰 일반 위치에 있는 점들의 집합이 존재한다.[22]
3. 2. 빈 볼록 육각형
일반 위치에 있는 점들의 충분히 큰 집합에서 다른 점을 포함하지 않는 "빈" 볼록 육각형의 존재에 대한 문제는 오랫동안 미해결 상태였다. 그러나 2007년 니콜라스(Nicolás)와 2008년 게르켄(Gerken)이 임의의 충분히 큰 일반 위치에 있는 점들의 집합은 빈 볼록 육각형을 포함한다는 것을 증명했다.[21] 게르켄은 필요한 점의 수가 ''f''(9) 이하임을 보였고, 니콜라스는 ''f''(25) 이하임을 보였다. 2008년 발터(Valtr)는 게르켄의 증명을 단순화했지만, 더 많은 점(''f''(15))을 요구했다.[23]
최소 30개의 점이 필요한데, 빈 볼록 육각형이 없는 일반 위치의 점 29개의 집합이 존재하기 때문이다.[23] 2024년에 Heule과 Scheucher는 SAT 솔빙 접근 방식을 사용하여 일반 위치에 있는 30개의 점 집합이 실제로 빈 육각형을 포함한다는 것을 보여주며 이 문제를 해결했다.
3. 3. 빈 볼록 칠각형
일반 위치에 있는 점들의 충분히 큰 집합에서 다른 점을 포함하지 않는 "빈" 볼록 사각형, 오각형 등이 존재하는지에 대한 질문을 할 수 있다. 해피 엔딩 문제에 대한 원래의 해는 일반 위치에 있는 5개의 점이 비어 있는 볼록 사변형을 가지며, 일반 위치에 있는 점 10개의 집합이 비어 있는 볼록 오각형을 갖는다는 것을 나타내도록 적용될 수 있다.[21] 그러나 빈 볼록 칠각형을 포함하지 않는 충분히 큰 일반 위치에 있는 점들의 집합이 존재한다.[22]
4. 관련 문제
이 문제는 완전 그래프의 직선 그래프 그리기에서 교차 수를 최소화하는 문제, 고차원 유클리드 공간에서 점 집합에 관한 문제 등과 관련이 있다. 이 문제들은 그래프 이론, 볼록 다포체 등과 연결된다.[24][25][26]
4. 1. 교차수 최소화 문제
볼록 사각형의 수를 최소화하는 ''n''개의 점 집합을 찾는 문제는 완전 그래프의 직선 그래프 그리기에서 교차 수를 최소화하는 것과 같다.[24] 사각형의 수는 ''n''의 네제곱에 비례하지만 정확한 상수는 알려져 있지 않다.[11]
4. 2. 고차원 공간으로의 확장
고차원 유클리드 공간에서 충분히 큰 점 집합은 차원보다 큰 임의의 k에 대해 볼록 다포체의 꼭짓점을 형성하는 k개의 점 부분 집합을 가진다. 이는 고차원 점 집합을 임의의 2차원 부분 공간으로 투영함으로써, 충분히 큰 평면 점 집합에서 볼록 k각형이 존재함으로부터 바로 알 수 있다.[25] 그러나 볼록 위치에 있는 k개의 점을 찾는 데 필요한 점의 수는 평면에서보다 고차원에서 더 작을 수 있으며, 더 제약이 많은 부분 집합을 찾는 것이 가능하다. 특히, d차원에서 일반 위치에 있는 d+3개의 점은 순환 다포체의 꼭짓점을 형성하는 d+2개의 점 부분 집합을 갖는다.[25] 보다 일반적으로, 모든 k>d인 d 및 k에 대해, 일반 위치에 있는 m(k, d)개의 점 집합이 인접 다포체의 꼭짓점을 형성하는 ''k''개의 점 부분 집합을 갖도록 하는 수 m(k, d)가 존재한다.[26]
참조
[1]
뉴스
A world of teaching and numbers - times two
http://www.smh.com.a[...]
The Sydney Morning Herald
2005-11-07
[2]
문서
[3]
문서
[4]
논문
1935
[5]
논문
2006
[6]
논문
1961
[7]
논문
2016
[8]
논문
1978
[9]
논문
1983
[10]
논문
2003
[11]
논문
1994
[12]
서적
2003
[13]
서적
2003
[14]
문서
[15]
뉴스
A world of teaching and numbers - times two
http://www.smh.com.a[...]
The Sydney Morning Herald
2005-11-07
[16]
문서
[17]
논문
1935
[18]
논문
2006
[19]
논문
1961
[20]
논문
2016
[21]
논문
1978
[22]
논문
1983
[23]
논문
2003
[24]
논문
1994
[25]
서적
2003
[26]
서적
2003
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
