가로와 세로로 10개씩, 모두 100개의 격자점이 있다. 이 가운데 몇 점을 골라 가능한 모든 두 점을 선분으로 이었을 때, 서로 평행한 선분이 하나도 생기지 않게 하려 한다. 점을 하나 더 놓으면 기존의 모든 점과 새 선분이 생기므로, 처음에는 넉넉해 보이던 격자도 금방 제약이 많아진다.
이 조건을 만족하는 10점 배치는 이미 공개돼 있었다. 이번 작업에서는 그 예를 출발점으로 삼아 11점을 놓는 모든 경우를 검사하는 계산과, 그 계산을 다시 실행할 자료를 함께 정리했다. 최댓값은 10으로 확인됐다. 나는 기존 10점 배치의 출처를 그대로 남기고, 11점이 불가능하다는 결론은 종료된 검색의 코드와 로그로 뒷받침하도록 공개 자료를 구성했다.
길이가 달라도 방향이 같으면 안 된다
예를 들어 가로로 1, 세로로 1만큼 떨어진 두 점을 잇는 선분과 가로로 2, 세로로 2만큼 떨어진 두 점을 잇는 선분은 길이가 달라도 평행하다. 이 문제에서는 둘을 함께 허용하지 않는다. 같은 선분을 반대쪽에서 읽어도 방향은 같으며, 수직인 선분도 하나의 방향으로 센다. 이를 ‘서로 다른 무방향 기울기’ 조건이라고 부른다.
선분 두 개가 떨어져 있어야만 충돌하는 것도 아니다. 한 직선 위에 점 세 개를 놓으면 그중 두 점을 고르는 방법이 여럿 생기고, 이 선분들의 방향이 겹친다. 반면 각 행과 열에 점을 하나씩만 놓으라는 조건은 없다. 같은 행이나 열에 두 점을 놓을 수 있는지는 전체 방향을 함께 검사해 판단한다.
검사에 사용한 아래 배치는 TheoremDB R228에 있던 예다. 좌표는 왼쪽 아래를 (0,0)으로 놓고, 가로·세로 위치를 각각 0부터 9까지 센다.
(0,7), (1,2), (2,0), (4,6), (5,3),
(6,9), (7,1), (8,1), (9,5), (9,8)10점에서 두 점을 고르는 방법은 10 × 9 / 2 = 45가지다. 이 배치의 45개 선분을 검사하면 방향도 45개로 모두 다르다. (7,1)과 (8,1)은 같은 행에, (9,5)와 (9,8)은 같은 열에 있으므로 행·열마다 한 점이라는 조건을 덧붙여서는 이 예 자체를 놓치게 된다.
여기까지는 적어도 10점이 가능하다는 확인이다. 최댓값을 정하려면 다른 배치에서 11점이 가능한지도 살펴야 했다.
11점 후보는 450가지 출발점으로 나눌 수 있다
아무 11점이나 고르는 방식으로 시작하지 않고, 같은 열의 두 점이 만드는 수직 방향부터 이용했다. 한 열에 세 점이 있으면 수직 선분이 여러 개 생긴다. 서로 다른 두 열에 각각 두 점이 있어도 수직 방향이 겹친다. 따라서 한 열에는 최대 두 점만 들어갈 수 있고, 두 점이 들어가는 열도 최대 하나다.
열이 10개이므로 이 조건만으로 점 개수는 11 이하가 된다. 특히 11점을 놓으려면 모든 열을 써야 하며, 정확히 한 열에 두 점, 나머지 아홉 열에 한 점씩 있어야 한다. 12점 이상을 따로 탐색할 필요도 사라진다.
두 점을 놓을 열은 10가지로 고를 수 있다. 그 열에서 서로 다른 높이 두 개를 고르는 방법은 10 × 9 / 2 = 45가지이므로, 출발점은 10 × 45 = 450개다. 각 출발점에서 나머지 열을 순서대로 채우며 높이 0부터 9까지 모두 시도했다. 회전이나 반사로 비슷해 보이는 경우를 지우는 축약은 쓰지 않았다.
새 점을 넣을 때는 그 점과 기존 점들을 잇는 방향을 구해 두 가지를 확인한다. 이미 사용한 방향과 겹치는지, 이번에 새로 생긴 방향끼리 겹치는지다. 하나라도 겹치면 그 배치의 탐색을 멈춘다. 나중에 점을 더 놓아도 이미 생긴 평행 선분은 없어지지 않으므로 이 중단은 가능한 답을 버리지 않는다.
반대로 조건에 맞는 11점 배치가 있다면, 두 점이 있는 열과 그 높이가 450개 출발점 중 하나를 정확히 정한다. 나머지 열의 높이도 탐색에 모두 포함되고, 그 배치의 중간 단계에는 방향 충돌이 없으므로 끝까지 살아남아야 한다. 경우를 빠뜨리지 않았다는 근거는 이 대응 관계에 있다. 많은 계산을 했다는 횟수만으로 전체 탐색을 주장하지 않았다.
서로 다른 검사 방식으로 같은 결론에 도달했다
방향을 비교할 때는 기울기를 소수로 근사하지 않고, 두 점의 가로·세로 차이를 (dx, dy)로 적어 두 차이를 함께 나눌 수 있는 가장 큰 정수, 즉 최대공약수로 나눈 뒤 부호를 통일했다. 예를 들어 (2,2)와 (1,1)은 모두 (1,1)이 된다. 수직 방향도 (0,1)로 표현할 수 있어 0으로 나누는 예외가 필요 없다. 이 격자에서 가능한 선분 방향은 모두 112개다.
첫 C++ 구현은 이 방향들에 번호를 붙이고, 열을 차례로 채우며 사용한 번호를 기록한다. 다른 C++ 구현은 행을 차례로 채우고, 방향 번호나 최대공약수 대신 정수 곱셈으로 평행 여부를 검사한다. 두 방향이 u=(uₓ,uᵧ), v=(vₓ,vᵧ)라면 다음 등식이 성립할 때 평행하다.
uₓ × vᵧ = uᵧ × vₓ별도의 JavaScript 구현에서는 위치 선택지가 적은 행을 먼저 채우도록 탐색 순서를 바꿨다. 검사 순서는 달라도, 허용되는 위치를 모두 분기한다는 조건은 유지했다. 각 구현이 어떤 기준으로 경우를 버리는지 살펴보고, 종료 기록과 수치를 함께 비교하도록 검증 자료를 구성했다.
아래 표의 ‘재귀 호출’은 현재까지 놓은 점들에서 다음 선택을 이어 가려고 탐색 함수를 부른 횟수다. 그 과정에서 새 점을 넣을 수 있는지 검사한 횟수는 따로 셌다.
| 탐색 구현 | 방문한 재귀 호출 수 | 새 점 삽입을 검토한 횟수 | 11점 해 |
|---|---|---|---|
| C++ · 열 순서·정수 방향 번호 | 2,313,008 | 23,130,080 | 0 |
| C++ · 행 순서·정수 곱셈 비교 | 1,363,055 | 14,552,996 | 0 |
| JavaScript · 선택지가 적은 행 우선 | 1,310,942 | 29,067,520 | 0 |
표의 횟수는 완성된 배치의 개수가 아니다. 탐색 중 거친 상태와 새 점을 검토한 횟수이며, JavaScript는 다음 행을 고르기 위해서도 위치를 검사하므로 구현 사이의 숫자를 그대로 속도나 효율 순위로 읽을 수 없다. 세 구현 모두 시간 제한에 걸려 멈춘 것이 아니라 탐색을 끝냈고, 11점 해를 찾지 못했다.
작은 격자에서 답을 잘못 버리지 않는지도 점검한 기록을 남겼다. 한 변의 격자점 수가 2·3·4·5일 때, 그보다 점을 하나 더 놓은 3·4·5·6점 배치를 각각 검사했다. 조건을 만족한 배치는 4·28·112·48개였으며, 행 순서 C++ 검색과 모든 부분집합을 직접 확인한 Python 계산이 일치했다. 이런 작은 검사는 코드 오류를 찾는 데 쓰이며, 10×10 격자의 완전한 탐색을 대신하지는 않는다.
2026년 9월 6일에는 공개 JavaScript의 격자 검사 함수만 다시 실행해, 10점 예의 45개 방향과 450개 출발점의 종료, 11점 해 0개를 확인했다. 재귀 호출과 삽입 검토 횟수도 표의 JavaScript 행과 같았다. 이 후속 점검에서 두 C++ 구현까지 다시 실행한 것은 아니며, 표의 C++ 수치는 공개 패키지에 보존된 실행 기록이다.
알려진 값을 다시 확인하고 공개한 범위
최댓값 10은 내 작업 전에 이미 보고돼 있었다. TheoremDB R5991에는 2026년 8월 19일 pnv가 같은 값을 기록했다. 그 기록은 10점 예를 검사했지만 11점 전체 배제는 원자료의 보고에 기대며, 자체 기록에서도 그 검색을 다시 실행하지 않았다고 설명한다. 검토한 시점의 근거 등급은 self_reported였다.
이 선행 보고를 원고에 반영하면서, 이번 기여는 알려진 값에 다시 실행할 수 있는 탐색 코드와 근거를 붙이는 범위로 정했다. Peile–Taylor의 2000년 논문에 실린 원래 수치표는 이번 자료 대조에서도 직접 읽지 못했으므로 그 표의 10×10 항목을 단정하지 않았다. 앞선 보고가 있다는 사실은 유지하며 최초 발견을 주장하지 않는다.
같은 계산을 다시 실행하려면
2026년 9월 5일 공개한 Zenodo 프리프린트와 재현 패키지는 다른 유한 탐색 문제 F01과 묶여 있다. 압축을 푼 루트에서 다음 명령으로 보존된 검증을 따라갈 수 있다. 두 명령 모두 F03뿐 아니라 함께 실린 F01도 검사한다.
python3 verify_all.py REPLAY_NEW
node independent_verifier.js .첫 경로는 Linux 또는 WSL, Python 3.10 이상과 C++17을 지원하는 g++ 또는 clang++가 필요하다. 보관된 실행 환경은 Python 3.12.3과 g++ 13.3.0이다.
두 번째 경로는 Node.js 24.19.0에서 실행한 기록이 있으며, 공통 원자료 파일을 읽되 앞의 Python·C++ 수학 구현을 가져다 쓰지 않는다. 별도의 최적화 솔버나 GPU, 실행 중 네트워크 연결은 필요하지 않다.
공개 자료에 남긴 역할과 검토 상태
문제 자료를 제공하고 프로젝트의 방향과 공개 범위를 정한 역할은 내가 맡았다. 수학적 축약, 탐색 코드와 초기 계산·설명에는 ChatGPT Pro가, 파일 점검과 재실행·선행 자료 대조·추가 계산 검수 및 공개 원고 준비에는 Codex가 실질적으로 관여했다. 기존 10점 배치의 출처도 원고와 데이터 파일에 남겼다.
내 연구 기록 R11761은 2026년 9월 6일 확인 기준 completed, 근거 등급 computational로 등록돼 있다. 그러나 문제 P2682의 공식 상태는 여전히 Open이고, 완전한 해결이 검토를 통과한 상태가 아니다. 서로 다른 구현과 보조 검사는 프로젝트 내부의 계산 검증이며, 외부 인간 심사나 형식 증명 커널의 인증을 받았다는 뜻으로 쓰지 않는다.
이제 10점이 가능한 예뿐 아니라 11점이 배제되는 경로까지 파일에서 따라갈 수 있다. 공개한 것은 이 유한한 문제의 계산 근거와 재실행 방법이며, 다음 검토자는 같은 범위에서 탐색의 빠짐이나 잘못된 중단 조건이 있는지 확인할 수 있다.