Boggle số cơ bản
Trong bài đăng này , chúng tôi đã được giới thiệu về trò chơi Numerical Boggle trên một$6 \times 6$ hội đồng quản trị, các quy tắc trong đó như sau
- Mỗi ô phải chứa một chữ số từ $0$ đến $9$.
- Bắt đầu từ một ô, bạn thu thập các chữ số khi di chuyển sang các ô lân cận (theo cả 8 hướng). Khi các chữ số được thu thập, chúng được nối từ trái sang phải để tạo thành một số duy nhất. Lưu ý rằng chữ số bắt đầu cũng được thu thập và bạn có thể truy cập lại các ô.
Nhiệm vụ sau đó là xây dựng một lưới như vậy (có kích thước $6 \times 6$) sao cho số dương nhỏ nhất không thể xây dựng được càng lớn càng tốt.
Rõ ràng, trò chơi này và việc tối ưu hóa tiếp theo có thể được tổng quát hóa thành các lưới vuông có kích thước bất kỳ, $n \times n$.
Hơn nữa, chúng ta không cần phải hạn chế bản thân trong việc$10$. Cho bất kỳ số nguyên dương nào$b$, chúng ta có thể quy định rằng mỗi ô phải chứa một chữ số từ $0$ đến $b-1$ và đặt ra tối ưu hóa đối với cơ sở mới này (ngoại trừ cơ sở một ngôi chỉ sử dụng $1$).
Được thúc đẩy bởi sự khái quát này, chúng ta có thể xem xét vấn đề trong các cơ sở nhỏ hơn.
Đặc biệt, nếu chúng ta nhìn vào trường hợp$n=2$ và $b=2$, nhiệm vụ tối ưu hóa của chúng tôi có thể dẫn đến kết quả như sau
Nó chỉ ra rằng, đối với lưới này (hoặc thực sự là bất kỳ $2 \times 2$ lưới với hai $0$s và hai $1$s) có thể xây dựng mọi số nhị phân theo các quy tắc của Numerical Boggle (hãy tự mình thử). Chúng tôi sẽ nói rằng một lưới như vậy có phạm vi vô hạn về cơ sở$b$.
Hơn nữa, chúng tôi sẽ nói rằng một cơ sở $b$ thừa nhận một lưới có phạm vi vô hạn là có một lưới vuông nào đó có kích thước hữu hạn ($n \times n$) có phạm vi vô hạn trong cơ sở $b$. Điều này dẫn chúng ta đến câu đố của chúng ta.
Cơ số nguyên dương lớn nhất là gì $b$ thừa nhận một lưới ô vuông hữu hạn có phạm vi vô hạn hoặc làm như vậy $b$hiện hữu? Vui lòng cung cấp bằng chứng về câu trả lời của bạn.
Trả lời
Đây là giới hạn trên để khớp với giới hạn dưới của câu trả lời khác mà tôi nghĩ là khớp với giới hạn dưới, nhưng tôi đã hiểu sai các quy tắc của Boggle:
Trên bất kỳ $k\times k$ bảng, số chiều dài-$n$ các con đường phát triển gần như $8^n$. Ví dụ, nó được giới hạn bởi$k^2 \cdot 8^n$: chúng ta có $k^2$ nơi để bắt đầu và từ đó, mỗi bước đi một trong những $8$hướng. (Không phải lúc nào cũng có thể thực hiện được mọi bước theo mọi hướng, nhưng đây là giới hạn trên.)
Tuy nhiên, số lượng $n$-digit số trong cơ sở $b$ phát triển gần như $b^n$: nó là $(b-1)b^{n-1}$. Vì vậy đối với$b \ge 9$, số lượng đường đi có thể có độ dài $n$ cuối cùng sẽ nhỏ hơn số lượng $n$-digit số, và sẽ có một số số chúng tôi không thể tìm thấy. Chúng ta làm tấm ván càng lớn thì thảm họa này càng xảy ra muộn, nhưng nó sẽ xảy ra cuối cùng.
Vẫn còn một khoảng cách cho
$5 \le b \le 8$, nơi mà một giải pháp có thể tồn tại, nhưng chúng tôi không biết nó.
Vì lưới của chúng ta là hữu hạn và chúng ta cần có khả năng biểu diễn các chuỗi dài vô hạn, nên có vẻ như có rất ít điểm khi thêm bất kỳ chữ số X nào vào lưới tại một số ô vuông không được kết nối với mọi chữ số: nếu chúng ta đã từng sử dụng chữ số, thì ở bước trước đó cũng sẽ cần một hình vuông khác có X có thể truy cập được cho các trình tự không thể thực hiện thông qua X. được kết nối kém. Điều này dường như gây ra phân nhánh vô hạn (vì chúng ta phải phù hợp với mọi trình tự có thể, chúng ta có thể giả sử rằng có một kẻ thù ác luôn chọn con đường khó chịu nhất cho chúng ta), điều mà chúng ta không thể làm trên một sân chơi hữu hạn.
Tôi không chắc liệu điều trên có thực sự đúng hay không, nhưng giả sử có, chúng ta hãy thử xây dựng một số bảng "được kết nối độc đáo" trong đó mọi chữ số được kết nối với tất cả các chữ số có thể, do đó dễ dàng cung cấp "mức độ vô hạn" cần thiết.
Cơ số 3 có vẻ đơn giản (đệm với các chữ số ngẫu nhiên nếu bạn thực sự muốn một hình vuông):
0 1 1 0
0 2 2 0
hoặc với số chữ số tối thiểu có thể, vừa với bên trong hình vuông nhỏ nhất có thể:
0 0 1 2 1 2
Base-4 ít tầm thường hơn một chút, nhưng vẫn khá khả thi:
0 0 1 2 3 1 1 3 2 1 0 0
Cơ sở 5 đưa ra một khó khăn:
chữ số "được kết nối độc đáo" ở ngoài cùng bên trái ở hàng trên cùng không được có 5 hàng xóm ở phía dưới cùng và bên phải:
0 4 1 2 3
Tất nhiên chúng tôi có thể khắc phục điều này bằng cách thêm một số khác, nhưng chúng tôi vẫn gặp sự cố
không thể có một chữ số đồng thời
1. được nối liền nhau (bên cạnh tất cả các chữ số có thể có),
2. ở hàng trên cùng và
3. chữ số tận cùng bên trái trong hàng của nó.
Vì vậy, giả sử rằng phỏng đoán trong chương đầu tiên có giá trị bất cứ điều gì (tôi không chắc chắn về điều đó), thì điều chúng ta có thể làm là
base-4, vừa với bảng boggle 4x4 tiêu chuẩn.
Một chút cải thiện cho câu trả lời của Misha Lavrov.
Số lượng đường đi có độ dài khác nhau $nk$ có thể được tìm ra trên một $n\times n$ lưới là tối đa $n^2(8^n-3^n)^k$. Điều này là do mỗi nhóm$n$ các chuyển động liên tiếp không thể đi lên tất cả, vì vậy có nhiều nhất $8^n-3^n$ trình tự cho phép của các hướng cho mỗi nhóm.
Các $k$gốc thứ của cái này là $n^{2/k}(8^n-3^n)<8^n$ cho $k$ đủ lớn (về $n$). Vì vậy, bạn có thể thực hiện ít hơn$8^{nk}$ số lượng chiều dài khác nhau $nk$ cho một số giá trị của $k$, vì vậy trường hợp $b=8$ cũng không được.
Thật không may, tôi không nghĩ rằng điều này có thể được đẩy xa hơn nữa:
một phép tính phía sau của một phong bì cho thấy rằng đủ lớn $n$ thực sự có nhiều hơn $7^k$ các con đường dài khác nhau $k$ Cho mọi $k$, vì một cuộc dạo chơi ngẫu nhiên đã $8$ tất cả các lựa chọn nhưng $k-O(k/n)$ các bước có xác suất cao và $8^{1-O(1/n)}>7$ Cho lớn $n$.
Tôi nghĩ rằng tôi có một lập luận mạnh mẽ hơn ủng hộ câu trả lời của Bass.
1. Nếu vô số đảo của bảng Boggle có thể cùng tạo ra tất cả các trình tự, thì ít nhất một đảo tạo ra tỷ lệ khác không của tất cả các trình tự.
2. Nếu một hòn đảo có thể tạo ra tỷ lệ khác không của tất cả các trình tự, nó thực sự có thể tạo ra tất cả các trình tự (và do đó nó có phạm vi vô hạn). Cơ sở lý luận: Nếu nó không thể tạo ra một chuỗi độ dài hữu hạn nhất định$k$, tỷ lệ các trình tự được tạo cho độ dài $\ell+1$ là (đại khái) $1-1/2^k$ nhân với chiều dài $\ell$. Do đó, tỷ lệ cho tất cả$\ell \in [1, \infty)$hội tụ về không. Sự mâu thuẫn.
3. Nếu một bảng hữu hạn với phạm vi vô hạn có một ô không tạo ra tất cả các chuỗi bắt đầu bằng chính nó, ô đó có thể bị loại bỏ mà không làm hại đến phạm vi vô hạn. Cơ sở lý luận: Giả sử kết luận là sai. Sau đó, một số trình tự buộc phải đi qua ô được đề cập và theo giả định, chúng ta có thể xây dựng một trình tự mà bảng không thể tạo ra (đó là trình tự buộc đến ô + trình tự không thể tạo từ ô) . Sự mâu thuẫn.
4. Tất cả các bảng hữu hạn cho $b \ge 5$chứa ít nhất một ô không thể tạo tất cả các chuỗi bắt đầu bằng chính nó. Điều này là không đáng kể khi quan sát thấy trong câu trả lời của Bass, vì ô trên cùng bên trái luôn có độ lệch 4 hoặc thấp hơn.
5. Kết hợp 3 và 4, không tồn tại một bảng hữu hạn với phạm vi vô hạn cho $b \ge 5$.
Giả sử không có bất kỳ lỗ hổng logic nào trong các tuyên bố trên, câu trả lời là
Cơ sở tối đa cho phép một bảng có phạm vi vô hạn là 4 , như được tìm thấy bởi Bass.
Tôi đoán các bước 1 và 2 không thực sự cần thiết cho kết luận (như
một tập hợp hữu hạn các hòn đảo vẫn là một bảng hữu hạn
), nhưng tôi quyết định giữ chúng vì chúng là những quan sát thú vị của IMO.
Vẽ một nghiệm (?) Cho b = 5. Tôi đang hiển thị bức tranh chưa hoàn thành để mời một số phản hồi.
Ý tưởng chung: đường cao tốc có vòng quay:
bản thiết kế mã hóa màu. Màu xanh lam là nền. các vạch trắng là trợ lý trực quan để phân tách bốn dải theo hướng xen kẽ, mỗi dải có bốn "làn đường". Lưu ý rằng đây chỉ là hiển thị bố cục chung; giải pháp cuối cùng có thể yêu cầu dải dài hơn và nhiều hơn.
Quan sát rằng trong một dải duy nhất, mỗi hình vuông có tất cả các hàng xóm được yêu cầu trong cùng một dải.
Vì vậy, cách duy nhất để tiêu diệt điều này là thiên vị chuyển động theo một hướng. Đó là nơi các dải lân cận phát huy tác dụng. Chúng ta có thể lật ngược lại chúng nếu cần.
Vậy điều này có giải quyết được mọi thứ không?
Không chắc chắn 100%. Có hai vấn đề: 1. chúng ta có thể quay đầu ở nhiều nơi nhưng không phải tất cả. 2. không phải lúc nào chúng ta cũng có thể chọn dải để thay đổi. Vì vậy, về nguyên tắc, chúng ta có thể kết thúc ở dải cuối cùng và hết đường.
2. có lẽ không phải là vấn đề thực sự bởi vì để bắt buộc điều này sẽ đòi hỏi ít nhiều phải luôn buộc các bước di chuyển theo đường chéo (các bước di chuyển trực giao gần như chắc chắn cung cấp cho chúng ta quá nhiều khoảng trống) và buộc thay đổi làn đường vào những thời điểm thích hợp. Vì có lẽ chúng ta không thể kiểm soát được khi nào nên lật ngược lại, yêu cầu thứ hai này có vẻ quá khó thực thi.
Cảm giác ruột của tôi là 1 cũng có thể được giải quyết (Tôi chỉ không thể bận tâm đến tất cả các trường hợp ngay bây giờ. Nếu ai khác muốn làm điều đó, hãy tiếp tục ủng hộ của tôi)
Một điều cần quan sát là thực sự có những cuộc tấn công vào thiết lập này mà chỉ có thể bị đánh bại bằng cách lập kế hoạch trước. Nếu kẻ thù có thể quyết định chữ số tiếp theo mà không cần thông báo, họ có thể giết chúng ta:
Ví dụ là tấn công 2 từ phía trên với chiến lược chi tiết sau: đi vòng qua màu vàng-> đỏ-> cam nhạt-> tím-> cam đậm buộc quay đầu. Ngay sau khi quay đầu xe buộc phải chuyển làn bằng cách lặp lại một chữ số, chỉ cần đợi một màu không có lựa chọn nào khác. Bắt đầu lại. Rõ ràng là nếu chúng ta biết trước thời điểm thay đổi làn đường dự kiến, chúng ta có thể thích nghi khi nào chính xác để quay đầu và đánh bại cuộc tấn công này.