삼자선문제

이산 기하학에서 세 개의 선이 없는 문제는 n${\displaystyle }$× ${\displaystyle n}$ ${\displaystyle$ n$\times$ n$}$ $그리드$에 세 개의 점이 동일한 선에 놓이지 않도록 몇 개의 점을 배치할 수 있는지를 묻습니다.문제는 그리드와 정렬된 경사면뿐만 아니라 모든 경사면의 선에 관한 것입니다.그것은 1900년 헨리 두데니에 의해 소개 됐습니다.브라스, 모저, 파흐는 이를 "격자점에 ^[1]관한 가장 오래되고 광범위하게 연구된 기하학적 질문들 중 하나"라고 불렀습니다.

비둘기 구멍 원칙에 따라 격자 내 ${\displaystyle \mathrm{2n}}$+ ${\displaystyle 1}${\$displaystyle$ 2n + 1}개의$$ {\displaystyle $2n$+$1}$개의 점은 3개 이상의 점으로 이루어진 행을 $포함$하기 $때문$에$$최대 ${\displaystyle \mathrm{2n}}$ {\$displaystyle$2n$$}개의 점을 배치할 수 있습니다.${\displaystyle \mathrm{최대}}$ 46 ${\displaystyle$ 46$\}$까지의 n$${\$displaystyle$ n$}$에 대해$$ ${\displaystyle \mathrm{2n}}${\$displaystyle 2n}$ $포인트$로 문제를 해결할 수 있지만, 크기가 큰 그리드에는 ${\displaystyle \mathrm{2n}}${\$displaystyle 2n}$ 포인트$$ $미만$이 배치될 수 있다고 추측됩니다.알려진 방법은 임의 크기의 그리드에 선형으로 많은 점을 배치할 수 있지만, 이러한 방법 중 가장 좋은 방법은 ${\displaystyle \mathrm{2n}}${\$displaystyle 2n$이 아닌 ${\displaystyle \mathrm{3n}/2\mathrm{}}$ ${\displaystyle 3n/2}$점보다$$ $약간{\displaystyle \mathrm{}}$ 적습니다.

격자가 아닌 점들의 집합 중에서 세 개가 일렬로 있지 않은 점들을 찾는 것과 관련된 몇 가지 문제들도 연구되어 왔습니다.비록 레크리에이션 수학에서 비롯되었지만, 세 줄이 아닌 문제는 그래프 그리기와 헤이브론 삼각형 문제에 적용됩니다.

소규모 인스턴스

이 문제는 헨리 두데니가 1900년에 처음 제기한 것인데, 레크리에이션 수학의 퍼즐로서 체스판의 16개의 전당포를 보드 위에 놓고 세 개가 ^[2]일렬로 있지 않도록 하는 용어로 표현되었습니다.이것은 정확히 n${\displaystyle }$= ${\displaystyle 8}${\$displaystyle n$= 8}인 경우의 세 줄 안의 문제입니다. 이후 버전의 퍼즐에서 두데니는 문제를 수정하여 두 폰이 정사각형 d4와 e5 위에 있고 보드 중앙에서 서로 공격하는 해를 요청함으로써 해결책을 독특하게 만들었습니다.

많은 저자들이 n ${\displaystyle$ n$\}$^[5]의 작은 값에 대해 이 문제에 대한 해결책을 발표했으며, 1998년까지 ${\displaystyle n}$ ${\displaystyle 2n}$개의$$ 점을 n${\displaystyle }$× ${\displaystyle n}${\$displaystyle$ n$}$$개$의 그리드에 배치할 수 $있으며{\displaystyle \mathrm{}}$, 최대 46개의$$n개의 {\$displaystyle$ $n$$$}개까지의 모든 $n개{\displaystyle }$ 및 일부 큰 ^[6]값에 대해 3개가 없는 것으로 알려졌습니다.n$$= ${\displaystyle 2}${\$displaystyle$ n$$= $2$부터 시작하는 n {\$displaystyle$ $n$}의 작은 ${\displaystyle 값}$에 대해 2$n$ {\$displaystyle$ 2n$}$ 포인트를 $가진$ 솔루션의 수는 다음과 같습니다.

반사 및 회전 하에서 ${\displaystyle \mathrm{2n}}$ ${\displaystyle 2n}$을 갖는 솔루션의 등가 클래스 수는 다음과 같습니다.

상한 및 하한

n ${\displaystyle$ n$\}$의 함수로 배치할 수 있는 정확한 점 수는 알 수 없습니다.그러나 증명된 경계와 추측된 경계 모두 이 수를 n$${\$displaystyle$ n$\}$에 비례하는 범위 내로 제한합니다.

일반배치방법

Roth(1951)가 발표한 Paul Erdős의 해결책은$$n {\$displaystyle$n}이 $소수$일 때$,$ n {\$displaystyle$ n$}$개의 격자점${\displaystyle \mathrm{집합}}$(i$,i^{$2$}$ $mod{\displaystyle }$n $){\displaystyle$$$n$\},$ 즉{\$displaystyle$0\$leq i<$n의 0 때, 세 개의 공선점이 포함되지 않는다는 관찰에 기초합니다.n ${\displaystyle$ n$}$이(가) 소수가 아닐 $때{\displaystyle }$${\displaystyle ,}$ $n{\displaystyle }$ × ${\displaystyle n}${\$displaystyle$p\$times$ p$}$ $그리드$에 포함된${\displaystyle }$p × ${\displaystyle p}${\$displaystyle$ p$\$$times$p} 그리드에$$ 대해 이 구성을 수행할 수 있습니다. $여기$서 p$${\$displaystyle$ p$}$는 $최대{\displaystyle }$ n$${\$displaystyle$ n$\}$의 가장 큰 소수입니다. 연속된 소수들 사이의 간격이 소수들 자체보다 훨씬 작기 $때문$에$,$ p {\$d$$isplaystyle$ p$}$은(는) 항상 n$${\$displaystyle$ n$\}$에 가깝기 때문에 이 메서드를 사용하여 n ×${\displaystyle }$${\displaystyle n}$ {\$displaystyle$ $n\$$times$ n$$$}$의 점을 공선으로 ^[7]세 개의 점이 없는${\displaystyle }$n${\displaystyle }$× n ${\displaystyle$ n$(n$$)}$개의$$ 그리드에 $배치$할 수 있습니다.

Erdős의 경계는 이후에 개선되었습니다. Hall et al. (1982)에 따르면${\displaystyle ,}$ n /$$ {\$displaystyle n/$2}가 $소수$일 때, ${\displaystyle \mathrm{쌍곡선}}$ y = ${\displaystyle k}$ ${\displaystyle$ xy=$k$$mod{\displaystyle }$n / 2$${\$displaystyle$ n$/2$})의 여러 복사본에 점을 배치하여 3${\displaystyle }$(${\displaystyle n}$-${\displaystyle 2)}$ / ${\displaystyle 2}${\$displaystyle$ 3$(n$ - 2$)/2$$}$ $점$으로 해를 얻을 수 있으며, $여기$서 k ${\displaystyle$ k$}$를 선택할 수 있습니다.임의로 $0$이 아닌${\displaystyle mod\mathrm{}}$ n$$/ 2 {\$displaystyle$ n$/$$2$}입니다. 다시 말해, $n$ {\$displaystyle$ n$}$의${\displaystyle 경우\mathrm{}}$ n$$/ 2 {\$displaystyle$ n$/2$} $근처$의 소수점에 대해 이 구성을 수행하여 ${\displaystyle \frac{32}{}n}$ -${\displaystyle o}$(^[8]${\displaystyle n)}${\$tfrac {3}{2}$n - o($n)$ 포인트를 $갖는{\displaystyle \frac{\mathrm{}}{}}$ 해를 얻을 수 있습니다.

상한

$최대{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{2n}}${\$displaystyle 2n}$개의$$ 점은 크기 $n{\displaystyle }$ ${\displaystyle$ n$\}$의 그리드에 배치될 수 있습니다. 더 많은 점이 배치되면 비둘기 구멍 원칙에 따라 그 중 일부는 모두 그리드의 동일한 수평 라인에 놓이게 됩니다.n ${\displaystyle \le }$ ${\displaystyle 46}${\$displaystyle$ n$\leq$ 46$\}$의 경우 이 사소한 경계는 엄격한 ^[3]것으로 알려져 있습니다.

추측한계

작은 그리드에는 ${\displaystyle \mathrm{정확히}}$2n개의 {\$displaystyle 2n}$개의$$ 포인트를 배치할 수 있지만, Guy & Kelly(1968)는 큰 그리드의 경우 배치할 수 있는 포인트 수에 대한 상한이 상당히 작다고 추측했습니다.더 정확하게 말하면, 그들은 배치할 수 있는 점의 수가 기껏해야 ${\displaystyle \mathrm{cn}}$ {\$displaystylecn$보다^[9] 큰 하위 선형 양일 것이라고 추측했습니다$.$

이 추측으로 이어지는 휴리스틱 추론의 오류가 발견된 후, 가이는 오류를 수정하고 ${\displaystyle \mathrm{cn}}$ ${\displaystyle$ cn$}$보다^[10] 하위 선형 이상을 더 잘 할 수 없다는 강력한 추측을 했습니다.

적용들

그래프 그리기에서 특정 종류의 퇴행을 피하기 위해 세 줄이 아닌 문제에 대한 해결책을 사용할 수 있습니다.이 문제는 주어진 그래프의 꼭짓점을 평면의 정수 좌표에 배치하고 그래프의 가장자리를 직선 세그먼트로 그리는 것을 포함합니다.유틸리티 그래프와 같은 특정 그래프의 경우 모서리 쌍 사이의 교차는 피할 수 없지만 두 개의 다른 꼭짓점을 통해 꼭짓점이 모서리에 놓이게 하는 배치는 피해야 합니다.꼭짓점이 세 개의 줄이 없는 상태로 배치될 때는 선분뿐만 아니라 두 개의 꼭짓점을 통과하는 전체 선이 다른 ^[11]꼭짓점으로부터 자유롭기 때문에 이런 종류의 문제가 발생할 수 없습니다.세 줄이 아닌 문제가 선형적으로 많은 점을 갖는 해를 갖는다는 것은 모든 그래프, 심지어 완전한 그래프도 정점의 수에서 이차적인 면적을 갖는 격자를 사용하여 원하지 않는 정점-가장자리 사건 없이 그릴 수 있다는 것을 의미하는 그래프 그리기 용어로 변환될 수 있습니다.완전한 그래프의 경우 2차 면적 미만의 그림은 불가능합니다.완전한 그래프는 또한 그래프 색상에 선형 개수의 색상이 필요하지만, 더 적은 색상으로 채색할 수 있는 다른 그래프도 작은 그리드에 그릴 수 있습니다. 그래프가 n개의$${\$displaystyle$ n$}$개의$$ 정점을 $가지고{\displaystyle }$ k개의$${\$displaystyle$ k$}$개의$$ 색상으로 $채색$된 경우 ${\displaystyle \mathrm{nk}}$ ${\displaystyle$ nk$\}$$개$의 면적에 비례하는 그리드에 그릴 수 있습니다.완전한 그래프의 세 줄이 아닌 도면은 k = ${\displaystyle n}$ ${\displaystyle$ k =$n$인 이 결과의 특수한 경우입니다.

세 줄이 아닌 문제는 이산 기하학의 또 다른 문제인 하일브론 삼각형 문제에도 적용됩니다.이 문제에서는 격자에 제한되지 않고 단위 사각형의 어느 곳에나 n개의$${\$displaystyle$ n$}$개의$$ 점을 $배치$해야 합니다.배치의 목표는 작은 면적의 삼각형을 피하는 것이며, 더 구체적으로는 세 개의 점으로 구성된 가장 작은 삼각형의 면적을 최대화하는 것입니다.예를 들어, 세 점이 일렬로 있는 배치는 이 기준에 의해 매우 좋지 않을 것입니다. 이 세 점은 면적이 0인 축퇴 삼각형을 형성하기 때문입니다.반면에 점이 단위 사각형 내의 변 길이$$ε {\$displaystyle \varepsilon}$의 격자에 배치될 수 있고, 한 줄에 세 개가 없다면, 픽의 정리에 의해 모든 삼각형은 격자 사각형의 절반인 ε 2${\displaystyle {}^{}2}$ ${\displaystyle \varepsilon ^{2}/2$의 면적을 갖게 됩니다.따라서 세 줄이 아닌 문제의 인스턴스를 해결한 다음 정수 그리드를 단위 사각형 내에 맞게 축소하면 가장 작은 삼각형의 면적이${\displaystyle }\Omega {\displaystyle \mathrm{}}$ (${\displaystyle 1}$/ ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}${\$displaystyle \Omega (1$/ $n^{2$인 Heilbronn 삼각형 문제에 대한 해결책이 생성됩니다.이 응용 프로그램은 폴 에르도스가 세 줄이 ^[13]아닌 문제에 대한 해결책을 찾도록 한 동기가 되었습니다.1951년부터 1982년까지 Heilbronn 삼각형 문제에 대해 알려진 최고의 영역 하한으로 남아있었는데, 이때는 no-three in line ^[14]문제에 기초하지 않은 구성을 사용하여 로그 인자에 의해 개선되었습니다.

일반화 및 변형

일반위치 부분집합

계산 기하학에서, 세 개의 선이 없는 점들의 유한 집합은 일반적인 위치에 있다고 합니다.이 용어에서, 3-in-line 문제는 일반 위치에 있는 그리드의 가장 큰 부분 집합을 추구하지만, 연구자들은 또한 다른 비-그리드 점 집합의 가장 큰 일반 위치 부분 집합을 찾는 문제를 고려했습니다.특정 입력 집합에 대해 이 부분 집합을 찾는 것은 NP-hard이며 일정 인자 내에서 크기를 근사하기는 어렵습니다. 이러한 근사 결과의 경도는 문제가 APX-hard라고 요약됩니다.가장 큰 부분 집합의 $크기$가 k$${\$displaystyle$ k$\}$인 경우, 선택한 ^[15]점의 쌍을 통해 나머지 모든 점이 선 위에 놓일 때까지 한 번에 하나씩 점을 선택하는 그리디 알고리즘에 의해 비 상수 $근사비{\displaystyle }$O(${\displaystyle k)}${\$displaystyle$ O$({\sqrt {k}})}$의 해를 얻을 수 있습니다.

알고리즘이 입력 크기뿐만 아니라 입력의 다른 매개 변수 측면에서 분석되는 매개 변수화된 복잡성을 사용하여 정확한 최적 솔루션을 찾기 위한 알고리즘의 실행 시간을 보다 세밀하게 이해할 수 있습니다.이 경우, 가장 큰 일반 위치 부분 집합이 $크기{\displaystyle }$ k$${\$displaystyle$ k$\}$인 입력의 경우, k ${\displaystyle$ k$}$의 $지수{\displaystyle }$ 함수에 입력 $크기{\displaystyle }$ n$${\$displaystyle$ n$\}$의 다항식을 곱한$$ 시간 내에 찾을 수 있으며, 다항식의 지수는 k$${\$displaystyle$ k$\}$에 $의존$하지 않습니다.이러한 종류의 시간 경계 문제를 고정 매개 변수 처리 가능이라고 합니다.^[16]

ℓ =$$( $\sqrt{S}$) ${\textstyle$$\ell$ $}$ 점과 ℓ =$$$O ({\sqrt${ S$}}$ 점이$$있는 $점$ 집합 S ${\displaystyle$ S$}$에 대해 ℓ =$$( $\sqrt{S}$) ${\textstyle \ell$ = O$({\sqrt${ S$}})$에$$거의 비례하는 크기의 일반 위치 부분 집합이 존재합니다.그리드 예제는 이 경계를 크게 ^[17]개선할 수 없음을 보여줍니다.이러한 큰 일반 위치 부분 집합의 존재 증명은 엔트로피 ^[15]압축으로 알려진 알고리듬 기술을 사용하여 존재 경계와 일치하는 크기의 S$${\$displaystyle$ S$\}$의 일반 위치 부분 집합을 찾기 위한 다항 시간 알고리듬으로 변환될 수 있습니다.

욕심쟁이 배치

마틴 가드너는 Adena, Holton & Kelly(1974)의 제안을 반복하면서 확장할 수 없는 ${\displaystyle n}$×n ${\displaystyle$ n$\times$ n$}$ $그리드$의 가장 작은 부분 집합을 요청했습니다. 한 줄에 세 개의 점이 없지만 모든 적절한 슈퍼 집합에는 세 개의 점이 있습니다.마찬가지로,^[3] 이것은 노쓰리 인라인 문제가 고착될 때까지 한 번에 하나씩 점을 배치하여 해결하려는 탐욕스러운 알고리즘에 의해 생성될 수 있는 가장 작은 집합입니다.축-평행 및 대각선만 고려할 경우, 이러한 모든 집합에는 최소${\displaystyle }$n - ${\displaystyle 1}${\$displaystyle n-1}$의 ^[18]점이 있습니다.그러나 모든 선이 고려되는 문제의 버전에 대해서는 알려진 것이 거의 없습니다. 모든 그리디 배치에는 막히기 전에 최소${\displaystyle }\Omega {\displaystyle \mathrm{}}$ (${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {/3\mathrm{}}^{}}${\$displaystyle \Omega(n^{2/3})}$개의$$ 포인트가 포함되지만 $사소한{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{2n}}${\$displaystyle 2n}$개의$$ 상한보다 더 나은 것은 없습니다.^[19]

고차원

Pór & Wood(2007)는 3차원 격자의 점들의 비공선 집합을 고려했습니다.그들은 세 점이 일직선을 이루지 $않는{\displaystyle }$n ×${\displaystyle n}$ × ${\displaystyle n}${\$displaystyle$ n$\times$n\$times$ n$}$ 격자의 최대 점 수가${\displaystyle }$Ω (${\displaystyle n^{}}$2)$${\$displaystyle \Theta (n^{2$임을 증명했습니다. $Erd$ő$s$의 2차원 구조와 유사하게 점 (${\displaystyle x,y}$, ${\displaystyle {x2}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {y2}^{}}${\$displaystyle$ $(x,y,$ x$^{2}+y^{$2$}$ $mod{\displaystyle }$p$)\},$$여기$서 p$${\$displaystyle$ p$}$는 3 mod ^[20]4에 소수로 대응됩니다.원래의 3행이 아닌 문제가 2차원 그래프 그리기에 사용될 수 있는 것처럼, 이 3차원 솔루션을 사용하여 3차원 그리드에 그래프를 그릴 수 있습니다.여기서 비공선성 조건은 꼭짓점이 인접하지 않은 모서리에 놓여서는 안 된다는 것을 의미하지만, ^[21]두 모서리가 교차하지 않는 더 강력한 요구 사항으로 작업하는 것이 일반적입니다.

훨씬 더 높은 차원에서 초구 근처의 점을 선택하여 얻은 세 개의 선이 없는 격자점 집합은 산술 ^[22]진행을 구성하는 세 개가 없는 정수 집합인 큰 세일럼-스펜서 집합을 찾는 데 사용되었습니다.그러나 원 근처의 점을 2차원으로 선택하는 동일한 아이디어를 사용하는 것은 잘 작동하지 않습니다. 이 방법은 세 개의 선이 없다는 요건을 충족하지만 너무 작은 볼록 다각형을 형성하는 점을 찾습니다.$n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ n$\times$ n$}$ 그리드에$$ 정점이 있는 가장 큰 볼록 다각형의${\displaystyle {}^{}}$은 ${\displaystyle {O\mathrm{}(n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$3$)$ {\$displaystyle O(n^{2/3$})}^[23]$개뿐$입니다.캡 세트 문제는 ^[24]정수가 아닌 유한 필드 위의 벡터 공간으로 기반하고 고차원적인 공간에서 세 줄이 아닌 문제와 유사한 문제에 관한 것입니다.

고차원에 대한 또 다른 일반화는 $3차원{\displaystyle }$N ×${\displaystyle N}$ × ${\displaystyle N}$ × N ${\displaystyle$ N$\times$ N$\times$ N$}$ 그리드에서$$ 가능한 한 많은 점을 찾아 동일한 평면에 4개가 있지 않도록 하는 것입니다.이 순서는 5,8,10,13,16,...OEIS: N = 2, 3, 4 등용 A280537

토러스

이 문제에 대한 또 다른 변형은 토러스의 왼쪽이 오른쪽으로 연결되고 위쪽이 아래쪽으로 연결되는 주기적인 경계 조건을 사용하여 그리드를 이산 토러스로 변환하는 것입니다.이는 격자를 통해 비스듬한 선에 더 많은 점을 통해 더 긴 선으로 연결되는 효과가 있으며, 따라서 각 선에서 최대 2개로 점을 선택하는 것을 더 어렵게 만듭니다.이러한 확장된 선은 또한 유클리드 평면의 무한 격자를 통해 토러스의 차원을 모듈로 하는 정상 선으로 해석될 수 있습니다.$m{\displaystyle }$× ${\displaystyle n}$ ${\displaystyle$ m$\times$ n$}$ 그리드를$$ 기반으로 하는 토러스의 경우, 세 개의 선이 없는 점을 선택할 수 있는 최대 ${\displaystyle 수}$는 최대 $n$) {\$displaystyle$ 2$\gcd(m,n$^[25]입니다. 두 차원이 동일하고 prime일 때,선형 개수의 공선 ^[26]삼중을 형성하지 않고는 각 행과 열에 정확히 하나의 점을 배치할 수 없습니다.문제의 고차원 토러스 버전도 ^[27]연구되었습니다.

참고 항목

• 같은 행, 열 또는 대각선에 두 개가 없는 격자에 점을 배치하는 8개의 퀸 퍼즐

메모들

참고문헌

외부 링크

• Flammenkamp, Achim. "The No-Three-in-Line Problem".
• Weisstein, Eric W. "No-Three-in-a-Line-Problem". MathWorld.