기본 수치 보글
에서 이 게시물에 , 우리는에 수치 머뭇 거리는의 게임에 도입$6 \times 6$ 이사회의 규칙은 다음과 같습니다.
- 각 셀은 다음의 단일 숫자를 포함해야합니다. $0$ ...에 $9$.
- 하나의 셀에서 시작하여 인접한 셀 (8 방향 모두)로 이동할 때 숫자를 수집합니다. 숫자가 수집되면 왼쪽에서 오른쪽으로 연결되어 단일 숫자를 형성합니다. 시작 숫자도 수집되며 셀 을 다시 방문 할 수 있습니다 .
그런 다음 작업은 이러한 그리드 (크기 $6 \times 6$) 구성 할 수없는 가장 작은 양수가 가능한 한 커지도록합니다.
당연히이 게임과 후속 최적화는 모든 크기의 정사각형 그리드로 일반화 될 수 있습니다. $n \times n$.
더욱이 우리는$10$. 양의 정수가 주어지면$b$, 우리는 각 셀이 $0$ ...에 $b-1$ 이 새로운 기본에 대해 최적화를 수행합니다 (단항 만 사용하는 단항 제외). $1$).
이 일반화에 동기를 부여하여 더 작은 기반에서 문제를 볼 수 있습니다.
특히 케이스를 보면$n=2$ 과 $b=2$, 최적화 작업은 다음과 같은 결과를 가져올 수 있습니다.
이 그리드 (또는 실제로 $2 \times 2$ 두 그리드 $0$s와 두 $1$s) Numerical Boggle 규칙에 따라 모든 이진수를 구성 할 수 있습니다 (직접 시도해보십시오). 우리는 그러한 그리드가 기본적으로 무한한 범위 를 가지고 있다고 말할 것입니다.$b$.
또한 우리는 기본 $b$ 무한한 범위의 그리드를 인정합니다. 유한 크기의 사각형 그리드가 있습니다 ($n \times n$)베이스에 무한한 범위가 있음 $b$. 이것은 우리를 퍼즐로 인도합니다.
가장 큰 양의 정수 밑은 무엇입니까 $b$ 무한한 범위의 유한 정사각형 그리드를 허용하거나 $b$있다? 답변에 대한 증거를 제공하십시오.
답변
여기에 하한 과 일치 한다고 생각한 다른 답변의 하한과 일치 하는 상한이 있지만 Boggle의 규칙을 오해했습니다.
어떤 $k\times k$ 보드, 길이의 수$n$ 경로는 대략 다음과 같이 자랍니다. $8^n$. 예를 들어,$k^2 \cdot 8^n$: 우리는 $k^2$ 시작하고 거기에서 각 단계는 $8$지도. (모든 방향의 모든 단계가 항상 가능한 것은 아니지만 이것은 상한선입니다.)
그러나 수 $n$-베이스의 숫자 $b$ 대략적으로 자랍니다 $b^n$: 그것은 $(b-1)b^{n-1}$. 그래서$b \ge 9$, 가능한 길이의 경로 수 $n$ 결국 수보다 작을 것입니다 $n$-숫자, 그리고 우리가 찾을 수없는 숫자가있을 것입니다. 보드를 더 크게 만들수록 나중에이 재앙이 발생하지만 결국에는 일어날 것입니다.
아직 공백이 있습니다.
$5 \le b \le 8$, 솔루션이 존재할 수 있지만 우리는 그것을 모릅니다.
우리의 그리드는 유한하고 무한히 긴 시퀀스를 표현할 수 있어야하므로 모든 숫자에 연결되지 않은 사각형의 그리드에 숫자 X를 추가하는 데는 별 의미가 없어 보입니다. 이전 단계에서 잘못 연결된 X를 통해 만들 수없는 시퀀스에 대해 액세스 할 수있는 X가있는 또 다른 사각형이 있어야합니다. 이것은 무한 분기를 일으키는 것으로 보입니다 (가능한 모든 시퀀스를 수용해야하기 때문에 우리는 가정 할 수 있습니다. 항상 우리를 위해 가장 성가신 길을 선택하는 사악한 적이 있다는 사실), 우리는 유한 한 플레이 필드에서 할 수 없습니다.
위의 내용이 사실인지 확실하지 않지만, 모든 자릿수가 가능한 모든 자릿수에 연결되어 필요한 "무한 범위"를 쉽게 제공하는 "잘 연결된"보드를 구성 해 보겠습니다.
Base-3은 간단 해 보입니다 (정사각형을 원하는 경우 임의의 숫자로 패드).
012
0
또는 가능한 최소 자릿수를 사용하여 가능한 최소 제곱에 맞 춥니 다.
0 012 1 2
Base-4는 덜 사소하지만 여전히 가능합니다.
0 0 12 3 1 1 3 2 1 0 0
Base-5에는 어려움이 있습니다.
맨 윗줄에서 가장 왼쪽에있는 "잘 연결된"숫자는 아래쪽과 오른쪽에만 5 개의 이웃을 가질 수 없습니다.
0 4 1 2 3
물론 다른 번호를 추가하여이 문제를 해결할 수 있지만 여전히 문제가 있습니다.
1. 잘 연결된 숫자 (가능한 모든 숫자 옆에 있음),
2. 맨 위 행에,
3. 행 에서 가장 왼쪽에있는 숫자가 동시에있을 수 없습니다 .
따라서 첫 번째 장의 추측이 가치가 있다고 가정하면 (전혀 확실하지 않습니다), 우리가 할 수있는 최선은
표준 4x4 보글 보드 내부에 맞는 base-4.
Misha Lavrov의 답변이 약간 개선되었습니다.
길이의 다른 경로의 수 $nk$ 추적 할 수있는 $n\times n$ 그리드는 최대 $n^2(8^n-3^n)^k$. 이것은 각 그룹의$n$ 연속적인 움직임이 모두 위로 올라갈 수는 없으므로 기껏해야 $8^n-3^n$ 각 그룹에 허용되는 방향 순서.
그만큼 $k$이것의 뿌리는 $n^{2/k}(8^n-3^n)<8^n$ ...에 대한 $k$ 충분히 크다 ( $n$). 따라서 당신은$8^{nk}$ 길이의 다른 수 $nk$ 어떤 가치를 위해 $k$, 그래서 경우 $b=8$ 또한 불가능합니다.
불행히도 나는 이것이 더 이상 밀릴 수 없다고 생각합니다.
봉투 뒷면 계산에 따르면 $n$ 정말 이상있다 $7^k$ 길이의 다른 경로 $k$ 모든 $k$, 무작위 걷기가 있기 때문에 $8$ 전혀 선택하지만 $k-O(k/n)$ 확률이 높은 단계 $8^{1-O(1/n)}>7$ 큰 $n$.
나는 Bass의 대답을 뒷받침하는 더 강력한 주장이 있다고 생각합니다.
1. 유한하게 많은 Boggle 보드의 아일랜드가 모든 시퀀스를 공동으로 생성 할 수있는 경우 하나 이상의 아일랜드가 모든 시퀀스의 0이 아닌 비율을 생성합니다.
2. 아일랜드가 모든 시퀀스의 0이 아닌 비율을 생성 할 수 있다면 실제로 모든 시퀀스를 생성 할 수 있습니다 (따라서 무한 범위를 가짐). 근거 : 특정 유한 한 길이 시퀀스를 생성 할 수없는 경우$k$, 길이에 대해 생성 된 시퀀스의 비율 $\ell+1$ (대략) $1-1/2^k$ 길이의 배 $\ell$. 따라서 모든 사람의 비율$\ell \in [1, \infty)$0으로 수렴합니다. 모순.
3. 무한 범위의 유한 보드에 자체적으로 시작하는 모든 시퀀스를 생성하지 않는 셀이있는 경우 해당 셀은 무한 범위를 손상시키지 않고 제거 할 수 있습니다. 근거 : 결론이 거짓이라고 가정합니다. 그런 다음 일부 시퀀스가 해당 셀을 통과하도록 강요되며, 가정에 의해 보드에서 생성 할 수없는 시퀀스를 구성 할 수 있습니다 (셀에 강제로 적용하는 시퀀스 + 셀에서 생성 할 수없는 시퀀스). . 모순.
4. 모든 유한 보드 $b \ge 5$자신으로 시작하는 모든 시퀀스를 생성 할 수없는 셀이 하나 이상 포함되어 있습니다. 이것은 Bass의 대답에서 관찰되는 것처럼 사소한 일입니다. 맨 위의 가장 왼쪽 셀은 항상 4 이하의 차수를 갖기 때문입니다.
5. 3과 4를 결합하면 무한한 범위의 유한 보드가 존재하지 않습니다. $b \ge 5$.
위의 주장에 논리적 허점이 없다고 가정하면 대답은 다음과 같습니다.
무한한 범위의 보드를 허용하는 최대베이스는 Bass에서 찾을 수 있듯이 4 입니다.
결론에 1 단계와 2 단계는 실제로 필요하지 않은 것 같습니다.
유한 한 섬 집합은 여전히 유한 한 보드입니다.
), 그러나 나는 IMO 이후로 그것들을 유지하기로 결정했습니다. 그들은 흥미로운 관찰입니다.
b = 5에 대한 해 (?) 스케치. 피드백을 요청하기 위해 미완성 사진을 보여주고 있습니다.
일반적인 아이디어 : 유턴이있는 고속도로 :
컬러 코딩 된 청사진. 파란색은 배경입니다. 흰색 선은 각각 4 개의 "차선"이있는 4 개의 교대 방향 스트립을 구분하는 시각 보조 도구입니다. 이것은 단지 일반적인 레이아웃을 보여주는 것입니다. 최종 솔루션에는 더 길고 더 많은 스트립이 필요할 수 있습니다.
단일 스트립 내에서 각 사각형에는 동일한 스트립 내에서 필요한 모든 이웃이 있습니다.
그래서 이것을 죽이는 유일한 방법은 움직임을 한 방향으로 편향시키는 것입니다. 인접한 스트립이 작동하는 곳입니다. 우리는 그들에게 u- 턴하고 필요한 경우 돌아갈 수 있습니다.
그래서 이것이 모든 것을 해결합니까?
100 % 확실하지 않습니다. 두 가지 문제가 있습니다. 1. 우리는 많은 곳에서 유턴을 할 수 있지만 모든 곳이 아닙니다. 2. 변경할 스트립을 항상 선택할 수는 없습니다. 따라서 원칙적으로 우리는 마지막 스트립에 도착하여 도로에서 벗어날 수 있습니다.
2. 강제로 사용하려면 어느 정도 항상 대각선 이동 (직교 이동은 우리에게 너무 많은 흔들림 공간을 제공함)을 강제하고 적절한 시간에 차선을 강제로 변경해야하므로 실제 문제가 아닐 수 있습니다. 우리는 아마도 u- 턴을 할시기를 통제 할 수 없기 때문에이 두 번째 요구 사항은 시행하기가 너무 어려워 보입니다.
내 직감은 1도 처리 할 수 있다는 것입니다 (지금 당장 모든 케이스를 찌르는 것을 귀찮게 할 수는 없습니다. 다른 사람이 계속하고 싶다면 내 찬성 투표가 보장됩니다)
관찰해야 할 한 가지는 전방 계획에 의해서만 패배 할 수있는이 설정에 대한 공격이 실제로 있다는 것입니다. 적이 예고없이 다음 숫자를 결정할 수 있다면 우리를 죽일 수 있습니다.
예는 다음과 같은 세부 전략을 사용하여 위에서 공격 2를 수행하는 것입니다. 노란색-> 빨간색-> 연한 주황색-> 보라색-> 진한 주황색을 통해 U 턴을 강제 실행합니다. 유턴 후 빠르게 한 자리를 반복하여 차선을 변경하고 선택의 여지가없는 색상을 기다리십시오. 다시 시작하다. 차선 변경이 예정된시기를 미리 알고 있다면 U 턴 시점에 정확히 적응하여이 공격을 물리 칠 수 있습니다.